python3高效的大列表查找

Question

我正在用NLTK制作我自己的Rymer is Python。CMU dict有超过130000个条目，格式如下：

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

这些是单词，发音（发音）对。我操纵叉（可能把“G”换成“T”）并检查这是否是一个单词。我使用以下函数：

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\u word\u prons是一个10mb的Python Pickle文件，包含所有130k个条目

如果我执行这个查找1000次，大约需要23秒，考虑到这个任务，这不是很糟糕，但必须有一个更好的算法。我见过有人在其他主题上推荐对分集合，但这些集合适用于简单的字符串查找。这或多或少是检查列表是否相等，而不是字符串。你知道吗

我确实实现了一些树状结构，其中包含这样的数据（使用上面的示例）：

{'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:博士

2015年，在python3中进行这种查找（匹配列表）的最快方法是什么？你知道吗

Answer 1

如果我理解正确，您需要检查数据集中是否有pronunciation。从您的第一个代码块开始，您似乎并不关心匹配来自何处。你知道吗

因此，我认为我们可以：

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')

我们从tuple构造pron_set，因为list是不可散列的（不能用作集成员）。你知道吗

集合查找应该比遍历列表快得多。我建议您熟悉Python data structures；您永远不知道什么时候deque会为您节省大量时间。你知道吗

Answer 2

您是否考虑过使用这里概述的Python列表理解？你知道吗

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

在某些情况下，列表理解可能比普通for循环快，但是它仍然执行字节码级别的循环。如果你不确定我的意思，请检查以下线程： Are list-comprehensions and functional functions faster than "for loops"?

也许值得一试，看看这是否会更快。你知道吗