为什么 Python 集不保留插入顺序？
Why don't Python sets preserve insertion order?
最近我很惊讶地发现，虽然在 Python 3.7+ 中保证字典保留插入顺序，但集不是：
>>> d = {'a': 1, 'b': 2, 'c': 3}
>>> d
{'a': 1, 'b': 2, 'c': 3}
>>> d['d'] = 4
>>> d
{'a': 1, 'b': 2, 'c': 3, 'd': 4}
>>> s = {'a', 'b', 'c'}
>>> s
{'b', 'a', 'c'}
>>> s.add('d')
>>> s
{'d', 'b', 'a', 'c'}
造成这种差异的原因是什么？导致 Python 团队更改 dict 实现的相同效率改进是否也不适用于集合？
我不是在寻找指向有序集实现的指针，也不是在寻找使用字典作为集合替代品的方法。我只是想知道为什么 Python 团队没有在为听写做内置集合的同时保留顺序。
Sets 和 dicts 针对不同的用例进行了优化。 集合的主要用途是快速成员资格测试，它与顺序无关。对于字典，查找成本是最关键的操作，并且键更有可能出现。对于集合，元素是否存在是事先不知道的，因此集合实现需要针对找到和未找到的情况进行优化。此外，对常见集合运算（例如并集和交集）的一些优化使得在不降低性能的情况下难以保留集合顺序。
虽然这两种数据结构都是基于散列的，但一个常见的误解是集合只是作为具有空值的字典来实现的。即使 在 CPython 3.6 中的紧凑 dict 实现之前，set 和 dict 实现也已经存在显着差异，几乎没有代码重用。例如，字典使用随机探测，而集合使用线性探测和开放寻址的组合，以改善缓存局部性。初始线性探测（CPython 中的默认 9 steps）将检查一系列相邻的 key/hash 对，通过降低哈希冲突处理的成本来提高性能 - 连续内存访问比分散访问更便宜探针。
dictobject.c - master, v3.5.9setobject.c - master, v3.5.9- issue18771 - 变更集以减少 Python 3.4.
中集合对象的散列冲突成本
理论上可能将CPython的set实现改成类似于compact dict，但在实践中有缺点，值得注意核心开发人员反对进行此类更改。
Sets remain unordered. (Why? The usage patterns are different. Also, different implementation.)
Sets use a different algorithm that isn't as amendable to retaining insertion order.
Set-to-set operations lose their flexibility and optimizations if order is required. Set mathematics are defined in terms of unordered sets. In short, set ordering isn't in the immediate future.
在 python-dev 邮件列表中可以找到关于是否为 3.7 压缩集以及为什么不这样做的详细讨论。
总而言之，要点是：不同的使用模式（插入排序指令如 **kwargs 是 useful，对于集合而言较少），space 压缩集合的节省不太显着（因为只有 key + hash 数组可以加密，而不是 key + hash + value 数组），并且前面提到的集合当前使用的线性探测优化与紧凑实现不兼容。
我将在下面重现 Raymond 的 post，其中涵盖了最重要的要点。
On Sep 14, 2016, at 3:50 PM, Eric Snow wrote:
Then, I'll do same to sets.
除非我误解了，否则雷蒙德反对制作类似的
更改设置。
没错。这里有一些关于这个问题的想法，摆在人们面前
开始 运行 狂野。
对于 compact dict，space 节省是一个净赢，额外的 space 被索引和过度分配消耗
key/value/hash 数组被改进的抵消了
key/value/hash 数组的密度。然而对于套装来说，网是很多的
不太有利，因为我们仍然需要指数和过度分配
但只能通过压缩三个中的两个来抵消 space 成本
阵列。换句话说，当你有
浪费 space 用于键、值和哈希。如果你失去其中之一
三，它不再引人注目。
集的使用模式与字典不同。前者有更多的命中或未命中查找。后者往往有更少的丢失密钥
查找。此外，一些针对set-to-set操作的优化
很难在不影响的情况下保留集合顺序
性能。
我寻求其他途径来提高集合性能。而不是压缩（这不是 space 赢的很多，并招致了
附加间接），我添加了线性探测以降低成本
碰撞并提高缓存性能。这种改进是
与我提倡的压缩方法不兼容
词典。
目前，字典的排序副作用是无法保证的，所以开始坚持让集合也变得有序还为时过早。
文档已经 link 用于创建 OrderedSet (
https://code.activestate.com/recipes/576694/ ) 但看起来像
吸收率几乎为零。另外，既然 Eric Snow 给了我们一个
快速 OrderedDict，从中构建 OrderedSet 比以往任何时候都容易
MutableSet 和 OrderedDict，但我还是没有观察到任何真正的
兴趣，因为典型的组对组数据分析并不真正需要
或关心订购。同样，快速会员的主要用途
测试与顺序无关。
就是说，我确实认为有向 PyPI 添加替代集实现的空间。特别是，有一些有趣的
可订购数据的特殊情况，其中可以进行 set-to-set 操作
通过比较整个范围的键来加速（见
https://code.activestate.com/recipes/230113-implementation-of-sets-using-sorted-lists
为起点）。 IIRC，PyPI 已经有了类似 set-like bloom 的代码
过滤器和布谷鸟哈希。
我知道让一个主要代码块被接受到 Python 核心是令人兴奋的，但这不应该打开闸门
参与其他数据类型的更多重大重写，除非我们确定
这是有保证的。
– Raymond Hettinger
自 [Python-Dev] Python 3.6 dict becomes compact and gets a private version; and keywords become ordered，2016 年 9 月。
讨论
你的问题很重要，T. Peters 已经heavily discussed on python-devs not long ago. R. Hettinger shared a list of rationales in that thread. The state of the issue appears open-ended now, shortly after this detailed reply提出了。
简而言之，保留插入顺序的现代字典的实现是独一无二的，不适合集合。特别是，dicts 无处不在 运行 Python （例如 __dict__ 在对象的命名空间中）。现代 dict 背后的一个主要动机是减小大小，使 Python 整体内存效率更高。相比之下，集合在 Python 的核心中不如字典普遍，因此阻止了这种重构。另请参阅 R. Hettinger 关于现代字典实现的 talk。
观点
Python 中集合的无序性质与 mathematical sets 的行为相似。不能保证订单。
The corresponding mathematical concept is unordered and it would be weird to impose
such as order - R. Hettinger
如果order of any kind were introduced to sets in Python, then this behavior would comply with a completely separate mathematical structure, namely an ordered set (or Oset). Osets play a separate roll in mathematics, particularly in combinatorics. One practical application of Osets is observed in changing of bells。
拥有无序集与非常通用且无处不在的数据结构一致，该数据结构取消了大多数现代数学，即 Set Theory。我提交，Python 中的无序集很好。
另请参阅扩展此主题的相关帖子：
- Converting a list to a set changes element order
- Get unique values from a list in python
最近我很惊讶地发现，虽然在 Python 3.7+ 中保证字典保留插入顺序，但集不是：
>>> d = {'a': 1, 'b': 2, 'c': 3}
>>> d
{'a': 1, 'b': 2, 'c': 3}
>>> d['d'] = 4
>>> d
{'a': 1, 'b': 2, 'c': 3, 'd': 4}
>>> s = {'a', 'b', 'c'}
>>> s
{'b', 'a', 'c'}
>>> s.add('d')
>>> s
{'d', 'b', 'a', 'c'}
造成这种差异的原因是什么？导致 Python 团队更改 dict 实现的相同效率改进是否也不适用于集合？
我不是在寻找指向有序集实现的指针，也不是在寻找使用字典作为集合替代品的方法。我只是想知道为什么 Python 团队没有在为听写做内置集合的同时保留顺序。
Sets 和 dicts 针对不同的用例进行了优化。 集合的主要用途是快速成员资格测试，它与顺序无关。对于字典，查找成本是最关键的操作，并且键更有可能出现。对于集合，元素是否存在是事先不知道的，因此集合实现需要针对找到和未找到的情况进行优化。此外，对常见集合运算（例如并集和交集）的一些优化使得在不降低性能的情况下难以保留集合顺序。
虽然这两种数据结构都是基于散列的，但一个常见的误解是集合只是作为具有空值的字典来实现的。即使 在 CPython 3.6 中的紧凑 dict 实现之前，set 和 dict 实现也已经存在显着差异，几乎没有代码重用。例如，字典使用随机探测，而集合使用线性探测和开放寻址的组合，以改善缓存局部性。初始线性探测（CPython 中的默认 9 steps）将检查一系列相邻的 key/hash 对，通过降低哈希冲突处理的成本来提高性能 - 连续内存访问比分散访问更便宜探针。
dictobject.c- master, v3.5.9setobject.c- master, v3.5.9- issue18771 - 变更集以减少 Python 3.4. 中集合对象的散列冲突成本
理论上可能将CPython的set实现改成类似于compact dict，但在实践中有缺点，值得注意核心开发人员反对进行此类更改。
Sets remain unordered. (Why? The usage patterns are different. Also, different implementation.)
Sets use a different algorithm that isn't as amendable to retaining insertion order. Set-to-set operations lose their flexibility and optimizations if order is required. Set mathematics are defined in terms of unordered sets. In short, set ordering isn't in the immediate future.
在 python-dev 邮件列表中可以找到关于是否为 3.7 压缩集以及为什么不这样做的详细讨论。
总而言之，要点是：不同的使用模式（插入排序指令如 **kwargs 是 useful，对于集合而言较少），space 压缩集合的节省不太显着（因为只有 key + hash 数组可以加密，而不是 key + hash + value 数组），并且前面提到的集合当前使用的线性探测优化与紧凑实现不兼容。
我将在下面重现 Raymond 的 post，其中涵盖了最重要的要点。
On Sep 14, 2016, at 3:50 PM, Eric Snow wrote:
Then, I'll do same to sets.
除非我误解了，否则雷蒙德反对制作类似的 更改设置。
没错。这里有一些关于这个问题的想法，摆在人们面前 开始 运行 狂野。
对于 compact dict，space 节省是一个净赢，额外的 space 被索引和过度分配消耗 key/value/hash 数组被改进的抵消了 key/value/hash 数组的密度。然而对于套装来说，网是很多的 不太有利，因为我们仍然需要指数和过度分配 但只能通过压缩三个中的两个来抵消 space 成本 阵列。换句话说，当你有 浪费 space 用于键、值和哈希。如果你失去其中之一 三，它不再引人注目。
集的使用模式与字典不同。前者有更多的命中或未命中查找。后者往往有更少的丢失密钥 查找。此外，一些针对set-to-set操作的优化 很难在不影响的情况下保留集合顺序 性能。
我寻求其他途径来提高集合性能。而不是压缩（这不是 space 赢的很多，并招致了 附加间接），我添加了线性探测以降低成本 碰撞并提高缓存性能。这种改进是 与我提倡的压缩方法不兼容 词典。
目前，字典的排序副作用是无法保证的，所以开始坚持让集合也变得有序还为时过早。 文档已经 link 用于创建 OrderedSet ( https://code.activestate.com/recipes/576694/ ) 但看起来像 吸收率几乎为零。另外，既然 Eric Snow 给了我们一个 快速 OrderedDict，从中构建 OrderedSet 比以往任何时候都容易 MutableSet 和 OrderedDict，但我还是没有观察到任何真正的 兴趣，因为典型的组对组数据分析并不真正需要 或关心订购。同样，快速会员的主要用途 测试与顺序无关。
就是说，我确实认为有向 PyPI 添加替代集实现的空间。特别是，有一些有趣的 可订购数据的特殊情况，其中可以进行 set-to-set 操作 通过比较整个范围的键来加速（见 https://code.activestate.com/recipes/230113-implementation-of-sets-using-sorted-lists 为起点）。 IIRC，PyPI 已经有了类似 set-like bloom 的代码 过滤器和布谷鸟哈希。
我知道让一个主要代码块被接受到 Python 核心是令人兴奋的，但这不应该打开闸门 参与其他数据类型的更多重大重写，除非我们确定 这是有保证的。
– Raymond Hettinger
自 [Python-Dev] Python 3.6 dict becomes compact and gets a private version; and keywords become ordered，2016 年 9 月。
讨论
你的问题很重要，T. Peters 已经heavily discussed on python-devs not long ago. R. Hettinger shared a list of rationales in that thread. The state of the issue appears open-ended now, shortly after this detailed reply提出了。
简而言之，保留插入顺序的现代字典的实现是独一无二的，不适合集合。特别是，dicts 无处不在 运行 Python （例如 __dict__ 在对象的命名空间中）。现代 dict 背后的一个主要动机是减小大小，使 Python 整体内存效率更高。相比之下，集合在 Python 的核心中不如字典普遍，因此阻止了这种重构。另请参阅 R. Hettinger 关于现代字典实现的 talk。
观点
Python 中集合的无序性质与 mathematical sets 的行为相似。不能保证订单。
The corresponding mathematical concept is unordered and it would be weird to impose such as order - R. Hettinger
如果order of any kind were introduced to sets in Python, then this behavior would comply with a completely separate mathematical structure, namely an ordered set (or Oset). Osets play a separate roll in mathematics, particularly in combinatorics. One practical application of Osets is observed in changing of bells。
拥有无序集与非常通用且无处不在的数据结构一致，该数据结构取消了大多数现代数学，即 Set Theory。我提交，Python 中的无序集很好。
另请参阅扩展此主题的相关帖子：
- Converting a list to a set changes element order
- Get unique values from a list in python