Знаю что есть алгоритм чтобы находить proximity of 2 strings и определять есть это варианты одного и того же стринга или нет. Например сравнение имени человека. Last name is the same, first name - вариации bill, Will etc. middle name is optional.
А нет интересно алгоритма по определению proximity of 2 lists? Скажем в списке сегодня 100 членов а завтра 102 и 99 из них совпадают, значит скорее всего речь об одном и том же списке, просто в него три члена добавили
Algorithm question
-
- Уже с Приветом
- Posts: 19041
- Joined: 11 Jan 2012 09:25
- Location: CA
Algorithm question
https://www.youtube.com/watch?v=wOwblaKmyVw
-
- Уже с Приветом
- Posts: 3647
- Joined: 23 May 2010 15:10
Re: Algorithm question
собственно в чем проблема
фигачишь в hash-таблицу первый список, далее пробегаешь по второму и смотришь, если элемент есть в hash-таблице, то удаляешь его оттуда, если нет, то элемент добавляешь во вторую (новую) hash-таблицу. В итоге, в первой hash-таблице элементы, которые есть в первом, но нет во втором, во второй hash-таблице - элементы, которые есть во втором, но нет в первом. Соответственно, различные элементы - это объединение этих hash-таблиц
сложность O(n1 + n2) = O(n) (n1 - длина первого, n2 - второго списков)
фигачишь в hash-таблицу первый список, далее пробегаешь по второму и смотришь, если элемент есть в hash-таблице, то удаляешь его оттуда, если нет, то элемент добавляешь во вторую (новую) hash-таблицу. В итоге, в первой hash-таблице элементы, которые есть в первом, но нет во втором, во второй hash-таблице - элементы, которые есть во втором, но нет в первом. Соответственно, различные элементы - это объединение этих hash-таблиц
сложность O(n1 + n2) = O(n) (n1 - длина первого, n2 - второго списков)
-
- Уже с Приветом
- Posts: 3647
- Joined: 23 May 2010 15:10
Re: Algorithm question
Соответственно, для вашей задачи, нужно ввести критерий, что считать модификацией одного списка, например, изменилось не более n элементов, или изменилось не более i% элементов.
-
- Уже с Приветом
- Posts: 19041
- Joined: 11 Jan 2012 09:25
- Location: CA
Re: Algorithm question
Это я понимаю просто был еше специальный алгоритхм для этого дела. Сейчас вспомню и напишуAlexandr wrote:Соответственно, для вашей задачи, нужно ввести критерий, что считать модификацией одного списка, например, изменилось не более n элементов, или изменилось не более i% элементов.
https://www.youtube.com/watch?v=wOwblaKmyVw
-
- Уже с Приветом
- Posts: 19041
- Joined: 11 Jan 2012 09:25
- Location: CA
Re: Algorithm question
Нашла !
https://en.wikipedia.org/wiki/Levenshtein_distance" onclick="window.open(this.href);return false;
но в моем случае и правда не надо, просто find union of 2 sets (removeAll ) и проверить критерий
https://en.wikipedia.org/wiki/Levenshtein_distance" onclick="window.open(this.href);return false;
но в моем случае и правда не надо, просто find union of 2 sets (removeAll ) и проверить критерий
https://www.youtube.com/watch?v=wOwblaKmyVw
-
- Уже с Приветом
- Posts: 3647
- Joined: 23 May 2010 15:10
Re: Algorithm question
спасибо, тож освежу в памятиСабина wrote:Нашла !
https://en.wikipedia.org/wiki/Levenshtein_distance" onclick="window.open(this.href);return false;
но в моем случае и правда не надо, просто find union of 2 sets (removeAll ) и проверить критерий