在Python中为检查字典中的成员身份设置vs DAWG

Question

我需要能够快速检查一个给定的单词是否在我的字典(英语单词列表)中。我只关心检查成员的速度(不添加或删除元素)，内存使用并不是真正的问题。

最初我使用的是这样的集合：

words = set(x.strip().lower() for x in open("/usr/share/dict/words").readlines())
if(word in words):
    ...

我的程序大约用了。4s以在测试输入上运行。然后，我尝试通过使用DAWG (http://pypi.python.org/pypi/pyDAWG)来优化事情，而不是通过预先计算DAWG并对其进行酸洗：

words = pickle.load(open('wordlistDAWG.pyd'))
if(words.word2index(word) is not None):
    ...

在相同的测试输入上，程序运行了大约40秒(包括几秒钟来加载DAWG，这我并不关心)。我希望使用DAWG可以让事情运行得更快！

也许我没有理解python是如何散列的-一个集合已经是我能得到的最好的(O(1)成员资格测试了吗？)而不是DAWG或者Trie？DAWG只会节省内存而不会节省计算吗？

非常感谢！

Answer 1

我认为DAWG不会为你节省CPU周期，如果你使用它作为set的替代品。

集合查找对于集合大小是O(1)，DAWG查找对于DAWG项目计数也是O(1)。DAWG查找对于查找密钥长度是O(N) (当密钥在DAWG中时，需要len(密钥)步骤来检查密钥是否在DAWG中)。Set lookup对于密钥长度也是O(N) (因为必须计算密钥的散列)。所以这归结为实现，并且

• 哈希图通常比其他数据结构(包括DAWG和Tries)更快；
• Python得到了很好的优化；内置类型的哈希计算也得到了优化；CPython中的集合/字典具有专门的Unicode键代码路径。

当项目不在DAWG中时，DAWG可能具有优势，因为它需要少于len(键)步骤来检查这一点，并且总是需要计算hash len(键)步骤(好吧，如果hash值没有被缓存)。但即使在这种情况下，也很难击败内置的set。

一个无耻的插件--你也可以试一试https://pypi.python.org/pypi/DAWG --但是__contains__仍然比dict慢2倍。

顺便说一句，word2index的pyDAWG Python版本在内部执行了许多字典查找，所以它的速度不会比单个集合查找快。

Answer 2

您通过调用word2index来使用完美的散列功能，而这听起来您并不需要。为什么不使用exists呢？