Наиболее эффективный способ определить, содержит ли большой список определенную строку (Python)

Question

У меня есть файл, содержащий почти все слова на английском языке (~ 60 тыс. Слов, ~ 500 тыс. Символов). Я хочу проверить, является ли определенное слово, которое я получаю в качестве ввода, "на английском" (т. Е. Находится ли это точное слово в списке).

Какой самый эффективный способ сделать это в Python?

Тривиальное решение - загрузить файл в список и проверить, есть ли слово в этом списке. Список может быть отсортирован, что, я считаю, сократит сложность до O (logn). Однако я не уверен, как Python реализует поиск по спискам, и есть ли снижение производительности, если такой большой список находится в памяти. Могу ли я «оскорбить» тот факт, что могу ограничить длину слов? (например, скажем, самый длинный - 15 символов).

Обратите внимание, что я запускаю приложение на компьютере с большим объемом памяти, поэтому меня меньше заботит потребление памяти, чем скорость и загрузка ЦП.

Спасибо

Answer 1

Python Set - это то, что вы должны попробовать.

Объект set - это неупорядоченная коллекция различных объектов hashable. Обычное использование включает тестирование принадлежности , удаление дубликатов из последовательности и вычисление математических операций, таких как пересечение, объединение, разность и симметричная разность.

Answer 2

Пример кода Python:

L = ['foo', 'bar', 'baz'] # Your list
s = set(L)  # Converted to Set

print 'foo'  in s # True
print 'blah' in s # False

Answer 3

A Trie структура будет соответствовать вашим целям. Несомненно, есть реализации Python, которые можно найти там ...

Answer 4

Другие дали вам способ в памяти, используя set (), и это, как правило, будет самым быстрым способом, и не должны облагаться налогом вашей памяти для набора данных из 60 тыс. Слов (максимум несколько МБ). Вы должны быть в состоянии построить свой набор с:

f=open('words.txt')
s = set(word.strip() for word in f)

Однако для загрузки набора в память требуется некоторое время. Если вы проверяете много слов, это не проблема - время поиска более чем компенсирует это. Однако, если вы собираетесь проверять только одно слово на выполнение команды (например, это приложение командной строки, например, «checkenglish [word]»), время запуска будет больше, чем потребовалось бы вам, чтобы просто выполнить поиск по строке файла. по линии.

Если это ваша ситуация или у вас гораздо больший набор данных, лучше использовать формат на диске. Самый простой способ - использовать модуль dbm . Создайте такую ​​базу данных из списка слов с помощью:

import dbm
f=open('wordlist.txt')
db = dbm.open('words.db','c')
for word in f:
    db[word] = '1'
f.close()
db.close()

Тогда ваша программа может проверить членство с помощью:

db = dbm.open('words.db','r')
if db.has_key(word):
    print "%s is english" % word
else:
    print "%s is not english" % word

Это будет медленнее, чем поиск по набору, так как будет доступ к диску, но будет быстрее, чем поиск, с низким использованием памяти и без значительного времени инициализации.

Существуют и другие альтернативы, такие как использование базы данных SQL (например, sqlite).

Answer 5

Две вещи:

Тип Python 'mutable set' имеет метод add (s.add (item)), так что вы можете сразу перейти от чтения (строки) из вашего большого файла прямо к набору, не используя список в качестве промежуточная структура данных.

Python позволяет вам «выбрать» структуру данных, чтобы вы могли сохранить свой большой набор в файл и сэкономить время повторного запуска набора.

Во-вторых, я искал список всех односложных слов на английском языке для собственного удовольствия, но те, которые я нашел, кажутся проприетарными. Если это не навязчиво, могу ли я спросить, могут ли другие получить ваш список английских слов?

Answer 6

500k символов не большой список. если элементы в вашем списке уникальны, и вам нужно выполнять этот поиск несколько раз, используйте set, что снизит сложность до O(1) в лучшем случае.

Answer 7

Если потребление памяти не является проблемой и слова не изменятся, самый быстрый способ сделать это - поместить все в хеш и искать таким образом В Python это Set. У вас будет постоянный поиск.

Answer 8

Вы в основном проверяете, входит ли участник в сет или нет, верно?

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

Или используйте ту структуру данных, которая используется bash для автозаполнения имен команд - это быстро и очень эффективно в памяти (не помню имени).

Answer 9

Преобразование списка в набор будет полезно только в том случае, если вы неоднократно запускаете этот тип запроса к данным, как это происходит при сортировке списка и выполнении бинарного поиска. Если вы собираетесь извлечь данные из списка только один раз, лучшим выбором будет простой старый линейный поиск:

if 'foo' in some_list:
    do_something()

В противном случае вам лучше всего использовать набор, как уже упоминалось, или бинарный поиск. Какой из них выбрать, во многом зависит от объема данных и объема памяти, который вы можете сэкономить. Мне говорят, что действительно большие списки, как правило, получают больше пользы от хэширования, хотя объем занимаемой памяти может быть чрезмерно дорогим.

Наконец, третий вариант заключается в том, что вы можете импортировать данные в базу данных sqlite и читать непосредственно из нее. Sqlite очень быстрый и может избавить вас от необходимости загружать список целом из файла. Python имеет очень хорошую встроенную библиотеку sqlite .