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

Question

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

我正在编写 Ghost 的实现对于 MIT Introduction to Programming, assignment 5 .

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

更新:我可以使用每次迭代列表的东西，例如彼得的简单建议:

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

(来自 here )将列表缩小到以该片段开头的有效单词列表，如果 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

但速度差不多，我认为这可能是因为列表推导作为编译代码运行？

然后我认为更有效的方法是在列表中进行某种形式的二分搜索以找到匹配的单词 block 。这是要走的路，还是我错过了一些非常明显的东西？

显然，在这种情况下，这并不是什么大问题，但我刚刚开始编程，想要正确地做事。

更新:

我已经用 simple test script 测试了以下建议.虽然彼得的二分搜索/二分法显然更适合单次运行，但我对缩小列表是否会赢得一系列片段感兴趣。事实上，它没有:

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”)，我猜您给出的示例会丢失，在这种情况下，它可能会花费大部分时间来组装大量有效单词，并且获得只需对列表进行部分扫描可以忽略不计。很难确定，但它有点学术，因为无论如何二进制搜索更好。