Сравнение двух строк

> Есть две строчки длины n. Элементы - целые числа, от 1 до M, упорядоченны по возрастанию (т.е. лексикографически),

ты что лексикографически упорядочиваешь? Две строчки или элементы-числа?

> определяют возбужденные состояния в многочастичной системе, и сравниваются при вычислении гамильтониана

это обман себя и окружающих -- произносить такие умные слова и не мочь простейшую задачку решить, найти отличающиеся элементы в упорядоченных цепочках чисел. Убей себя об стену.

> Спасибо за помощь.

пожалуйста

>ты что лексикографически упорядочиваешь?

Упорядоченны элементы каждой строки.

>это обман себя и окружающих -- произносить такие умные слова и не мочь простейшую задачку решить

У меня есть два алгоритма, но я недоволен их скоростью.

>Убей себя об стену.

5.2

> У меня есть два алгоритма, но я недоволен их скоростью.

Ну так расскажи, что ты уже сделал, какие алгоритмы.
Лучше с кодом, его же немного должно быть.
Какой смысл тратить время на решение, чтобы потом оказалось,
что таким способом ты уже пробовал и он тебе не подошел?

> У меня есть два алгоритма, но я недоволен их скоростью.

нужно делать проход одновременно двух строк и сравнивать их элементы. И продвигаться то по одной строке то по другой. Думаю такой алгоритм у тебя уже есть.

Единственно как это можно ускорить -- продвигаться не по 1 элементу а по нарастающей (1-2-4-8-..) а потом искать бинарным поиском.. Это если n большое.

>нужно делать проход одновременно двух строк и сравнивать их элементы. И продвигаться то по одной строке то по другой. Думаю такой алгоритм у тебя уже есть.

Да, есть, и я возлагал на него большие наджеды, поскольку он явно использует лексикографическую упорядоченность элементов.
Реализован он так (в нотациях Mathematica 5.2):

M = 30; n = 10;
(*здесь порождаются сочетания*)
P = Binomial[M, n];
a = Table[0, {p, P}, {k, n}];
a[[1]] = Table[k, {k, n}];
Do[a[[p]] = a[[p - 1]]; k = n;
While[a[[p, k]] == M + k - n, k--]; a[[p, k]]++;
Do[a[[p, i]] = a[[p, i - 1]] + 1, {i, k + 1, n}], {p, 2, P}]

(*строки матрицы "a" мне как раз и надо сравнить. номера строк пусть будут p1 и p2, сравниваются нарочно с конца, s1 и s2 делают сдвиг на отличающемся элементе, k - номер текущего элемента*)

Do[s1 = s2 = 0; k = n; d1 = d2 = Table[0, {k, 3}];
While[s1 < 3 && s2 < 3 && k - s1 > 0 && k - s2 > 0,
Which[a[[p1, k - s1]] > a[[p2, k - s2]],
d1[[s1 + 1]] = a[[p1, k - s1]]; s1++,
a[[p1, k - s1]] < a[[p2, k - s2]],
d2[[s2 + 1]] = a[[p2, k - s2]]; s2++,
a[[p1, k - s1]] == a[[p2, k - s2]], k--
]
];
(*здесь осталось аккуратно записать разные элементы, повозившись с концевыми, это уже не так важно*)
If[Max[{s1, s2}] > 2, tag = 0,
Which[s1 - s2 == 1, d2[[s1]] = a[[p2, 1]], s2 - s1 == 1,
d1[[s2]] = a[[p1, 1]], s1 - s2 == 2, d2[[1]] = a[[p2, 2]];
d2[[2]] = a[[p2, 1]], s2 - s1 == 2, d1[[1]] = a[[p1, 2]];
d1[[2]] = a[[p1, 1]]
]
]
Собственно, вот. Возможно, я неоптимально его реализовал. Но он работает процентов на 10 дольше, чем алгоритм, НЕ использующий упорядоченность. Смотрите:

q1 = q2 = Table[0, {i, M}];
(*ставлю в соответствие элементам строчки 'a' единички, которые находятся в строке q на позиции, равной значению элемента*)
Do[q2[[a[[p2, i]]]] = q1[[a[[p1, i]]]] = 1, {i, 1, n}];
(*теперь строки q вычитаю, и получаю \pm единички только там, где были разные элементы. Остается сосчитать число единичек, и найти их позиции. Это делается штатными средствами*)
qd = q1 - q2;
t = \Sum_{i = 1}^{i=M} |qd[[i]]|;
Which[t == 4, p1d = Position[qd, 1]; p2d = Position[qd, -1];
k1 = Position[a[[p1]], p1d[[1, 1]]]; k2 = Position[a[[p1]], p1d[[2, 1]]];
k3 = Position[a[[p2]], p2d[[1, 1]]]; k4 = Position[a[[p2]], p2d[[2,1]]];tag=4,t == 2, p1d = Position[qd, 1]; p2d = Position[qd, -1]; k1 =
Position[a[[p1]], p1d[[1, 1]]]; k2 = Position[a[[p2]], p2d[[1, 1]]];tag=2,t>4,tag=0]
И вот этот алгоритм работает быстрее, at least в интересующей меня области: n порядка 10, M порядка 30.

Проблема состоит в том, что мне нужно сравнить несколько миллионов пар строк. И это отжирает кучу времени, больше всего времени в моей программе. Если я неоптимально реализовал алгоритмы, подскажите, где.
И еще, пожалуйста, объясните, в чем смысл "продвижения по нарастающей". Спасибо.

> поскольку он явно использует лексикографическую упорядоченность элементов.

по терминологии: лексикографически упорядочивают строки. Например: (1,5,7) < (1,5,9) < (1,6,1) < (2,1,1) < (2,3,0) Числа конечно тоже можно рассматривать как строки из одного элемента, но про них не принято говорить что их _лексикографически_ упорядочивают.

> Но он работает процентов на 10 дольше, чем алгоритм, НЕ использующий упорядоченность.

Для M не намного большего чем n -- в первом больше сравнений чем во втором. А непредсказуемые сравнения -- большой тормоз на современных процах.

> в чем смысл "продвижения по нарастающей".

ну вот ты делаешь s1++ или s2++ -- продвигаешь на 1. А нужно в первый раз продвинуть на 1. А потом, если нужно продвигать опять ту же строку то продвинуть на 2. И т.д. А когда дойдешь до того что неравнество стало в другую сторону, то обратно вернуться бинарным поиском. Но это оправдано только для больших n и возможных сильных неравномерностях в распределении чисел-элементов.

>по терминологии: лексикографически упорядочивают строки.

Правильно, это я заговорился. Сразу ведь написал - упорядоченны по возрастанию.

>Для M не намного большего чем n -- в первом больше сравнений чем во втором.

Да, я так и думал, что асимптотически, при больших M/n, первый алгоритм должен быть быстрее. Но у меня M/n порядка 3, не больше.

А вот, говрят, есть еще алгоритмы Оливера, Левинштейна, etc. Они здесь применимы?

> Элементы - целые числа, от 1 до M, упорядоченны по возрастанию (т.е. лексикографически), повторов в строчке нет

> Требуется найти число одинаковых элементов в двух строках, и указать позиции отличающихся элементов

короче говоря Вам нужен еффективный алгоритм объединения двух упорядоченных множеств. Сразу замечу, что предствление таких множеств в виде векторов (строк) крайне неэффективно по скорости операций объединения и вычитания. Посмотрите другие способы предствления множеств - в частности деревья.

ключевое слово "представить данные по другому" сказано :)

почитайте классику CS - получите огромное удовольствие

Это почему обьединения-то?

потому как "Требуется найти число одинаковых элементов" и "позиции отличающихся" то есть слегка можифицированный алгоритм объединения множеств. Хотя можно модифицировать и алг. пересечения.

p.s. я думаю все поняли что имелось в виду, и не стоит предираться к словам.

Упоминание об "алгоритме Оливера" встречается, похоже, только в описании функции PHP similar_text, которая работает за время O(n^3). В общем, предыдущей фразы достаточно, чтобы потерять к этому алгоритмы интерес. Тем не менее, статья, на которую ссылаются из описания (http://citeseer.ist.psu.edu/oliver93decision.html) не проясняет картины.

Алгоритма Левенштейна как такового нет; есть т.н. "расстояние Левенштейна", определяющее (как и similar_text) степень "похожести" двух строк. Не та задача.

Глядя на твоё условие, можно сказать очевидную фразу: в общем случае, время работы любого алгоритма не может быть меньше 2n шагов (т.к. у тебя 2n чисел в исходных данных). Простейший алгоритм вида

---
"установить по указателю на начало каждой строки; на каждом шаге продвигать на 1 вперёд указатель с меньшим значением, или оба сразу в случае равенства"
---

как раз 2n шагов и делает, и не требует дополнительной памяти. Если именно он у тебя реализован (я не вникал в твой код) и работает медленнее, чем алгоритм, не использующий упорядочение, то это дефект реализации.

По поводу представления исходных данных в иных структурах (не в строках) -- не думаю, что здесь это нужно для получения требуемого результата.

Попытки "скакать" на больше чем 1 элемент тоже не кажутся целесообразными, однако можно попробовать (результат зависит от разброса чисел в строках -- если в одной строке будут числа идти подряд, а в другой -- с большими промежутками, то может оказаться быстрее).

Спасибо, все понял. Дожму простейший алгоритм со сдвигом на один элемент.

кстати STL`у для такой операции требуется 2*(N1+N2)-1 сравнение
(N1,N2 размеры множеств),
дерзайте, вдруг получится лучше !

Eсли у тебя мощность M меньше 64 и повторов быть не может, то 
подумай о такой фигне:

1) Берешь 64-разраядное целое. 

2) Каждому числу из M ставишь в соответствие бит этого числа. 

Получаешь 1-1-значное отображение f вида

1 -> 00...001
2 -> 00...010
3 -> 00...100

Например,

int64 f(uint x)
{
   return 1 << x;
}

3)  Этап преобразования входных данных. Кодируешь свои строки s1 и s2 
след образом

int64 string2int64(s)
{
    int64 res = 0;
    for (int i =0; i<s.length();i++) res += f(s[i]); 
}

4) Этап собственно сравнения 

   r = r1 & r2 - все те числа которые совпали
   ! r - все те числа которые несовпали и которых небыло
   ! r & (r1 | r2) - все числа которые не совпали 

r1, r2 - закодированные строки

Фсе. Дальше можно навернуть костыль для опеределния позиций без 
особых проблем. 

Вообщем то так и реализуются операции над множествами с маленькой 
мощностью в ЭВМ. 

Разумеется тут надо подумать как убрать явное преобразование входных данных

угу, я ведь так и сделал, только единицы писал не в 64-разрядное число, а в строку (что дольше, но проще реализуется в Mathematica). и ведь так получилось быстрее всех прочих алгоритмов.

В число лучше. Гораздо быстрее получится (если получится правильно реализовать f и f^-1 преобразование)

> В число лучше. Гораздо быстрее получится (если получится правильно реализовать f и f^-1 преобразование)

AI нужно двигать, чтобы компилятор сам мог такие оптимизации делать..

А работу потерять не боишься :) ?

Тебе насоветовали здесь много полезного с чем я согласен.

Я бы ещё попробовал использовать статистический подход. Построй распределение вероятности появления несовпадающих чисел в зависимости от их номера в строке. Если распределение равномерное, то тут ничего не поймаешь, но если имеются выраженные пики с номерами "центров или островов притяжения", то сравнение надо начинать в первую очередь с этих номеров, учитывая что уже после 4-х расхождений ты прекращаешь сравнивание, при ярко выраженной неравномерности можно существенно ускорить работу.

Вы правы:) Несовпадающие элементы появляются у меня, в основном, в конце строк. Именно поэтому я начинаю сравнивать строки с конца в том алгоритме, где используются указатели.