Самый эффективный способ поиска/поиска в огромном списке (python)
- Я просто разбирал большой файл, и я создал список, содержащий 42 000 строк/слов. Я хочу запросить [против этого списка], чтобы проверить, принадлежит ли ему данное слово/строка. Поэтому мой вопрос:
Каков наиболее эффективный способ для такого поиска?
Первый подход заключается в сортировке списка (list.sort()), а затем просто используйте
>> if word in list: print 'word'
что действительно тривиально, и я уверен, что есть лучший способ сделать это. Моя цель - применить быстрый поиск, который определяет, находится ли данная строка в этом списке или нет. Если у вас есть идеи другой структуры данных, они приветствуются. Тем не менее, я хочу избежать более сложных структур данных, таких как Tries и т.д. Мне интересно услышать идеи (или трюки) о быстрых поисках или любых других методах библиотеки python, которые могли бы выполнять поиск быстрее, чем простой in.
А также я хочу знать индекс элемента поиска
Ответы
Ответ 1
Не создавайте 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)
Ответ 2
Точка о наборах против списков, которые не были рассмотрены: в "синтаксическом анализе большого файла" можно было бы ожидать обработки дубликатов слов/строк. Вы не упомянули об этом вообще.
Очевидно, что добавление новых слов в набор удаляет дубликаты "на лету" без каких-либо дополнительных затрат на процессорное время или время вашего размышления. Если вы попробуете это со списком, оно заканчивается O (N ** 2). Если вы добавите все в список и удалите дубликаты в конце, самым умным способом сделать это будет... барабанный ролл... используйте набор, и преимущество (малая) памяти в списке, вероятно, будет перегружено дубликаты.
Ответ 3
Используя эту программу, похоже, что 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
Ответ 4
Если вы ожидаете сложных поисков позже - и сложным я имею в виду не тривиальным - я рекомендую вам сохранить его в sqlite3.
