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

Question

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

我使用了 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

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

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

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

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

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