Версия для печати темы Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > Python: Общие вопросы > как максимально быстро сравнить два списка

Автор: kulibinka 8.12.2006, 02:22

Как максимально быстро сравнить два спискаКак максимально быстро сравнить два списка. Суть задачи в следующем: у меня есть список (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 оперативной памяти), но это чересчур медленно для моей задачи. Подскажите пожалуйста ф-ю с быстродействием повыше чем мои. Код # -*- coding: windows-1251 -*- #    сравниваю еффективность разных ф-й для подсчета схожести всех елементов 2-х списков import time, random from sets import Set def list_similarity1 (list1, list2):     s1 = Set(list1)     s2 = Set(list2)     return list(s1 & s2) def list_similarity2 (list1, list2):     return [i for i in list1 if i in list2] def check_similarity (check_function, spisok, message):     """получаем ф-ю и список, возвращаем время проверки"""     print '\n', message     spisok_size = len(spisok)     t = time.time()     for i in range(spisok_size):         for j in range(i+1, spisok_size):             list_similarity1(spisok[i], spisok[j])     print time.time() - t, ' seconds' #генерация списков print 'generation test set' spisok = [] spisok_size = 300 all_values = [random.randint(0, 1000000) for i in range(1000000)] for i in range(spisok_size):     spisok.append(random.sample(all_values, 1000)) #тестирую ф-ии print 'testing' print (spisok_size * spisok_size + spisok_size)/2, ' operations' check_similarity(list_similarity1, spisok, 'function with sets') check_similarity(list_similarity2, spisok, 'function with lists')

Автор: Artemios 8.12.2006, 09:24

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

Автор: Mkdir 8.12.2006, 09:31

Для начала давайте исправим ошибки в коде =) строки 20-22: Код for i in range(spisok_size):     for j in range(i+1, spisok_size):         list_similarity1(spisok[i], spisok[j]) а по идее программы предполагается следующее: Код for i in range(spisok_size):     for j in range(i+1, spisok_size):         check_function(spisok[i], spisok[j]) но после правки я так и не дождался второго результата... =) Когда я внимательнее вник в исходник, то мне либо показалось что Вы сделали все слишком сложно, либо я плохо понял задачу. В любом случае, вот мой вариант: Код import time, random def fill_list(list, length):     """Fill list like [[132367, 62145, 83239, 54543], [1355, 33546], ...]"""     for i in xrange(length):         list.append([])         for j in xrange(random.randint(2, 10)):             list[i].append(random.randint(0, 100000)) def list_similarity1(list1, list2):     return list1 == list2 def check_similarity (check_function, list1, list2, message):     print '\n', message     t = time.time()     res = check_function(list1, list2)     print time.time() - t, ' seconds'     if res:         print "Result: True"     else:         print "Result: False" lists_size = 300 print 'generation test list #1...', list1 = [] fill_list(list1, lists_size) print 'ok' print 'generation test list #2...', list2 = [] fill_list(list2, lists_size) print 'ok' print 'testing...' check_similarity(list_similarity1, list1, list2, 'different lists') check_similarity(list_similarity1, list1, list1, 'similar lists') Если я правильно понял задачу, то моя "реализация" превзойдёт все ваши ожидания =)

Автор: Artemios 8.12.2006, 09:37

В случае упорядоченного набора попробуй функцию: Код def cmp_lists(l1,l2):     return len(l1)==len(l2) and reduce(lambda x,y: x and not cmp(y[0],y[1]), zip(l1,l2), 1) (хотя скорость особо гарантировать не буду  )

Автор: Mkdir 8.12.2006, 09:38

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

Автор: Artemios 8.12.2006, 10:11

Цитата(kulibinka @  8.12.2006,  02:22 ) Мне нужно сравнить между собой все елементы spisok - сравнить значит подсчитать какие слова в каждых из двух елементов совпадают ((n*n + n)/2 операций). Цитата(Artemios @  8.12.2006,  09:37 ) В случае упорядоченного набора попробуй функцию: Цитата(Mkdir @  8.12.2006,  09:38 ) Я еще раз перечитал тему и понял, что все-таки неправильно понял =)  Угу, я тоже неправильно. Все-таки неупорядоченные множества

Автор: FunnyFalcon 8.12.2006, 10:22

Попробуйте это. Не уверен, но может оказаться быстрее. Код def list_similarity1 (list1, list2):     s2 = dict.fromkeys(list2)     return [s for s in list1 if s in s2] Или даже усложнить: Код def list_similarity1 (list1, list2):     if len(list1)<=len(list2):         s2 = dict.fromkeys(list2)         return [s for s in list1 if s in s2]     else:         s1 = dict.fromkeys(list1)         return [s for s in list2 if s in s1]

Автор: Artemios 8.12.2006, 11:05

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

Автор: albertn 8.12.2006, 11:21

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

Автор: Artemios 8.12.2006, 11:25

И еще Цитата(kulibinka @  8.12.2006,  02:22 ) Загвоздка в том что n у меня очень большое (десятки тысяч), и потому очень важно найти максимально быструю ф-ю сравнения двух списков из слов. если время критично, может имеет смысл написать сравнение на Си, а потом откомпилировать, как расширение для Питона?

Автор: albertn 8.12.2006, 11:28

Вот кстати функция, которая возвращает матрицу смежности, и треугольную ее версию. Код map(lambda x:map(lambda y:Set(x)&Set(y),spisok),spisok) map(lambda x:map(lambda y:Set(spisok[x])&Set(spisok[y]),xrange(x,len(spisok))),xrange(len(spisok))) Работает медленнее т.к. генерирует сам список. Но если бы твоя функция генерировала подобный список возможно работала бы медленнее.

Автор: Mkdir 8.12.2006, 11:54

Цитата(albertn @ 8.12.2006,  11:21) kulibinka, приведи пример с использованием полученных сравнений, тогда будет всем более понятно +1. Вполне возможно, что задачу можно совсем по-другому решать =)

Автор: kulibinka 8.12.2006, 22:18

За исправление ф-ии сравнения еффективности ф-й спасибо  Насчет того Зачем мне это надо: Все это для вычесления того насколько похожи между собой 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  Цитата Распределение (вероятность) совпадающих и несовпадающих элементов в основной задаче? совершенно неизвестные. И о длинне списков ничего неизвестно. Цитата если время критично, может имеет смысл написать сравнение на Си, а потом откомпилировать, как расширение для Питона?  ох... хорошо бы попробовать, но о Си я ничегошеньки не знаю

Автор: kulibinka 8.12.2006, 23:43

Дополнительно попробовал ф-ии от FunnyFalcon и модуль psyco. Код # -*- coding: windows-1251 -*- #    сравниваю еффективность разных ф-й для подсчета схожести всех елементов 2-х списков import time, random, psyco from sets import Set def check_similarity (check_function, spisok, message):     """получаем ф-ю и список, возвращаем время проверки"""     print '\n', message     spisok_size = len(spisok)     t = time.time()     for i in range(spisok_size):         for j in range(i+1, spisok_size):             check_function(spisok[i], spisok[j])     print time.time() - t, ' seconds' def list_similarity1 (list1, list2):     s1 = Set(list1)     s2 = Set(list2)     return list(s1 & s2) def list_similarity2 (list1, list2):     return [i for i in list1 if i in list2] def list_similarity3 (list1, list2):     s2 = dict.fromkeys(list2)     return [s for s in list1 if s in s2] def list_similarity4 (list1, list2):     if len(list1)<=len(list2):         s2 = dict.fromkeys(list2)         return [s for s in list1 if s in s2]     else:         s1 = dict.fromkeys(list1)         return [s for s in list2 if s in s1] def list_similarity5 (list1, list2):      s1 = Set(list1)      return [i for i in list1 if i in s1] list_similarity11 = psyco.proxy(list_similarity1) list_similarity21 = psyco.proxy(list_similarity2) list_similarity31 = psyco.proxy(list_similarity3) list_similarity41 = psyco.proxy(list_similarity4) list_similarity51 = psyco.proxy(list_similarity5) #генерация списков print 'generation test set' spisok = [] spisok_size = 100 all_values = [random.randint(0, 1000000) for i in range(1000000)] for i in range(spisok_size):     spisok.append(random.sample(all_values, 1000)) #тестирую ф-ии print 'testing' print (spisok_size * spisok_size + spisok_size)/2, ' operations' check_similarity(list_similarity1, spisok, '1') check_similarity(list_similarity2, spisok, '2') check_similarity(list_similarity3, spisok, '3') check_similarity(list_similarity4, spisok, '4') check_similarity(list_similarity5, spisok, '5') check_similarity(list_similarity11, spisok, '11') check_similarity(list_similarity21, spisok, '21') check_similarity(list_similarity31, spisok, '31') check_similarity(list_similarity41, spisok, '41') check_similarity(list_similarity51, spisok, '51') Результат тестов: Цитата 1 20.1790001392  seconds 2 1036.97099996  seconds 3 9.59299993515  seconds 4 9.54400014877  seconds 5 36.1019999981  seconds 11 14.6410000324  seconds 21 1032.13399982  seconds 31 7.02999997139  seconds 41 7.06100010872  seconds 51 30.0729999542  seconds FunnyFalcon*psyco работает в 3 раза быстрее чем моя самая быстрая ф-я! И это уже что-то

Автор: Artemios 9.12.2006, 00:49

Цитата(kulibinka @  8.12.2006,  22:18 ) Все это для вычесления того насколько похожи между собой 2 текста. Пока я знаю только один метод - метод шинглов Здесь: http://forum.vingrad.ru/topic-121705/view/all/index.html над той же задачей думают.

Автор: Artemios 9.12.2006, 06:42

Поигрался немного с кодом. psyco неимею, поэтому убрал. Код # -*- coding: utf8 -*- import time, random from sets import Set def check_similarity (check_function, spisok, message):     print '\n', message     spisok_size = len(spisok)     t = time.time()     for i in xrange(spisok_size):         for j in xrange(i+1, spisok_size):             check_function(spisok[i], spisok[j])     print time.time() - t, ' seconds' def list_similarity1 (list1, list2):     s1 = Set(list1)     s2 = Set(list2)     return list(s1 & s2) #def list_similarity2 (list1, list2):     #return [i for i in list1 if i in list2] def list_similarity3 (list1, list2):     s2 = dict.fromkeys(list2)     return [s for s in list1 if s in s2] def list_similarity4 (list1, list2):     if len(list1)<=len(list2):         s2 = dict.fromkeys(list2)         return [s for s in list1 if s in s2]     else:         s1 = dict.fromkeys(list1)         return [s for s in list2 if s in s1]      def list_similarity5 (list1, list2):      s1 = Set(list1)      return [i for i in list2 if i in s1] def list_similarity12 (list1, list2):     s1 = set(list1)     s2 = set(list2)     return list(s1 & s2) def list_similarity42 (list1, list2):     if len(list1)<=len(list2):         s2 = set(list2)         return [s for s in list1 if s in s2]     else:         s1 = set(list1)         return [s for s in list2 if s in s1] def list_similarity52 (list1, list2):      s1 = set(list1)      return [i for i in list2 if i in s1] print 'generation test set' spisok = [] spisok_size = 100 all_values = [random.randint(0, 1000000) for i in range(1000000)] for i in range(spisok_size):     spisok.append(random.sample(all_values, 1000)) print 'testing' print (spisok_size * spisok_size + spisok_size)/2, ' operations' check_similarity(list_similarity1, spisok, '1') #check_similarity(list_similarity2, spisok, '2') check_similarity(list_similarity3, spisok, '3') check_similarity(list_similarity4, spisok, '4') check_similarity(list_similarity5, spisok, '5') check_similarity(list_similarity12, spisok, '1_2') check_similarity(list_similarity42, spisok, '4_2') check_similarity(list_similarity52, spisok, '5_2') На своей машине получил: Цитата 1 7.00922703743  seconds 3 3.62788891792  seconds 4 3.61328196526  seconds 5 9.78012800217  seconds 1_2 4.05814909935  seconds 4_2 3.58052396774  seconds 5_2 3.28020095825  seconds (1,3,4,5 остались старые, номер 2 выдавал 400 с чем-то секунд, но меня ломало каждый раз его ждать и тоже убрал; 1_2, 4_2, 5_2 -- заменил структуры в нужных местах соответствующих функций на стандартное множество -- set) Вывод: set предпочтителен. Далее, самую быструю 5_2 "в лоб" переписал на pyrex (входной язык -- немного "исковерканный" Питон, предназначена для простого (и неоптимального  ) написания модулей расширения под Питон); а также туда же забил check_similarity, только сузив ее применение: функций сравнения аргументом не принимает, внутри в цикле организована все та же 5_2. В конечном итоге на pyrex имел следующий код: Код import time def list_similarity52(list1, list2):      s1 = set(list1)     res = []     for i in list2:         if i in s1:             res.append(i)     return res def check_similarity53(spisok, message):     print '\n', message     cdef int spisok_size,i,j     spisok_size = len(spisok)     t = time.time()     for i from 0 <=i < spisok_size:         for j from i+1 <=j < spisok_size:             s1 = set(spisok[1])             res = []             for i in spisok[2]:                 if i in s1:                     res.append(i)     print time.time() - t, ' seconds' после его трансляции в Си и компиляции в модуль check_pyrex.so -- могу использовать в Питоне, и завершающий код: Код # -*- coding: utf8 -*- import time, random from sets import Set import check_pyrex def check_similarity (check_function, spisok, message):     print '\n', message     spisok_size = len(spisok)     t = time.time()     for i in xrange(spisok_size):         for j in xrange(i+1, spisok_size):             check_function(spisok[i], spisok[j])     print time.time() - t, ' seconds' def list_similarity1 (list1, list2):     s1 = Set(list1)     s2 = Set(list2)     return list(s1 & s2) #def list_similarity2 (list1, list2):     #return [i for i in list1 if i in list2] def list_similarity3 (list1, list2):     s2 = dict.fromkeys(list2)     return [s for s in list1 if s in s2] def list_similarity4 (list1, list2):     if len(list1)<=len(list2):         s2 = dict.fromkeys(list2)         return [s for s in list1 if s in s2]     else:         s1 = dict.fromkeys(list1)         return [s for s in list2 if s in s1]      def list_similarity5 (list1, list2):      s1 = Set(list1)      return [i for i in list2 if i in s1] def list_similarity12 (list1, list2):     s1 = set(list1)     s2 = set(list2)     return list(s1 & s2) def list_similarity42 (list1, list2):     if len(list1)<=len(list2):         s2 = set(list2)         return [s for s in list1 if s in s2]     else:         s1 = set(list1)         return [s for s in list2 if s in s1] def list_similarity52 (list1, list2):      s1 = set(list1)      return [i for i in list2 if i in s1] print 'generation test set' spisok = [] spisok_size = 100 all_values = [random.randint(0, 1000000) for i in range(1000000)] for i in range(spisok_size):     spisok.append(random.sample(all_values, 1000)) print 'testing' print (spisok_size * spisok_size + spisok_size)/2, ' operations' check_similarity(list_similarity1, spisok, '1') #check_similarity(list_similarity2, spisok, '2') check_similarity(list_similarity3, spisok, '3') check_similarity(list_similarity4, spisok, '4') check_similarity(list_similarity5, spisok, '5') check_similarity(list_similarity12, spisok, '1_2') check_similarity(list_similarity42, spisok, '4_2') check_similarity(list_similarity52, spisok, '5_2') check_similarity(check_pyrex.list_similarity52, spisok, '5_2_pyrex') check_pyrex.check_similarity53(spisok, '5_3_pyrex') на моей машине дал следующий результат: Цитата 1 7.0034198761  seconds 3 3.61762213707  seconds 4 3.60377693176  seconds 5 9.67175197601  seconds 1_2 4.02275705338  seconds 4_2 3.56534600258  seconds 5_2 3.29011011124  seconds 5_2_pyrex 2.38613009453  seconds 5_3_pyrex 0.0568170547485  seconds Вывод: отдельную функцию сравнения переписывать на Си -- не принесет ощутимого выигрыша.

Автор: Artemios 9.12.2006, 14:40

Извиняюсь, вариант 5_3_pyrex неверен, ошибся в коде check_similarity53. Правильный вариант модуля на pyrex: Код import time def list_similarity52(list1, list2):      s1 = set(list1)     res = []     for i in list2:         if i in s1:             res.append(i)     return res def check_similarity53(spisok, message):     print '\n', message     cdef int spisok_size,i,j     spisok_size = len(spisok)     t = time.time()     for i from 0 <=i < spisok_size:         s1 = set(spisok[i])         for j from i+1 <=j < spisok_size:             res = []             for x in spisok[j]:                 if x in s1:                     res.append(x)     print time.time() - t, ' seconds' дальше, Питон без изменения и тест: Цитата 1 7.58109593391  seconds 3 3.63567996025  seconds 4 3.61104297638  seconds 5 9.99201393127  seconds 1_2 4.05328583717  seconds 4_2 3.55678391457  seconds 5_2 3.25729894638  seconds 5_2_pyrex 2.39998984337  seconds 5_3_pyrex 1.1331179142  seconds

Автор: Artemios 9.12.2006, 15:02

А вот такой результат получил на той же машине: Цитата 6 1.10187888145  seconds сформировав в spisok не список списков, а список множеств, и применяя к нему упрощенный вариант 1_2: Код # -*- coding: utf8 -*- import time, random def check_similarity (check_function, spisok, message):     print '\n', message     spisok_size = len(spisok)     t = time.time()     for i in xrange(spisok_size):         for j in xrange(i+1, spisok_size):             check_function(spisok[i], spisok[j])     print time.time() - t, ' seconds' def list_similarity6 (set1, set2):     return set1 & set2 print 'generation test set' spisok = [] spisok_size = 100 all_values = [random.randint(0, 1000000) for i in range(1000000)] for i in range(spisok_size):     spisok.append(set(random.sample(all_values, 1000))) print 'testing' check_similarity(list_similarity6, spisok, '6')

Автор: kulibinka 9.12.2006, 15:11

За неимением понимания pyrex поигрался с вашими ф-ями (засунул их в psyco) Код # -*- coding: windows-1251 -*- #    сравниваю еффективность разных ф-й для подсчета схожести всех елементов 2-х списков import time, random, psyco from sets import Set def check_similarity (check_function, spisok, message):     """получаем ф-ю и список, возвращаем время проверки"""     print '\n', message     spisok_size = len(spisok)     t = time.time()     for i in range(spisok_size):         for j in range(i+1, spisok_size):             check_function(spisok[i], spisok[j])     print time.time() - t, ' seconds' def list_similarity1 (list1, list2):     s1 = Set(list1)     s2 = Set(list2)     return list(s1 & s2) def list_similarity2 (list1, list2):     return [i for i in list1 if i in list2] def list_similarity3 (list1, list2):     s2 = dict.fromkeys(list2)     return [s for s in list1 if s in s2] def list_similarity4 (list1, list2):     if len(list1)<=len(list2):         s2 = dict.fromkeys(list2)         return [s for s in list1 if s in s2]     else:         s1 = dict.fromkeys(list1)         return [s for s in list2 if s in s1] def list_similarity5 (list1, list2):      s1 = Set(list1)      return [i for i in list1 if i in s1] def list_similarity12 (list1, list2):     s1 = set(list1)     s2 = set(list2)     return list(s1 & s2) def list_similarity42 (list1, list2):     if len(list1)<=len(list2):         s2 = set(list2)         return [s for s in list1 if s in s2]     else:         s1 = set(list1)         return [s for s in list2 if s in s1] def list_similarity52 (list1, list2):      s1 = set(list1)      return [i for i in list2 if i in s1] list_similarity11 = psyco.proxy(list_similarity1) list_similarity21 = psyco.proxy(list_similarity2) list_similarity31 = psyco.proxy(list_similarity3) list_similarity41 = psyco.proxy(list_similarity4) list_similarity51 = psyco.proxy(list_similarity5) list_similarity121 = psyco.proxy(list_similarity12) list_similarity421 = psyco.proxy(list_similarity42) list_similarity521 = psyco.proxy(list_similarity52) #генерация списков print 'generation test set' spisok = [] spisok_size = 100 all_values = [random.randint(0, 1000000) for i in range(1000000)] for i in range(spisok_size):     spisok.append(random.sample(all_values, 1000)) #тестирую ф-ии print 'testing' print (spisok_size * spisok_size + spisok_size)/2, ' operations' check_similarity(list_similarity1, spisok, '1') #check_similarity(list_similarity2, spisok, '2') check_similarity(list_similarity3, spisok, '3') check_similarity(list_similarity4, spisok, '4') check_similarity(list_similarity5, spisok, '5') check_similarity(list_similarity12, spisok, '12') check_similarity(list_similarity42, spisok, '42') check_similarity(list_similarity52, spisok, '52') check_similarity(list_similarity11, spisok, '11') #check_similarity(list_similarity21, spisok, '21') check_similarity(list_similarity31, spisok, '31') check_similarity(list_similarity41, spisok, '41') check_similarity(list_similarity51, spisok, '51') check_similarity(list_similarity121, spisok, '121') check_similarity(list_similarity421, spisok, '421') check_similarity(list_similarity521, spisok, '521') Вот результаты: Цитата 1 20.3900001049  seconds 3 10.3249998093  seconds 4 10.1940000057  seconds 5 37.5740001202  seconds 12 11.0559999943  seconds 42 9.93400001526  seconds 52 9.6139998436  seconds 11 15.3519999981  seconds 31 7.5110001564  seconds 41 7.50099992752  seconds 51 32.1660001278  seconds 121 11.1459999084  seconds 421 7.23099994659  seconds 521 5.50699996948  seconds Как видно, ф-я 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 дает максимальную производительность.

Автор: kulibinka 9.12.2006, 15:58

Цитата А вот такой результат получил на той же машине сформировав в spisok не список списков, а список множеств, и применяя к нему упрощенный вариант 1_2 Гениально.  Вот то за что я так долго боролся - Artemios, ОГРОМНОЕ СПАСИБО  И даже psyco только ухудшает результаты  И я сомневаюсь что есть какой-либо другой ощутимо более производительный способ решения этой задачи.

Автор: Artemios 10.12.2006, 04:22

Цитата(kulibinka @  9.12.2006,  15:58 ) И даже psyco только ухудшает результаты  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-й: Цитата 6 0.40700006485  seconds против 1-й секунды Питона 2.4, так что разработчики не обманывали, когда говорили, что 5-я версия работает быстрее. Цитата(kulibinka @  9.12.2006,  15:58 ) И я сомневаюсь что есть какой-либо другой ощутимо более производительный способ решения этой задачи. Оптимизировать в принципе возможно, переписав всю задачу на Си. Как видим, разработчики Питона доказывают, что при грамотном программировании на низкоуровневом языке производительность можно существенно увеличить   Цитата(kulibinka @  9.12.2006,  15:11 ) А не скажете насколько скорость результатов на pyrex приближается к скорости на чистом Си? Если один-в-один перебивать питоновский код в pyrex -- производительность модуля на pyrex особо не возрастет (каждая строчка в стиле python-а будет транслирована в гору сишного кода). Лично мне pyrex понравился, как простенький переходничок для подключения си-шных библиотек, так как в нем можно комбинировать использование и питоновских объектов, и сишных типов, и преобразования между ними.

Автор: kulibinka 10.12.2006, 18:38

Цитата 6 0.40700006485  seconds против 1-й секунды Питона 2.4, так что разработчики не обманывали, когда говорили, что 5-я версия работает быстрее. Обрадованный возможностью настолько сильно повысить производительность не поленился поставить 5-й питон. На моих реальных данных (проверял на шингловость множество из 6000 случайных статей) его скорость равна один в один с 4-й. Возможно в 5-й сделали пооптимальнее сравнение множеств одинаковых размеров. Поэтому в нашем тестовом варианте производительность повысилась, а в моей проверке на шинглах осталась такой же.

Автор: Artemios 10.12.2006, 20:41

жаль. А на реальных данных в сравниваемых множествах элементы какого типа (т.е., для которых у нас тестовый аналог случайные целые числа)? Прото работа с множеством set тем эффективнее, чем эффективнее заданы методы __hash__() для элементов множества. Пример: Код >>> a = 5 >>> a.__hash__() 5 >>> b = '5' >>> b.__hash__() 6784020404 >>> c = ord(b) >>> c 53 >>> c.__hash__() 53 Поэтому, если допустим в множестве храним отдельные символы, то возможным шагом оптимизации будет предварительное преобразование символьных объектов в числовые (например функцией ord).  kulibinka, а нельзя ли здесь выложить (приаттачить к сообщению) код основной программы и несколько статей для теста?

Автор: Artemios 10.12.2006, 23:19

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

Автор: kulibinka 11.12.2006, 01:03

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

Powered by Invision Power Board (http://www.invisionboard.com)
© Invision Power Services (http://www.invisionpower.com)