为什么 Python 集合不保留插入顺序？-IT科技

摘要：问题描述：最近我惊讶地发现，虽然字典在 Python 3.7+ 中可以保证保留插入顺序，但集合却不能：>>> d = {'a': 1, 'b': 2, 'c': 3} >>> d {'a': 1, 'b': 2, 'c': 3} >>> d['d'] = ...

问题描述：

最近我惊讶地发现，虽然字典在 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 团队没有让内置集合像字典一样保留顺序。

解决方案 1：

集合和字典针对不同的用例进行了优化。集合的主要用途是快速成员测试，这与顺序无关。对于字典，查找成本是最关键的操作，并且键更有可能存在。对于集合，元素的存在与否是无法提前知道的，因此集合实现需要针对找到和未找到的情况进行优化。此外，对常见集合操作（例如并集和交集）的一些优化使得在不降低性能的情况下保留集合顺序变得困难。

虽然这两种数据结构都是基于哈希的，但人们普遍误以为集合只是作为具有空值的字典来实现的。即使在 CPython 3.6 中实现紧凑的字典之前，集合和字典的实现就已经存在很大差异，代码重用性很低。例如，字典使用随机探测，但集合使用线性探测和开放寻址的组合来改善缓存局部性。初始线性探测（CPython 中默认为9 步）将检查一系列相邻的键/哈希对，通过降低哈希冲突处理的成本来提高性能 - 连续内存访问比分散探测更便宜。

dictobject.c-主要，v3.5.9
setobject.c-主要，v3.5.9
issue18771-变更集以减少 Python 3.4 中集合对象的哈希冲突成本。

理论上可以将CPython 的集合实现更改为类似于紧凑字典，但在实践中存在缺点，而且著名的核心开发人员反对进行这样的改变。

集合保持无序。（为什么？使用模式不同。此外，实现也不同。）

–吉多·范罗苏姆

集合使用不同的算法，无法像保留插入顺序那样进行修正。如果需要顺序，集合到集合操作将失去灵活性和优化。集合数学是根据无序集合定义的。简而言之，集合排序并不是近期的未来。

–雷蒙德·赫廷格

在 python-dev 邮件列表中可以找到关于是否对 3.7 进行压缩集合以及为什么不这样做的详细讨论。

总之，要点为：不同的使用模式（插入排序字典如 **kwargs 很有用，但对于集合来说则没那么有用），压缩集合的空间节省不太显著（因为只有 key + hash 数组需要密集化，而不是 key + hash + value 数组），并且前面提到的集合当前使用的线性探测优化与紧凑实现不兼容。

我将在下面重现 Raymond 的帖子，其中涵盖了最重要的观点。

2016 年 9 月 14 日下午 3:50，Eric Snow 写道：
然后，我会对集合做同样的事情。
除非我误解了，否则雷蒙德反对对场景进行类似的改变。
没错。在人们开始胡乱评论之前，我来谈谈我对这个问题的一些看法。
对于紧凑型字典，空间节省是净收益，索引消耗的额外空间和键/值/哈希数组的过度分配被键/值/哈希数组的改进密度所抵消。然而对于集合，净收益就不那么有利了，因为我们仍然需要索引和过度分配，但只能通过密集化三个数组中的两个来抵消空间成本。换句话说，当你浪费了键、值和哈希的空间时，压缩更有意义。如果你失去这三者之一，它就不再引人注目了。
集合的使用模式与字典不同。前者有更多命中或未命中的查找。后者往往有较少的缺失键查找。此外，对集合到集合操作的一些优化使得在不影响性能的情况下保留集合顺序变得困难。
我寻求替代方法来提高集合性能。我没有使用压缩（这并没有节省多少空间，而且会产生额外的间接成本），而是添加了线性探测来降低冲突成本并提高缓存性能。这种改进与我提倡的字典压缩方法不相容。
目前，字典的排序副作用是无法保证的，因此现在开始坚持集合也变得有序还为时过早。文档已经链接到创建 OrderedSet 的方法（
https://code.activestate.com/recipes/576694/），但似乎采用率几乎为零。此外，现在 Eric Snow 为我们提供了一个快速的 OrderedDict，从 MutableSet 和 OrderedDict 构建 OrderedSet 比以往任何时候都容易，但我再次没有观察到任何真正的兴趣，因为典型的集合到集合数据分析实际上并不需要或关心排序。同样，快速成员资格测试的主要用途是顺序不可知的。
话虽如此，我确实认为 PyPI 仍有空间添加替代集合实现。特别是，对于可排序数据，有一些有趣的特殊情况，可以通过比较整个键范围来加速集合到集合的操作（请参阅
https://code.activestate.com/recipes/230113-implementation-of-sets-using-sorted-lists
了解起点）。如果我没记错的话，PyPI 已经有了类似集合的布隆过滤器和布谷鸟哈希的代码。
我理解，将一个主要的代码块纳入 Python 核心是令人兴奋的，但除非我们确定有必要，否则这不应该为对其他数据类型进行更多重大重写打开闸门。

– 雷蒙德·赫廷格

摘自[Python-Dev] Python 3.6 dict 变得紧凑并获得私有版本；且关键字变得有序，2016年9月。

解决方案 2：

讨论

您的问题很贴切，已在 python-devs 上进行了深入讨论。R. Hettinger在该主题中分享了一系列理由。在 T. Peters 做出详细回复后不久，该问题的状态似乎没有定论。一段时间后（约 2022 年），该讨论在python-ideas的其他地方重新燃起。

简而言之，保留插入顺序的现代字典的实现是独一无二的，并且不适用于集合。特别是，字典在运行 Python 时无处不在（例如__dict__在对象的命名空间中）。现代字典背后的主要动机是减小大小，使 Python 整体上更节省内存。相比之下，集合在 Python 核心中的流行程度不如字典，因此阻止了这种重构。另请参阅 R. Hettinger关于现代字典实现的演讲。

观点

Python 中集合的无序性质与数学集合的行为相似。不保证顺序。