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

Question

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

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

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

>> if word in list: print 'word' 

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

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

Answer 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) 

Answer 2

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

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

Answer 3

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

Answer 4

Используя эту программу, она выглядит как dicts являются fastes, множество вторых, список с bi_contains третьим:

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