645

Dictionaries are ordered in Python 3.6 (under the CPython implementation at least) unlike in previous incarnations. This seems like a substantial change, but it's only a short paragraph in the documentation. It is described as a CPython implementation detail rather than a language feature, but also implies this may become standard in the future.

How does the new dictionary implementation perform better than the older one while preserving element order?

Here is the text from the documentation:

dict() now uses a “compact” representation pioneered by PyPy. The memory usage of the new dict() is between 20% and 25% smaller compared to Python 3.5. PEP 468 (Preserving the order of **kwargs in a function.) is implemented by this. The order-preserving aspect of this new implementation is considered an implementation detail and should not be relied upon (this may change in the future, but it is desired to have this new dict implementation in the language for a few releases before changing the language spec to mandate order-preserving semantics for all current and future Python implementations; this also helps preserve backwards-compatibility with older versions of the language where random iteration order is still in effect, e.g. Python 3.5). (Contributed by INADA Naoki in issue 27350. Idea originally suggested by Raymond Hettinger.)

Update December 2017: dicts retaining insertion order is guaranteed for Python 3.7

4

5 回答 5

715

字典是在 Python 3.6+ 中排序的吗？

它们是插入排序的[1]。从 Python 3.6 开始，对于 Python 的 CPython 实现，字典会记住插入项的顺序。这被认为是 Python 3.6 中的一个实现细节；如果您希望在 Python 的其他实现（以及其他有序行为[1]）中保证OrderedDict插入排序，则需要使用。

从 Python 3.7 开始，这不再是实现细节，而是成为一种语言特性。来自 GvR 的 python-dev 消息：

让它如此。“字典保持插入顺序”是裁决。谢谢！

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

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

本质上，通过保留两个数组。

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

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

在之前的实现中，必须分配一个类型PyDictKeyEntry和大小的稀疏数组；不幸的是，这也导致了很多空白空间，因为出于性能原因dk_size，该数组不允许超过2/3 * dk_size满。（并且空白空间仍然有大小！）。PyDictKeyEntry

现在情况并非如此，因为只存储了所需的条目（那些已插入的条目），并且保留了一个稀疏类型的数组intX_t（X取决于 dict 大小）2/3 * dk_sizes full。空白处从 typePyDictKeyEntry变为intX_t.

因此，很明显，创建一个类型PyDictKeyEntry的稀疏数组比存储ints 的稀疏数组需要更多的内存。

如果有兴趣，您可以在 Python-Dev 上查看有关此功能的完整对话，这是一本好书。

在 Raymond Hettinger 提出的原始提案中，可以看到所使用的数据结构的可视化，它抓住了这个想法的要点。

例如，字典：

d = {'timmy': 'red', 'barry': 'green', 'guido': 'blue'}

当前存储为 [keyhash, key, value]：

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 的存在，“有序”暗示了 `dict` 对象*不提供*的进一步行为。OrderedDicts 是可逆的，提供顺序敏感的方法，主要是提供顺序敏感的相等测试（`==`、`!=`）。`dict`s 目前不提供任何这些行为/方法。
[2]：新的字典实现通过更紧凑的设计在**内存方面表现得更好**；这是这里的主要好处。速度方面，差异不是那么大，有些地方新字典可能会引入轻微的回归（例如键查找），而在其他地方（迭代和调整大小）应该存在性能提升。 总体而言，字典的性能，尤其是在现实生活中，由于引入了紧凑性而有所提高。
于 2016-10-11T15:17:53.593 回答
77

以下是回答最初的第一个问题：

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

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

这个新实现的顺序保留方面被认为是一个实现细节，不应依赖

dict并不明确意味着是一个有序集合，所以如果你想保持一致而不依赖于新实现的副作用，你应该坚持使用OrderedDict.

让你的代码面向未来:)

有一个关于这里的辩论。

编辑：Python 3.7 将保留此功能， 请参阅

于 2016-10-11T15:09:00.853 回答
33

更新：Guido van Rossum在邮件列表中宣布，从 Python 3.7dict开始，所有 Python 实现必须保留插入顺序。

于 2017-12-15T17:24:53.057 回答
20

我想添加到上面的讨论中，但没有评论的声誉。

Python 3.8 包含reversed()字典上的函数（从OrderedDict.

现在可以使用 reversed() 以反向插入顺序迭代字典和字典视图。（由 Rémi Lapeyre 在 bpo-33462 中贡献。） 查看 python 3.8 中的新功能

我没有看到任何提及相等运算符或其他功能的内容，OrderedDict因此它们仍然不完全相同。

于 2019-07-26T14:38:59.097 回答
8

为了在 2020 年全面回答这个问题，让我引用Python 官方文档中的几句话：

在 3.7 版更改: 字典顺序保证为插入顺序。这种行为是 CPython 3.6 的实现细节。

在 3.7 版更改: 字典顺序保证为插入顺序。

在 3.8 版更改: 字典现在是可逆的。

字典和字典视图是可逆的。

关于 OrderedDict 与 Dict的声明：

有序词典就像普通词典一样，但具有一些与排序操作相关的额外功能。现在它们变得不那么重要了，因为内置的 dict 类获得了记住插入顺序的能力（这种新行为在 Python 3.7 中得到了保证）。

于 2020-10-26T20:14:23.970 回答