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