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

Суть задачи в следующем: у меня есть список (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

Поигрался немного с кодом. psyco неимею, поэтому убрал.

На своей машине получил:

(1,3,4,5 остались старые, номер 2 выдавал 400 с чем-то секунд, но меня ломало каждый раз его ждать и тоже убрал; 1_2, 4_2, 5_2 -- заменил структуры в нужных местах соответствующих функций на стандартное множество -- set)
Вывод: set предпочтителен.

Далее, самую быструю 5_2 "в лоб" переписал на pyrex (входной язык -- немного "исковерканный" Питон, предназначена для простого (и неоптимального  ) написания модулей расширения под Питон); а также туда же забил check_similarity, только сузив ее применение: функций сравнения аргументом не принимает, внутри в цикле организована все та же 5_2. В конечном итоге на pyrex имел следующий код:

после его трансляции в Си и компиляции в модуль check_pyrex.so -- могу использовать в Питоне, и завершающий код:

на моей машине дал следующий результат:

Вывод: отдельную функцию сравнения переписывать на Си -- не принесет ощутимого выигрыша.

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

Извиняюсь, вариант 5_3_pyrex неверен, ошибся в коде check_similarity53.
Правильный вариант модуля на pyrex:

дальше, Питон без изменения и тест:

А вот такой результат получил на той же машине:

сформировав в spisok не список списков, а список множеств, и применяя к нему упрощенный вариант 1_2:

За неимением понимания pyrex поигрался с вашими ф-ями (засунул их в psyco)



Вот результаты:



Как видно, ф-я 521 (52 с использованием psyco) работает почти в 4 раза быстрее чем моя начальная - еще лучше 

А не скажете насколько скорость результатов на pyrex приближается к скорости на чистом Си?

Если они идентичны, то 52 с использованием psyco (у меня ф-я 1 - 20.3900001049 , эта 5.50699996948 - в 3.6 раз выше скорость) лучше чем 52 на Си (у вас ф-я 1 - 7.58109593391, а 52 на pyrex 2.39998984337 - в 3.1 раз выше скорость).

А значит использование psyco дает максимальную производительность.

Гениально. 
Вот то за что я так долго боролся - Artemios, ОГРОМНОЕ СПАСИБО 

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

Это сообщение отредактировал(а) kulibinka - 9.12.2006, 16:21

psyco, как я понимаю, оптимизирует байт-код Питона, а в No 6 его почти небудет -- builtin функции, реализованные, как и весь Питон, на Си.

Кстати, по поводу реализации. Все предыдущие тесты я проводил в ОС Linux на Python 2.4. 
Попробовал в Windows-е для ф-й 1,3,4,5,12,42,52 и отдельно для 6: 
на Python 2.4 результаты примерно такие же;
на Python 2.5 примерно на пол-секунды лучше прежнего работают варианты 12,42,52 (10%-15% относительного времени), 
а вот 6-й:

против 1-й секунды Питона 2.4, так что разработчики не обманывали, когда говорили, что 5-я версия работает быстрее.


Оптимизировать в принципе возможно, переписав всю задачу на Си. Как видим, разработчики Питона доказывают, что при грамотном программировании на низкоуровневом языке производительность можно существенно увеличить  


Если один-в-один перебивать питоновский код в pyrex -- производительность модуля на pyrex особо не возрастет (каждая строчка в стиле python-а будет транслирована в гору сишного кода). Лично мне pyrex понравился, как простенький переходничок для подключения си-шных библиотек, так как в нем можно комбинировать использование и питоновских объектов, и сишных типов, и преобразования между ними.

Это сообщение отредактировал(а) Artemios - 10.12.2006, 04:24

Обрадованный возможностью настолько сильно повысить производительность не поленился поставить 5-й питон.
На моих реальных данных (проверял на шингловость множество из 6000 случайных статей) его скорость равна один в один с 4-й.

Возможно в 5-й сделали пооптимальнее сравнение множеств одинаковых размеров. Поэтому в нашем тестовом варианте производительность повысилась, а в моей проверке на шинглах осталась такой же.

 жаль. А на реальных данных в сравниваемых множествах элементы какого типа (т.е., для которых у нас тестовый аналог случайные целые числа)?
Прото работа с множеством set тем эффективнее, чем эффективнее заданы методы __hash__() для элементов множества. Пример:

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

kulibinka, а нельзя ли здесь выложить (приаттачить к сообщению) код основной программы и несколько статей для теста?

Это сообщение отредактировал(а) Artemios - 10.12.2006, 20:50

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

Насчет кода и статей написал Вам в личку.

А насчет создания хешей то у меня так все и реализовано (см. код).