Самый эффективный способ поиска / поиска в огромном списке (python)

– Я просто разбирал большой файл, и я создал список, содержащий 42 000 строк / слов. Я хочу запросить [против этого списка], чтобы проверить, принадлежит ли ему данное слово / строка. Поэтому мой вопрос:

Каков наиболее эффективный способ для такого поиска?

Первый подход заключается в сортировке списка ( list.sort() ), а затем просто используйте

 >> if word in list: print 'word' 

что действительно тривиально, и я уверен, что есть лучший способ сделать это. Моя цель – применить быстрый поиск, который определяет, находится ли данная строка в этом списке или нет. Если у вас есть идеи другой структуры данных, они приветствуются. Тем не менее, я хочу избежать более сложных структур данных, таких как Tries и т. Д. Мне интересно услышать идеи (или трюки) о быстрых поисках или любых других методах библиотеки python, которые могли бы выполнять поиск быстрее, чем простой.

А также я хочу знать индекс элемента поиска

4 Solutions collect form web for “Самый эффективный способ поиска / поиска в огромном списке (python)”

Не создавайте list , создавайте set . Он выполняет поиск в постоянное время.

Если вы не хотите накладных расходов на память набора, сохраните отсортированный список и выполните поиск через него с помощью модуля bisect .

 from bisect import bisect_left def bi_contains(lst, item): """ efficient `item in lst` for sorted lists """ # if item is larger than the last its not in the list, but the bisect would # find `len(lst)` as the index to insert, so check that first. Else, if the # item is in the list then it has to be at index bisect_left(lst, item) return (item <= lst[-1]) and (lst[bisect_left(lst, item)] == item) 

Пункт о наборах против списков, которые не были рассмотрены: в «синтаксическом анализе большого файла» можно было бы ожидать обработки повторяющихся слов / строк. Вы не упомянули об этом вообще.

Очевидно, что добавление новых слов в набор удаляет дубликаты «на лету» без каких-либо дополнительных затрат времени процессора или вашего времени на размышление. Если вы попробуете это со списком, оно заканчивается O (N ** 2). Если вы добавите все в список и удалите дубликаты в конце, самым умным способом сделать это будет … барабанный ролл … используйте набор, и преимущество (малая) памяти в списке, вероятно, будет перегружено дубликаты.

Используя эту программу, похоже, что dicts – это посты, второй – список с bi_contains third:

 from datetime import datetime def ReadWordList(): """ Loop through each line in english.txt and add it to the list in uppercase. Returns: Returns array with all the words in english.txt. """ l_words = [] with open(r'c:\english.txt', 'r') as f_in: for line in f_in: line = line.strip().upper() l_words.append(line) return l_words # Loop through each line in english.txt and add it to the l_words list in uppercase. l_words = ReadWordList() l_words = {key: None for key in l_words} #l_words = set(l_words) #l_words = tuple(l_words) t1 = datetime.now() for i in range(10000): #w = 'ZEBRA' in l_words w = bi_contains(l_words, 'ZEBRA') t2 = datetime.now() print('After: ' + str(t2 - t1)) # list = 41.025293 seconds # dict = 0.001488 seconds # set = 0.001499 seconds # tuple = 38.975805 seconds # list with bi_contains = 0.014000 seconds 

Если вы ожидаете сложных поисков позже – и сложным я имею в виду не тривиальным – я рекомендую вам хранить его в sqlite3 .

Python - лучший язык программирования в мире.