Как максимально быстро сравнить два списка.
Суть задачи в следующем: у меня есть список (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 оперативной памяти), но это чересчур медленно для моей задачи.
Подскажите пожалуйста ф-ю с быстродействием повыше чем мои.
1 # -*- coding: windows-1251 -*-
2 # сравниваю еффективность разных ф-й для подсчета схожести всех елементов 2-х списков
3
4 import time, random
5 from sets import Set
6
7 def list_similarity1 (list1, list2):
8 s1 = Set(list1)
9 s2 = Set(list2)
10 return list(s1 & s2)
11
12 def list_similarity2 (list1, list2):
13 return [i for i in list1 if i in list2]
14
15 def check_similarity (check_function, spisok, message):
16 """получаем ф-ю и список, возвращаем время проверки"""
17 print '\n', message
18 spisok_size = len(spisok)
19 t = time.time()
20 for i in range(spisok_size):
21 for j in range(i+1, spisok_size):
22 list_similarity1(spisok[i], spisok[j])
23 print time.time() - t, ' seconds'
24
25
26 #генерация списков
27 print 'generation test set'
28 spisok = []
29 spisok_size = 300
30 all_values = [random.randint(0, 1000000) for i in range(1000000)]
31 for i in range(spisok_size):
32 spisok.append(random.sample(all_values, 1000))
33
34 #тестирую ф-ии
35 print 'testing'
36 print (spisok_size * spisok_size + spisok_size)/2, ' operations'
37 check_similarity(list_similarity1, spisok, 'function with sets')
38 check_similarity(list_similarity2, spisok, 'function with lists')