python3:自动完成算法的速度/效率改进

2021-02-25 04:23:07 发布

您现在位置:Python中文网/ 问答频道 /正文

我用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”开头的单词,而不是传递列表中的每个单词。不过,现在我有点搞不清楚如何最好地实现这一点。我也研究了堆栈溢出,这在其他方面也有帮助,但我还没有完全把所有的部分组合起来,以获得最终的性能提升。在

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