Python在单词集检查包中

Question

我有一个文本处理脚本，需要检查一个词是否在一个词袋。我要做很多次。我认为最有效的方法是定义我正在检查的单词集，然后执行if word in wordBag:。我看了文档，这是平均情况O（1）和最坏情况O（n）。这仅仅是因为hashset中的链接吗？有没有更像Python的方法？你知道吗

Answer 1

这真的取决于你的词集的大小。对于任何非巨量（可能高达数万）你的方法是绝对罚款和完全Python。简单是一种美德！你知道吗

如果您的包中有大量的单词，那么prefix-tree（或“trie”）方法可能是最好的方法，因为您可以检查PyPI的现有实现（example）。你知道吗

编辑：最坏的情况只发生在您怀疑的大量哈希冲突的情况下，但实际上这通常不是问题。在任何情况下，我都会先使用最简单的方法，如果您确实有性能或内存问题，只会查看更高级的解决方案。你知道吗