在Python中使用集合还是DAWG检查字典中的成员资格
我需要快速检查一个给定的单词是否在我的字典（英语单词列表）中。我只关心检查单词是否存在的速度（不考虑添加或删除元素），而且内存使用不是问题。
最开始我使用了一个集合，像这样：
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是否只是节省内存，而不节省计算时间？
非常感谢！
2 个回答
你正在使用完美哈希功能，通过调用 word2index，但听起来你其实不需要这个。那为什么不直接用 exists 呢？
我觉得如果你把DAWG当作集合来用，它并不会帮你节省CPU的运算时间。
查找集合的时间复杂度是O(1)，这意味着不管集合有多大，查找的时间都是固定的。而查找DAWG的时间复杂度也是O(1)，但这只针对DAWG里的项目数量来说。如果你要查找的键的长度是N，那么查找DAWG的时间复杂度就是O(N)，因为你需要检查N次才能确认这个键是否在DAWG里。查找集合也是一样，查找的时间复杂度是O(N)，因为你需要计算这个键的哈希值。所以这就看具体的实现了，
- 哈希表通常比其他数据结构（包括DAWG和Trie树）要快；
- Python的集合经过了很好的优化；内置类型的哈希计算也进行了优化；在CPython中，集合和字典对于unicode键有专门的处理方式。
当某个项目不在DAWG里时，DAWG可能会有优势，因为检查这个情况所需的步骤会少于键的长度，而计算哈希值时总是需要len(key)步（当然，如果哈希值没有被缓存的话）。但即使在这种情况下，内置的集合也很难被超越。
顺便提一下，你可以试试这个链接 https://pypi.python.org/pypi/DAWG，不过 __contains__ 的速度还是比字典慢大约两倍。
另外，pyDAWG这个Python版本的word2index在内部做了很多字典查找，所以它的速度不可能比单次集合查找快。