Some HAT...

= Анабар.ru => Python-форумы => Язык программирования Python => сообщение 1021
| Вход | Регистрация
нет
фото
Автор:  kylib
Дата:  8-Dec-2006 02:33 (gmt = -3.0)

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

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

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



все сообщения ветви:

Недостаточно прав для написания ответа
Время генерации страницы в секундах: 0.135