2

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

我使用了来自 Peter Norvig 的拼写更正，以便根据一小组单词验证用户的输入。由于我没有使用带有词频的字典，所以我一开始使用了简单list的而不是，但当我注意到单个单词查找大约需要 25 秒时，就将defaultdict其替换为。deque

令人惊讶的是，这并不比使用 a 快，list所以我几乎立即返回使用defaultdictwhich 返回的结果。

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

提前致谢

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
4

1 回答 1

10

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

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

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

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

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

于 2011-08-04T08:16:47.843 回答