Python 3.6+中的字典是否有序？

13 浏览
0 Comments

Python 3.6+中的字典是否有序？

输出内容缺失

admin 更改状态以发布 2023年5月23日
0

2 答案

0 Comments

以下是回答原问题的内容：

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

我认为文档中这句话已经足够回答你的问题了：

这个新实现中保留顺序的特性被视为实现的细节，不应依赖于它

dict 并没有明确表示它是有序集合，因此如果你想保持一致性并不依赖新实现的副作用，你应该继续使用 OrderedDict。

让你的代码具备未来的兼容性 🙂

关于这个问题还有一些讨论可以在这里看到。

编辑： Python 3.7 将保持这个作为特性，可以 查看

0
0 Comments

Python 3.6+中的字典是有序的吗？

它们是插入有序[1]的。

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

从Python 3.7开始，这是一项保证的语言特性，而不仅仅是一个实现细节。来自GvR的python-dev消息：

请这样做。 "Dict keeps insertion order"是命令。谢谢！

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

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

基本上是通过保持两个数组。

  • 第一个数组（dk_entries）按它们插入的顺序保存字典的项（类型为 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 的空间（空白空间仍然具有 PyDictKeyEntry 大小！）。

现在的情况不是这样的，因为只有已插入的条目被存储(即只存储所需条目)，并且保留了一种类型为intX_t(取决于字典大小的X)的稀疏数组，2/3*dk_size个槽位被占用。空白空间从PyDictKeyEntry类型更改为intX_t类型。

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

如果感兴趣的话，可以在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对象不提供的进一步行为。OrderedDict是可逆的，提供顺序敏感方法，主要提供顺序敏感的相等测试（`==`，`!=`）。dict目前不提供任何这些行为/方法。

[2]:新的字典实现经过更紧凑的设计，在内存方面表现更好;这是主要的优点。在速度方面，差异并不如此显著，新字典可能会在某些地方引入轻微的退化(例如键查找)，而在其他地方(比如迭代和重新调整大小)应该会有性能提升。
总体而言，字典的性能，特别是在实际情况下，由于引入的紧密度而得到改善。

0