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

Question

与以前的版本不同，字典在 Python 3.6 中排序(至少在 CPython 实现下)。这似乎是一个实质性的变化，但它只是 documentation 中的一小段。 .它被描述为 CPython 实现细节而不是语言特性，但也暗示这可能在 future 成为标准。
新字典实现如何在保留元素顺序的同时比旧字典实现更好？
以下是文档中的文本:

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.)

2017 年 12 月更新: dict s 保留插入顺序是 guaranteed对于 Python 3.7

Answer 1

Are dictionaries ordered in Python 3.6+?

他们是 已订购 [1] .从 Python 3.6 开始，对于 Python 的 CPython 实现，字典会记住插入项目的顺序。这被认为是 Python 3.6 中的一个实现细节；您需要使用 OrderedDict如果您想要在 Python 的其他实现中保证插入排序(以及其他有序行为 [1] )。
从 Python 3.7 开始 ，这不再是实现细节，而是成为一种语言特性。 From a python-dev message by GvR :

Make it so. "Dict keeps insertion order" is the ruling. Thanks!

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

How does the Python 3.6 dictionary implementation perform better^[2] than the older one while preserving element order?

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

第一个数组， 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 s 满保存。空白空间从类型 PyDictKeyEntry 更改至 intX_t .
所以，很明显，创建一个类型为 PyDictKeyEntry 的稀疏数组比用于存储 int 的稀疏数组需要更多内存s。
你可以看到完整的对话 on Python-Dev关于这个功能，如果有兴趣，它是一个很好的阅读。

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

For example, the dictionary:

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

is currently stored as [keyhash, key, value]:

entries = [['--', '--', '--'],
           [-8522787127447073495, 'barry', 'green'],
           ['--', '--', '--'],
           ['--', '--', '--'],
           ['--', '--', '--'],
           [-9092791511155847987, 'timmy', 'red'],
           ['--', '--', '--'],
           [-6480567542315338377, 'guido', 'blue']]

Instead, the data should be organized as follows:

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]:新的字典实现通过更紧凑的设计在**内存方面表现得更好**；这是这里的主要好处。速度方面，差异并没有那么大，有些地方新的字典可能会引入轻微的回归( key-lookups, for example )，而在其他地方(迭代和调整大小)应该存在性能提升。

总体而言，字典的性能，尤其是在现实生活中，由于引入了紧凑性而有所提高。