Python-字典是用Python3.6+订购的吗？

Question

与以前的版本不同，字典在Python 3.6中排序（至少在CPython实现下）。这似乎是一个重大更改，但只是文档中的一小段。它被描述为CPython实现细节而不是语言功能，但这也意味着将来可能会成为标准。

在保留元素顺序的同时，新的词典实现如何比旧的实现更好？

以下是文档中的文字：

dict()现在使用PyPy率先提出的“compact”表示形式。与Python 3.5相比，新dict（）的内存使用量减少了20％至25％。PEP 468（在函数中保留** kwarg的顺序。）由此实现。此新实现的顺序保留方面被认为是实现细节，因此不应依赖（将来可能会更改，但是在更改语言规范之前，希望在几个发行版中使用该新dict实现该语言的几个版本为所有当前和将来的Python实现强制要求保留顺序的语义；这还有助于保留与仍旧有效的随机迭代顺序的旧版本语言（例如Python 3.5）的向后兼容性。（由INADA Naoki在发行27350。最初由Raymond Hettinger提出的想法。）

Answer 1

它们是插入顺序[1]。从Python 3.6开始，对于Python的CPython实现，词典会记住插入项目的顺序。这在Python 3.6中被视为实现细节；你需要使用OrderedDict，如果你想多数民众赞成插入排序保证不同的Python的其它实现（与其他有序行为[1] ）。

从Python 3.7开始，它不再是实现细节，而是成为一种语言功能。从GvR的py​​thon-dev消息中：

做到这一点。裁定“裁定保留插入顺序”。谢谢！

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

在保留元素顺序的同时，Python 3.6字典实现如何比旧的实现更好的性能[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_size。空格从类型更改PyDictKeyEntry为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']]

正如你现在可以从视觉上看到的那样，在原始建议中，很多空间实际上是空的，以减少冲突并加快查找速度。使用新方法，可以通过将稀疏移动到真正需要的索引中来减少所需的内存。