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

Question

请原谅我以这样一般的方式询问,因为我确信他们的表现取决于他们如何使用它们,但在我的情况下collections.deque,比collections.defaultdict我想要验证值的存在时要慢.

我使用Peter Norvig的拼写校正来验证用户对一小组单词的输入.由于我没有使用带有单词频率的字典,所以我使用了一个简单list而不是defaultdict一开始,但是deque一旦我注意到单个单词查找花了大约25秒就用它替换它.

令人惊讶的是,这并不比使用a更快,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

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

• 列表是动态数组,您可以使用它们按顺序存储项目以进行快速随机访问,用作堆栈(在末尾添加和删除)或仅存储某些内容,然后以相同的顺序迭代它.
• Deques也是序列,仅用于在两端添加和删除元素,而不是随机访问或堆栈式增长.
• 字典(提供一个相对简单和方便的默认值,但对于这个问题 - 无关的扩展)是哈希表,它们将全功能键(而不是索引)与值相关联,并通过键提供对值的快速访问并且(必然)非常快速地检查密钥存在.他们没有维持秩序,并要求钥匙可以清洗,但是,你不能在不破蛋的情况下制作煎蛋卷.

所有这些属性都很重要,无论何时选择一个都要记住它们.在这种特殊情况下破坏你的脖子的是字典的最后一个属性和必须检查的可能更正的数量的组合.一些简单的组合应该得出这个代码为给定单词生成的编辑数量的具体公式,但是每个经常错误预测这些事情的人都会知道,即使对于普通单词,它也会出乎意料地大.

对于这些编辑中的每一个,都会检查是否edit in NWORDS需要编辑导致未知单词的编辑.在Norvig的程序中没有一点问题,因为in如前所述,检查(密钥存在检查)非常快.但是你用一个序列(一个双端队列)交换了字典!对于序列,in必须迭代整个序列并将每个项目与搜索的值进行比较(它可以在找到匹配时停止,但由于编辑最少的是知道位于双端队列开头的单词,因此它通常仍会搜索所有或大多数双端队列.由于有很多单词并且对每个生成的编辑进行了测试,因此您最终会花费99%的时间在一个序列中进行线性搜索,在该序列中您可以对字符串进行散列并比较一次(或最多 - 在碰撞的情况 - 几次).

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