Python 3: 自动补全算法的速度/效率改进

Question

我用Python3.6编写了一些代码来自动完成用户输入的（部分）单词。我的目标是使自动完成部分尽可能快/高效地运行，以此来发展我的编程技能和更好地理解Python。我限制自己使用标准库，只是因为我想探索使用这样一个约束可以实现什么。在

代码的第一部分是一个函数def load_wordfile，它加载一个.txt文件并创建一个单词列表，同时对单词进行小写和清理。我试着用列表理解和string.punctuation来加速这个过程，尽管这不是我的主要关注点。在

import string
from collections import Counter

def load_wordfile(filename):

    with open(filename, encoding='utf8') as f:

        # List comprehension and string.punctuation for efficiency and speed improvements
        return [word.strip(string.punctuation) for line in f for word in line.lower().split()]

在实例化期间，单词列表被传递给一个类AutoCompleter。在这个类中，一个方法complete实际执行自动完成。我希望自动完成的结果是元组列表，其中元组中的第一个值是匹配的单词，第二个值是单词出现的相对频率（在.txt中）。返回的元组列表应按频率降序排列。我知道Counter对这个很好，所以我利用了它。在

^{pr2}$

在第一次尝试的基础上，我设法在执行速度方面做了很大的改进，这导致了您在上面看到的代码。在

然而，我相信complete仍然可以改进。为了证明我现在所处的位置，我对NLTK英语单词语料库complete进行了基准测试，认为这是需要搜索匹配项的列表大小的一个很好的“上限”。在

from nltk.corpus import words

# words.words() is a list of over 250,000 unique English words
cmp = AutoCompleter(words.words())
pattern = 'do'

%timeit -n 100 cmp.complete(pattern)

时间的结果是：

41.6 ms ± 898 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)

从广泛的研究中，我认为我可以使用某种二进制搜索或bisect来加快根据用户输入的匹配（部分）单词的搜索速度。或者用不同的结构将输入输入到complete中，找到匹配单词的索引，然后从不同的列表中提取频率，最后将两者一起输出。在

我也有一个想法，就是用户输入“a”，那么我应该只关注以“a”开头的单词，而不是传递列表中的每个单词。不过，现在我有点搞不清楚如何最好地实现这一点。我也研究了堆栈溢出，这在其他方面也有帮助，但我还没有完全把所有的部分组合起来，以获得最终的性能提升。在

非常感谢你的帮助和建议。谢谢您！在