Проверить слово в очень большом списке

Question

Если у меня есть список из 10 000 слов, то какой оптимизированный способ проверить, есть ли в этом списке слово, которое не замедлит приложение до обхода?

Должен ли я загружать слова из файла и проверять на это?

def check_for_word(word): 
    HUGE_LIST = [...] # 10,000 Words 
    if word in HUGE_LIST: 
     return True 
    else: 
     return False 

Answer 1

Преобразовать список для установки - строки hashable так набор может быть легко созданы.

Look-up in set - O (1), где для списка O (n), где n - длина списка.

HUGE_SET = set(HUGE_LIST) # or frozenset, if it's constant and words won't be added to it 
return word in HUGE_SET 

Кроме того, рассмотрите возможность перемещения огромного списка и огромного набора вне тела функции. Прямо сейчас список воссоздается каждый раз, когда вызывается функция.

Список тайминги:

$ python -m timeit -s "words = list(map(str, xrange(10000)))" -n 10000 "'5000' in words" 
10000 loops, best of 3: 58.2 usec per loop 

Frozenset тайминги:

$ python -m timeit -s "words = frozenset(map(str, xrange(10000)))" -n 10000 "'5000' in words" 
10000 loops, best of 3: 0.0504 usec per loop 

Answer 2

• Если вы не будете делать какие-либо изменения в списке, используйте tuple вместо списка.

• Если элементы в списке уникальны, то лучше использовать set.

Поиск будет быстрее с кортежем/компл по сравнению для поиска в списке

Answer 3

Прочитайте слова из файла и превратить их в set слов. Проверка членства в наборе очень быстрая (и 10 000 не «очень большие» :-)).

with open('words.txt') as words: 
    wordset = {word.strip() for word in words} 

return word in wordset 

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

Answer 4

вы можете взять немного косвенный путь, написав функцию, что данный файл, содержащий все слова, возвращает функцию для проверки членства в

def make_checker(fname): 
    with open(fname) as f: 
     # Hp: one word per line, you can adjust the code for a different format 
     # this line builds a set by a _set comprehension_ 
     words = {word.strip() for word in f} 
    def the_checker(word): 
     return word in words 
    return the_checker 

что вы можете использовать, как это

check_4 = make_checker('corpus_of_4_letter_words.txt') 
... 
if check_4(answer.strip()): 
    print('Please, please do not use these words.')