我需要能够快速检查字典中是否有给定的单词（英语单词列表）。我只关心检查成员资格的速度（不添加或删除元素），并且内存使用并不是真正的问题。
最初我使用的是这样的集合：
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会只节省内存，而不节省计算量吗？
非常感谢！
最佳答案
我认为如果将DAWG用作一组替代产品，它并不会节省您的CPU周期。
关于集合大小，集合查找为O（1），关于DAWG项目计数，DAWG查找也为O（1）。关于查找密钥长度，DAWG查找为O（N）（当密钥位于DAWG中时，有len（key）个步骤需要检查密钥是否位于DAWG中）。关于密钥长度的集合查找也是O（N）（因为必须计算密钥的哈希值）。因此，这归结为实施，
哈希图通常比其他数据结构（包括DAWG和Tries）要快；
Python集已经过优化。内置类型的哈希计算也得到了优化； CPython中的set / dicts具有用于unicode键的专用代码路径。
当项目不在DAWG中时，DAWG可能有一个优势，因为它需要少于len（key）个步骤来检查此项目，并计算哈希值，始终需要len（key）个步骤（好吧，如果未缓存哈希值）。但是即使在这种情况下，也很难击败内置设备。
一个无耻的插件-您也可以尝试https://pypi.python.org/pypi/DAWG-但__contains__仍然比dict慢2倍。
顺便说一句，pyDAWG Python版本的word2index在内部执行了许多dict查找，因此它不会比单个集合查找更快。
关于python - 设置vs DAWG以检查Python中字典的成员资格，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/14953779/