python - Set 与 DAWG 在 Python 中检查字典中的成员资格

Question

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

最初我使用的是这样的一套:

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

我的程序花费了大约。在测试输入上运行 4 秒。然后，我尝试使用 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 周期。

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

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

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

无耻插件-你也可以给https://pypi.python.org/pypi/DAWG尝试一下 - 但 __contains__ 仍然比 dict 慢大约 2 倍。

顺便说一句，pyDAWG Python 版本的 word2index 在内部进行许多字典查找，因此它不会比单个集合查找更快。