Python中最快的方法是在长排序的字符串列表中查找"startswith"子字符串

Question

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

我正在编写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:
In total, Peter's simple test took 0.175472736359
In total, Peter's bisect left test took 9.36985015869e-05
In total, the list comprehension took 0.0499348640442
In total, Neil G's bisect took 0.000373601913452

创建第二个列表等的开销显然比搜索更长的列表花费更多的时间.事后看来,这可能是最好的方法,因为"减少列表"方法增加了第一次运行的时间,这是最糟糕的情况.

感谢所有一些很好的建议,以及彼得最好的答案!

Answer 1

生成器表达式是懒惰地评估的,所以如果你只需要确定你的单词是否有效,我希望以下更有效,因为它不一定强制它在找到匹配后构建完整列表:

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

请注意,缺少方括号对于此工作非常重要.

然而,在最坏的情况下,这显然仍是线性的.你是正确的,二元搜索会更有效率; 你可以使用内置bisect模块.它可能看起来像这样:

from bisect import bisect_left
def word_exists(wordlist, word_fragment):
    try:
        return wordlist[bisect_left(wordlist, word_fragment)].startswith(word_fragment)
    except IndexError:
        return False # word_fragment is greater than all entries in wordlist

bisect_left 在O(log(n))中运行,因此对于大型单词列表来说要快得多.

编辑:如果你的word_fragment是真正常见的东西(比如't'),我猜想你给出的例子会丢失,在这种情况下,它可能花费大部分时间来组装一大堆有效单词,并且只获得了对列表进行部分扫描可以忽略不计.很难说肯定,但它有点学术,因为无论如何二进制搜索更好.