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

Question

字典在Python 3.6中排序(至少在CPython实现下),与之前的版本不同.这似乎是一个重大变化,但它只是文档中的一小段.它被描述为CPython实现细节而不是语言特性,但也暗示这可能成为未来的标准.

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

以下是文档中的文字:

dict()现在使用PyPy开创的"紧凑"表示.与Python 3.5相比,新dict()的内存使用量减少了20%到25%.PEP 468(在函数中保留**kwargs的顺序.)由此实现.这个新实现的顺序保留方面被认为是一个实现细节,不应该依赖(这可能会在未来发生变化,但是在更改语言规范之前,希望在几种版本的语言中使用这个新的dict实现为所有当前和未来的Python实现强制命令保留语义;这也有助于保持与随机迭代顺序仍然有效的语言的旧版本的向后兼容性,例如Python 3.5).(由INADA Naoki在issue 27350中提供.最初由Raymond Hettinger提出的想法.)

2017年12月更新:Python 3.7 保证了dict保留插入顺序

Answer 1

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

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

从Python 3.7开始,这不再是一个实现细节,而是成为一种语言功能.来自GvR的py​​thon-dev消息:

这样做."Dict保持插入秩序"是裁决.谢谢!

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

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

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

• 第一个数组按照插入顺序dk_entries保存字典的条目(类型PyDictKeyEntry).保留顺序是通过仅作为附加数组来实现的,其中新项目总是在末尾插入(插入顺序).

• 第二个,dk_indices保存dk_entries数组的索引(即指示相应条目位置的值dk_entries).此数组充当哈希表.当密钥被散列时,它导致存储在其中的索引之一,dk_indices并且通过索引来获取相应的条目dk_entries.由于只保留索引,因此该数组的类型取决于字典的整体大小(从/ bit构建的类型int8_t(1字节)到int32_t/ int64_t(4/ 8字节))3264

在前面的实现中,必须分配类型PyDictKeyEntry和大小的稀疏数组dk_size; 不幸的是,它也导致了很多空的空间,因为出于性能原因,该阵列不允许超过2/3 * dk_size满.(和空的空间仍然有大小!).PyDictKeyEntry

现在情况并非如此,因为只保存了所需的条目(已插入的条目),并且保留了类型的稀疏数组intX_t(X取决于字典大小)2/3 * dk_size.空格从类型更改PyDictKeyEntry为intX_t.

因此,显然,创建稀疏数组类型PyDictKeyEntry比用于存储ints 的稀疏数组要求更高的内存.

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

在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的情况下,"有序"表示dict对象没有提供的进一步行为.OrderedDicts是可逆的,提供顺序敏感的方法,主要提供顺序敏感的相等测试(==,!=).dict目前不提供任何这些行为/方法.}

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

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

Answer 2

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

我应该使用dict或OrderedDict在Python 3.6？

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

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

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

让您的代码面向未来:)

有关于辩论在这里.

编辑:Python 3.7将保持这个功能 看到

Answer 3

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

Answer 4

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

Python 3.8尚未发布，但它甚至包括reversed()字典中的函数（消除了的另一处差异OrderedDict。）。

现在可以使用reversed（）以反向插入顺序迭代Dict和dictviews。（由RémiLapeyre在bpo-33462中贡献。） 查看python 3.8的新增功能

我看不到相等运算符或的其他功能，OrderedDict因此它们仍然不完全相同。

Answer 5

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

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

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

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

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

一个声明关于OrderedDict VS快译通：

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