Здравствуйте
У меня возникла такая задача.
Есть две строчки a1 и a2 одинаковой длины n. Элементы строк - целые числа, от 1 до M, упорядочены по возрастанию, повторов в строчке нет. Требуется найти число одинаковых элементов в двух строках, и указать позиции отличающихся элементов. Если в ходе сравнения выясняется, что разных элементов больше 4, то их позиции можно не находить.
Проблема состоит в том, что операция сравнения повторяется у меня в программе несколько миллионов раз и является бутылочным горлышком. Поэтому мне нужен максимально быстрый алгоритм.
Навскидку я придумал два алгоритма.
1. Проходить одновременно две строки, сравнивать текущие элементы и сдвигаться на различных. Если сдвигов больше двух - прекращать.
2. Развернуть каждую строчку a_i в строку q_i длины M, записать едининички в позиции, номер которых равен значениям элементов a. Разность строк q1 и q2 содержит \pm единички как раз там, где были отличающиеся элементы. Остается воспользоваться поиском.
Первый алгоритм, хотя и использует упорядоченность элементов и ограничение по числу различий, работает медленнее, чем второй, at least, в интересующей меня области параметров n=10, M=30.
Оба, тем не менее, зарезают производительность всей программы. Пожалуйста, подскажите наиболее быстрый способ сравнения для моей задачи. Спасибо!
p.s. Происхождение задачи: строчки суть сочетания из M по n, определяют возбужденные состояния в многочастичной системе, и сравниваются при вычислении гамильтониана.
У меня возникла такая задача.
Есть две строчки a1 и a2 одинаковой длины n. Элементы строк - целые числа, от 1 до M, упорядочены по возрастанию, повторов в строчке нет. Требуется найти число одинаковых элементов в двух строках, и указать позиции отличающихся элементов. Если в ходе сравнения выясняется, что разных элементов больше 4, то их позиции можно не находить.
Проблема состоит в том, что операция сравнения повторяется у меня в программе несколько миллионов раз и является бутылочным горлышком. Поэтому мне нужен максимально быстрый алгоритм.
Навскидку я придумал два алгоритма.
1. Проходить одновременно две строки, сравнивать текущие элементы и сдвигаться на различных. Если сдвигов больше двух - прекращать.
2. Развернуть каждую строчку a_i в строку q_i длины M, записать едининички в позиции, номер которых равен значениям элементов a. Разность строк q1 и q2 содержит \pm единички как раз там, где были отличающиеся элементы. Остается воспользоваться поиском.
Первый алгоритм, хотя и использует упорядоченность элементов и ограничение по числу различий, работает медленнее, чем второй, at least, в интересующей меня области параметров n=10, M=30.
Оба, тем не менее, зарезают производительность всей программы. Пожалуйста, подскажите наиболее быстрый способ сравнения для моей задачи. Спасибо!
p.s. Происхождение задачи: строчки суть сочетания из M по n, определяют возбужденные состояния в многочастичной системе, и сравниваются при вычислении гамильтониана.