Python 3 - эффективный поиск с большими списками

Question

Я делаю свой собственный ример Python, используя NLTK. CMU-dict имеет более 130 000 записей в таком формате:

[['griffon', ['G', 'R', 'IH1', 'F', 'AH0', 'N']], 
['griffy', ['G', 'R', 'IH1', 'F', 'IY0']], 
['grigas', ['G', 'R', 'AY1', 'G', 'AH0', 'Z']]] 

Это слова, слова (социации). Я манипулирую с прунами (возможно, переключись на «Г» на «Т») и проверьте, есть ли это слово. Я делаю это с помощью этой функции:

all_word_prons = get_word_pron_pairs_in_cmu_dict() 

def pron_is_a_word(pronunciation): 
    for word, pron in all_word_prons: 
     if pronunciation == pron: 
      return True 
     else: 
      return False 

all_word_prons является Python Рассол файл, который 10mb и содержит все 130K записей

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

Я сделал implment некоторое древовидную структуру, которая содержит данные, как это (используя приведенный выше пример):

{'G': {'R': {'IH1': {'F': {'IY0': {0: 'griffy'}, 'AH0': {'N': {0: 'griffon'}}}}, 'AY1': {'G': {'AH0': {'Z': {0: 'grigas'}}}}}}} 

Это по какой-то причине занимает еще больше времени, чем итерацию через него просто. Возможно, моя реализация неверна. Если вам интересно:

def build_fast_idict_tree(): 
    from nltk.corpus import cmudict 
    entries = cmudict.entries() 
    idict = {} 
    for entry in entries: 
     word, pronunciation = entry 
     idict_level = idict 
     for syl in pronunciation: 
      if syl not in idict_level: 
       idict_level[syl] = {} 
      idict_level = idict_level[syl] 
     idict_level[0] = word 
    return idict 

def get_fast_idict_tree(): 
    filename = "fast_idict_tree.pickle" 
    if os.path.isfile(filename): 
     list = pickle.load(open(filename, "rb")) 
    else: 
     list = build_fast_idict_tree() 
     pickle.dump(list, open(filename, "wb")) 
    return list 

def lookup_in_fast_idict_tree(syls): 
    idict = get_fast_idict_tree() 
    for syl in syls: 
     if syl not in idict: 
      return False 
     idict= idict[syl] 
    return idict[0] if 0 in idict else False 

TL: DR

Какой самый быстрый способ сделать этот вид поиска (соответствующий список) в Python 3 в 2015 году?

Answer 1

Считаете ли вы использование Python List Comprehensions, как описано здесь?

https://docs.python.org/3/tutorial/datastructures.html

В некоторых случаях списочные может быть быстрее, чем обычная для петель, однако он по-прежнему выполняет цикл на уровне байт-кода. Если вы не уверены, что я имею в виду, проверьте эту тему: Are list-comprehensions and functional functions faster than "for loops"?

Возможно, стоит посмотреть, будет ли это быстрее.

Answer 2

Если я правильно понял, вы хотите проверить, есть ли в вашем наборе данных pronunciation. Начиная с вашего первого блока кода, похоже, что вам небезразлично, что из word пришел матч.

Поэтому, я думаю, что мы могли бы сделать:

pron_set = {tuple(pron) for word, pron in all_word_prons} 
# do something to get a list of pronunciations to check 
for pronunciation in pronunciation_list: 
    if tuple(pronunciation) in pron_set: 
     print('pronunctiation') 

Построим pron_set из tuple потому, что list s не hashable (и не могут быть использованы в качестве элементов множества).

Установка поиска должна быть намного быстрее, чем повторение в списке. Я бы рекомендовал ознакомиться с Python data structures; вы никогда не знаете, когда deque может сэкономить вам много времени.