小编Hoo*_*voo的帖子

我做了很多谷歌搜索,但没有找到任何东西,所以如果我只是在寻找错误的东西,我真的很抱歉.

我正在编写Ghost实现MIT编程简介,作业5.

作为其中的一部分,我需要确定一串字符是否是任何有效单词的开头.我有一个有效单词列表("wordlist").

更新:我可以使用每次遍历列表的内容,例如Peter的简单建议:

def word_exists(wordlist, word_fragment):
return any(w.startswith(word_fragment) for w in wordlist)

我以前有:

wordlist = [w for w in wordlist if w.startswith(word_fragment)]

(从这里开始)将列表缩小到以该片段开头的有效单词列表,如果wordlist为空,则将其视为丢失.我采用这种方法的原因是我(错误地,见下文)认为这将节省时间,因为后续查找只需搜索较小的列表.

在我看来,这是通过原始词汇表中的每个项目(38,000个单词)检查每个项目的开始.当wordlist被排序时,这似乎很愚蠢,一旦它击中单词片段之后的某些内容,理解就会停止.我试过这个:

newlist = []
for w in wordlist:
    if w[:len(word_fragment)] > word_fragment:
        # Take advantage of the fact that the list is sorted
        break
    if w.startswith(word_fragment):
        newlist.append(w)
return newlist

但是这个速度大致相同,我认为可能是因为列表推导作为编译代码运行？

然后我认为再次更高效的是列表中的某种形式的二进制搜索,以找到匹配单词的块.这是要走的路,还是我错过了一些非常明显的东西？

显然,在这种情况下,这并不是什么大不了的事,但我刚刚开始编程并且想要正确地做事.

更新:

我已经用简单的测试脚本测试了以下建议.虽然Peter的二分搜索/ bisect显然会更好地进行单次运行,但我对缩小列表是否会胜过一系列片段感兴趣.事实上,它没有:

The totals for all strings "p", "py", "pyt", "pyth", "pytho" are as follows: …