为什么collections.deque比collections.defaultdict慢？
请原谅我用这么笼统的方式提问，因为我知道它们的性能可能会根据使用方式的不同而有所不同。但就我个人的情况来看，collections.deque在验证一个值是否存在时，速度远远慢于collections.defaultdict。
我使用了Peter Norvig的拼写纠正来检查用户输入是否在一个小的单词集合中。因为我不需要一个包含单词频率的字典，所以一开始我用的是简单的list，但当我发现查找一个单词要花大约25秒时，我就把它换成了deque。
令人惊讶的是，使用deque的速度并没有比list快，所以我又回到了使用defaultdict，它几乎能立即返回结果。
有人能给我解释一下这种性能差异吗？
提前谢谢你们！
附言：如果你们想重现我所说的情况，可以在Norvig的脚本中修改以下几行。
-NWORDS = train(words(file('big.txt').read()))
+NWORDS = collections.deque(words(file('big.txt').read()))
-return max(candidates, key=NWORDS.get)
+return candidates
1 个回答
这三种数据结构是不能互换的，它们的用途和特点都很不同：
- 列表是一种动态数组，你可以用它来顺序存储项目，方便快速随机访问，或者当作栈使用（在末尾添加和删除），也可以用来存储一些东西，之后按顺序遍历它。
- 双端队列也是一种序列，但它主要用于在两端添加和删除元素，而不是随机访问或像栈那样增长。
- 字典（提供默认值只是一个相对简单方便的扩展，但对于这个问题来说不太相关）是哈希表，它把完整的键（而不是索引）和对应的值关联起来，能通过键快速访问值，并且能快速检查键是否存在。字典不保持顺序，并且要求键是可哈希的，不过，想要做出煎蛋卷总得打破几个鸡蛋。
这些特性都很重要，选择时要记住它们。这里面最麻烦的是字典的最后一个特性和需要检查的可能修正数量的结合。简单的组合数学可以得出这个代码对给定单词生成的编辑次数的具体公式，但那些经常错误预测这种事情的人会知道，即使是普通单词，这个数字也会出乎意料地大。
对于每一个编辑，都有一个检查edit in NWORDS，用来排除那些生成未知单词的编辑。这在Norvig的程序中不是问题，因为in检查（键存在性检查）是非常快速的。但你把字典换成了序列（双端队列）！对于序列，in需要遍历整个序列，并将每个项目与要查找的值进行比较（虽然找到匹配项后可以停止，但由于最少的编辑通常是位于双端队列开头的已知单词，所以它通常还是会搜索整个或大部分双端队列）。由于单词数量相当多，并且每个生成的编辑都要进行测试，你最终会花费99%的时间在一个线性搜索上，而不是直接哈希一个字符串并比较一次（或者在碰撞的情况下最多比较几次）。
如果你不需要权重，可以概念上使用一些你从不查看的虚假值，依然能获得O(1)的in检查性能提升。实际上，你应该使用一个set，它使用的算法和字典几乎一样，只是去掉了存储值的部分（最初就是这样实现的，我不知道自从集合在一个专门的C模块中重新实现后，两者有多大差异）。