Как максимально быстро сравнить два спискаКак максимально быстро сравнить два списка.

Суть задачи в следующем: у меня есть список (spisok) длинны n. Он состоит из списков некоторых слов.
Например [[a, b, c], [c, k], [3, i, l, d, k], ...]
Мне нужно сравнить между собой все елементы spisok - сравнить значит подсчитать какие слова в каждых из двух елементов совпадают ((n*n + n)/2 операций).
Загвоздка в том что n у меня очень большое (десятки тысяч), и потому очень важно найти максимально быструю ф-ю сравнения двух списков из слов.

У меня есть 2 версии этой ф-ии (см. код), которые приблизительно равные по быстродействию.
Список длинны n = 300 они обрабатывают за 200 и 203 секунды соответственно (у меня 600 пентиум и 512 оперативной памяти), но это чересчур медленно для моей задачи.

Подскажите пожалуйста ф-ю с быстродействием повыше чем мои.

Вопрос: список рассматривается как упорядоченный набор, или как неупорядоченное множество?
То есть равны ли в твоей задаче списки [a,b,c] и [b,c,a]?

Для начала давайте исправим ошибки в коде =)

строки 20-22:


а по идее программы предполагается следующее:


но после правки я так и не дождался второго результата... =)

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



Если я правильно понял задачу, то моя "реализация" превзойдёт все ваши ожидания =)

Это сообщение отредактировал(а) Mkdir - 8.12.2006, 09:33

В случае упорядоченного набора попробуй функцию:

(хотя скорость особо гарантировать не буду  )

Это сообщение отредактировал(а) Artemios - 8.12.2006, 09:42

Я еще раз перечитал тему и понял, что все-таки неправильно понял =)

Угу, я тоже неправильно. Все-таки неупорядоченные множества  

Попробуйте это. Не уверен, но может оказаться быстрее.

Или даже усложнить:

Для неупорядоченных наборов еще вопросы:
Могут ли в списках встречаться повторяющиеся элементы, и если да, то зависит ли сравнение от количества повторений, то есть равны ли списки 
[a,b,c] и [a,a,b,c], а также списки [a,a,b,c] и [a,b,b,c] ?
Распределение (вероятность) совпадающих и несовпадающих элементов в основной задаче?

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

И еще

если время критично, может имеет смысл написать сравнение на Си, а потом откомпилировать, как расширение для Питона?

Вот кстати функция, которая возвращает матрицу смежности, и треугольную ее версию.

Работает медленнее т.к. генерирует сам список. Но если бы твоя функция генерировала подобный список возможно работала бы медленнее.

+1. Вполне возможно, что задачу можно совсем по-другому решать =)

За исправление ф-ии сравнения еффективности ф-й спасибо 

Насчет того Зачем мне это надо: Все это для вычесления того насколько похожи между собой 2 текста.
Пока я знаю только один метод - метод шинглов (http://company.yandex.ru/articles/article10.html и http://company.yandex.ru/articles/spamooborona.html).
Вкратце: вот нужно мне например сравнить 2 текста. Тогда я для каждого из них создаю список шинглов, а потом сравниваю эти 2 списка.

Из самой идеи шинглов видно что списки неупорядочены.

"Равны ли [a,b,c] и [a,a,b,c]"
это значит что первый текст на 100% лежи во втором (на 100% похож на второй), а второй на 75% похож на первый (3 из 4-х елементов полностью совпали).

"Равны ли [a,a,b,c] и [a,b,b,c]"
Аналогично - не равны. Но на 75% похожи друг на друга.

Добавлено @ 22:25 

совершенно неизвестные. И о длинне списков ничего неизвестно.


ох... хорошо бы попробовать, но о Си я ничегошеньки не знаю 

Дополнительно попробовал ф-ии от FunnyFalcon и модуль psyco.



Результат тестов:



FunnyFalcon*psyco работает в 3 раза быстрее чем моя самая быстрая ф-я! И это уже что-то 

Здесь:
http://forum.vingrad.ru/topic-121705/view/all/index.html
над той же задачей думают.

Это сообщение отредактировал(а) Artemios - 9.12.2006, 00:51