是否在Python 3.6中订购了字典？

3 回答

• 58

  以下是回答原始的第一个问题：

  我应该在Python 3.6中使用dict还是OrderedDict？

  我认为文档中的这句话实际上足以回答你的问题

  此新实现的顺序保留方面被视为实现细节，不应依赖

  dict 并未明确指定为有序集合，因此如果您希望保持一致并且不依赖于新实现的副作用，则应该坚持使用 OrderedDict .

  让您的代码面向未来:)

  有关于here的辩论 .

  编辑： Python 3.7 will keep this as a feature see

  回复于 2024-04-29T01:42:44+08:00
• 265

  是否在Python 3.6中订购了词典？

  他们是 insertion ordered [1] . 从Python 3.6开始，对于Python的CPython实现，字典记住了插入项的顺序 . 这被认为是Python 3.6中的实现细节;如果你想要在其他Python实现（和其他有序行为[1]）中保证插入排序，你需要使用 OrderedDict .

  As of Python 3.7 ，这不再是实现细节，而是成为语言功能 . From a python-dev message by GvR：

  这样做 . “Dict保持插入秩序”是裁决 . 谢谢！

  这只是意味着你可以依赖它 . Python的其他实现还必须提供插入有序字典，如果他们希望成为Python 3.7的一致性实现 .

  ---

  在保留元素顺序的同时，Python 3.6字典实现如何比旧版本更好[2]？

  基本上，通过保留两个数组 .

  • 第一个数组dk_entries按照插入顺序保存字典的条目（of type PyDictKeyEntry） . 保留顺序是通过这是一个仅附加数组来实现的，其中总是在末尾插入新项目（插入顺序） .

  • 第二个dk_indices，保存 dk_entries 数组的索引（即表示 dk_entries 中相应条目位置的值） . 此数组充当哈希表 . 当一个键被散列时，它会导致存储在 dk_indices 中的一个索引，并通过索引 dk_entries 来获取相应的条目 . 由于只保留索引，因此该数组的类型取决于字典的整体大小（范围从int8_t（ 1 字节）到int32_t / int64_t（ 4 / 8 字节） 32 / 64 位构建）

  在前面的实现中，必须分配类型为 PyDictKeyEntry 且大小为 dk_size 的稀疏数组;不幸的是，它也导致了很多空的空间，因为该数组不允许超过 2/3 * dk_size 完整for performance reasons . （而空的空间仍然有 PyDictKeyEntry 大小！） .

  现在情况并非如此，因为只存储了所需的条目（已插入的条目）和类型为 intX_t 的稀疏数组（ X ，具体取决于字典大小） 2/3 * dk_size 已满 . 空白区域从类型 PyDictKeyEntry 更改为 intX_t .

  因此，显然，创建一个类型为 PyDictKeyEntry 的稀疏数组比用于存储 int 的稀疏数组要多得多 .

  如果感兴趣，你可以看到有关此功能的完整对话on Python-Dev，这是一个很好的阅读 .

  ---

  In the original proposal made by Raymond Hettinger，可以看到所使用的数据结构的可视化，其捕获了该想法的要点 .

  例如，字典：d = {'timmy'：'red'，'barry'：'green'，'guido'：'blue'}
  目前存储为：entries = [[' - '，' - '，' - ']，
  [-8522787127447073495，'barry'，'green']，
  [' - '，' - '，' - ']，
  [' - '，' - '，' - ']，
  [ ' - '，' - '，' - ']，
  [-9092791511155847987，'timmy'，'red']，
  [' - '，' - '，' - ']，
  [-6480567542315338377，'guido'，'blue']]
  相反，数据应按如下方式组织：indices = [None，1，None，None，None，0，None，2]
  entries = [[-9092791511155847987，'timmy'，'red']，
  [-8522787127447073495，'barry'，'green']，
  [-6480567542315338377，'guido'，'blue']]

  正如您现在可以看到的那样，在原始提案中，大量空间基本上是空的，以减少碰撞并使查找更快 . 使用新方法，您可以通过在索引中移动实际需要的稀疏性来减少所需的内存 .

  ---

  [1]：我说“插入有序”而不是“有序”，因为存在OrderedDict，“ordered”表示dict对象不提供的进一步行为 . OrderedDicts是可逆的，提供顺序敏感的方法，主要提供顺序敏感的相等测试（==，！=） . dicts目前不提供任何这些行为/方法 .

  ---

  [2]：新的字典实现通过更紧凑的设计实现更好的内存;这是主要的好处 . 速度方面，差异并不是那么激烈，新的字典可能会引入轻微的回归（例如键查找），而在其他情况下（迭代和调整大小）会出现性能提升 .

  总的来说，字典的性能，特别是在现实生活中，由于引入的紧凑性而得到改善 .

  回复于 2024-04-29T01:42:44+08:00
• 17

  更新：Guido van Rossum announced on the mailing list，从Python 3.7 dict 开始，所有Python实现都必须保留插入顺序 .

  回复于 2024-04-29T01:42:44+08:00