Самый эффективный способ поиска / поиска в огромном списке (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

Используя эту программу, похоже, что слова - это быстрые, установить секунду, список с 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

Answer 3

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

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