python - 为什么 collections.deque 比 collections.defaultdict 慢？

Question

请原谅我以如此笼统的方式询问，因为我确信它们的性能取决于人们如何使用它们，但在我的情况下，collections.deque 比 collections 慢得多.defaultdict 当我想验证一个值的存在时。

我使用了 spelling correction from Peter Norvig为了根据一小组单词验证用户的输入。由于我没有使用带有词频的字典，所以我一开始使用了一个简单的 list 而不是 defaultdict，但很快用 deque 代替了它因为我注意到单个单词查找大约需要 25 秒。

令人惊讶的是，这并不比使用 list 快，所以我重新使用 defaultdict，它几乎可以立即返回结果。

有人可以向我解释这种性能差异吗？

提前致谢

---

PS:如果你们中有人想重现我所说的内容，请更改 Norvig 脚本中的以下行。

-NWORDS = train(words(file('big.txt').read()))
+NWORDS = collections.deque(words(file('big.txt').read()))

-return max(candidates, key=NWORDS.get)
+return candidates

Answer 1

这三种数据结构不可互换，它们用于非常不同的目的并且具有非常不同的特征:

• 列表是动态数组，您可以使用它们按顺序存储项目以实现快速随机访问、用作堆栈(在末尾添加和删除)或仅存储一些内容然后以相同的顺序对其进行迭代。
• 双端队列也是序列，仅用于在两端添加和删除元素，而不是随机访问或类似堆栈的增长。
• 字典(提供一个默认值只是一个相对简单和方便，但 - 对于这个问题 - 不相关的扩展)是哈希表，它们将功能齐全的键(而不是索引)与值相关联并提供对值的非常快速的访问通过 key 和(必然)非常快速地检查 key 是否存在。他们不维护秩序并要求 key 是可散列的，但是好吧，你不能不打破鸡蛋就做煎蛋。

所有这些属性都很重要，当您选择一个而不是另一个时，请记住它们。在这种特殊情况下，让你头疼的是字典的最后一个属性和必须检查的可能更正数量的组合。一些简单的组合应该得出一个具体的公式，用于计算此代码为给定单词生成的编辑次数，但每个经常错误预测此类事情的人都会知道，即使对于普通单词，它也会大得惊人。

对于这些编辑中的每一个，都有一个检查 edit in NWORDS 以清除导致未知单词的编辑。 Norvig 的程序中没有一点问题，因为如前所述，in 检查( key 存在性检查)非常快。但是你用一个序列(双端队列)交换了字典!对于序列，in 必须遍历整个序列并将每个项目与搜索的值进行比较(它可以在找到匹配项时停止，但由于最少的编辑是位于序列开头的已知单词双端队列，它通常仍然搜索所有或大部分双端队列)。由于有相当多的单词并且对生成的每个编辑都进行了测试，因此您最终会花费 99% 的时间在一个序列中进行线性搜索，您可以只对字符串进行哈希处理并比较一次(或最多 - 在发生碰撞的情况 - 几次)。

如果您不需要权重，您可以在概念上使用您从未查看过的虚假值，并且仍然可以获得 O(1) in 检查的性能提升。实际上，你应该只使用一个 set ，它使用与字典几乎相同的算法，只是切掉它存储值的部分(它实际上首先是这样实现的，我不知道自从集合在专用的、单独的 C 模块中重新实现以来，这两者有多大差异)。