1

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

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

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 会只节省内存而不是计算吗？

非常感谢！

4

2 回答 2

1

我认为如果您将 DAWG 用作套件替代品，它不会为您节省 CPU 周期。

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

  • hashmaps 通常比其他数据结构（包括 DAWG 和 Tries）更快；
  • Python set 优化得很好；内置类型的哈希计算也得到了优化；CPython 中的 set/dicts 具有用于 unicode 键的专用代码路径。

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

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

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

于 2013-03-01T13:30:18.770 回答
0

word2index通过调用听起来您不需要的方法，您正在使用完美的散列功能。你为什么不exists改用？

于 2013-02-19T09:45:41.277 回答