Сравнение двух больших списков в python

У меня есть один список, содержащий около 400 слов. И еще один список списков, в котором каждый список содержит около 150 000 слов. В этом списке 20 таких списков.

Теперь я хочу посмотреть, сколько из этих 400 слов появляется во всех этих 150 000 слов. Я также хочу знать слово из этих 400 слов, сколько раз в списке слов 150 тыс. Слов, какие из этих слов встречаются больше всего, сколько раз и т. Д.

Единственное решение, о котором я могу думать, – это полиномиальное решение времени. Это очень плохое решение и будет чересчур медленным:

for one_list in list_of_150kwords: for key in 400_words: for word in one_list: if key == word: # count this word # do other stuff 

Это очень уродливое и плохое решение, но я не могу придумать ничего лучшего. Я пробовал то же самое с NumPy, преобразовывая эти списки в массивы NumPy:

 list_of_150kwords = numpy.array(list_of_150kwords) ... 

Но я все еще нахожу это очень медленным. Любое другое решение? Или любая библиотека?

4 Solutions collect form web for “Сравнение двух больших списков в python”

Это звучит неплохо для использования set :

 set_of_150kwords = set(list_of_150kwords) one_set = set(one_list) len(one_set & set_of_150kwords) # set intersection is & => number of elements common to both sets 

Согласно теории множеств, пересечение двух множеств дает элементы, которые появляются в обоих множествах, то это просто вопрос о его длине. Для второй части (какой из этих слов встречается больше всего, сколько раз и т. Д.) Создайте Counter с list_of_150kwords , который расскажет вам, сколько раз каждое слово появляется в списке. И набор пересечений скажет вам, какие общие слова, решая оба ваших требования.

 from collections import Counter search_data = [ ["list", "of", "150k", "words"], ["another", "list", "of", "150k", "words"], ["yet", "another", "list", "of", "150k", "words"] # ... 17 more of these ] search_words = ["four", "hundred", "words", "to", "search", "for"] def word_finder(words_to_find): lookfor = set(word.lower() for word in words_to_find) def get_word_count(text): return Counter(word for word in (wd.lower() for wd in text) if word in lookfor) return get_word_count def get_words_in_common(counters): # Maybe use c.viewkeys() instead of set(c)? Which is faster? return reduce(operator.and_, (set(c) for c in counters)) def main(): wordcount = word_finder(search_words) counters = [wordcount(wordlst) for wordlst in search_data] common_to_all = get_words_in_common(counters) print(common_to_all) if __name__=="__main__": main() 

Это канонический пример того места, где будет полезно Trie . Вам нужно создать Trie для каждого из ваших 150K-списков. Затем вы можете проверить, существует ли данное слово в списке в O (W). где W – максимальная длина слова.

Затем вы можете просмотреть список из 400 слов и проверить, работает ли каждая работа в списке слов 150K.

Учитывая, что L, то есть число 150K-списков намного меньше 150K, а W намного меньше 150K, никакое соединение не будет таким быстрым, как сравнение Trie.

Конечная сложность работы:

 N = 400 //Size of small list W = 10 // Max word Length M = 150K // Max size of the 150K lists P = 4 // Number of 150K lists P * M // To construct Trie N * P * W // To find each word in the 150k lists MP + NPW // Total complexit 

Классическая карта уменьшает проблему …. http://sist.sysu.edu.cn/~wuweig/DSCC/Inverted%20Indexing%20by%20MapReduce.pdf

  • Как заполнить несколько именованных полей, используя структурированные данные
  • Наложение imshow участков в matplotlib
  • pydata blaze: позволяет ли параллельная обработка или нет?
  • Multiprocessing.Pool делает матричное умножение Numpy медленнее
  • numpy массив индексирования строк
  • Обобщение строк в Pandas DataFrame
  • Добавление столбца нулей в csr_matrix
  • NumPy: итерация по внешнему размеру массива numpy с использованием nditer
  • Python - лучший язык программирования в мире.