为什么Python的集合不保留插入顺序？

Question

为什么Python的集合不保留插入顺序？

61

最近我惊讶地发现，尽管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团队在为字典保留顺序的同时没有使内置集合也保留顺序。

- Bart Robinson

1

这个回答解决了你的问题吗？Python有有序集合吗？ - Mihai Chelaru

4

不，我理解Python没有内置有序集合。我只是想知道为什么会这样，因为字典现在是有序的。 - Bart Robinson

6

使用模式不同，因此它们针对不同的用例进行了优化。一种普遍的误解是集合只是CPython中具有null值的字典，这是完全不正确的：它们的实现不同。如果您的问题没有关闭，我可以发布详细答案。 - wim

1

使用模式不同，因此它们针对不同的用例进行了优化。一个好的回答应该详细说明这一点。问题是关于什么使得这两种不同的方法对应的用例最优。 - Karl Knechtel

2

请注意，自2.7版本以来，PyPy在“dict”和“set”中使用相同的排序方式。 - MisterMiyagi

2个回答

8

讨论

你的问题很相关，并且已经在python-devs上得到了广泛讨论。R. Hettinger在那个帖子中分享了一系列理由。在T. Peters发表了详细回复后，该问题的状态似乎还没有确定下来。一段时间过后（约2022年），讨论在python-ideas的其他地方重新燃起。

简而言之，保留插入顺序的现代字典实现是独特的，不适用于集合。特别地，字典在Python中随处可见（例如对象命名空间中的__dict__）。现代字典背后的主要动机是减小大小，从而使Python整体更加内存高效。相比之下，在Python核心中，集合比字典使用更少，因此不鼓励进行这样的重构。另请参见R. Hettinger关于现代字典实现的讲座。

观点

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

相应的数学概念是无序的，强加这样的顺序是很奇怪的-R. Hettinger

如果在Python中引入任何类型的排序，那么这种行为将符合一个完全独立的数学结构，即有序集合（或Oset）。 Oset在数学中扮演着单独的角色，特别是在组合学中。 Osets的一个实际应用是在更改钟声中观察到的。

拥有无序集合与一种非常通用和普遍的数据结构相一致，这种数据结构是现代大多数数学的基础，即集合论。我认为，在Python中使用无序集合是有好处的。

另请参阅扩展此主题的相关帖子：

- pylang

我的理解是，在数学意义上，完全有序集合实际上是已排序的集合（例如C++的std::set），而不是Python dict所具有的插入顺序排序。因此，无论数学“有序集合”存在什么样的论点，都不能支持Python中类似于dict的有序set。 - ShadowRanger

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- wim · Accepted Answer

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

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

dictobject.c - 主要, v3.5.9
setobject.c - 主要, v3.5.9
问题18771 - 在Python 3.4中减少集合对象哈希冲突成本的变更集。

从理论上讲，将CPython的集合实现更改为类似紧凑字典的方式是可能的，但实际上存在一些缺点，而且一些重要的核心开发人员反对进行这样的更改。

集合仍然是无序的。（为什么？使用模式不同。此外，实现也不同。）

- Guido van Rossum

集合使用一种不太适合保留插入顺序的算法。如果需要顺序，集合之间的操作会失去灵活性和优化。集合数学是基于无序集合定义的。简而言之，集合排序不在近期计划中。

- Raymond Hettinger

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

总结起来，主要观点是：不同的使用模式（插入顺序字典如**kwargs对于集合来说很有用，但对于集合来说不太有用），压缩集合的空间节省较少（因为只有键+哈希数组需要稠密化，而不是键+哈希+值数组），以及目前集合使用的线性探测优化与紧凑实现不兼容。

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

2016年9月14日下午3:50，Eric Snow写道：除非我理解错了，Raymond反对对集合进行类似的更改。

没错。在人们开始胡乱行动之前，我有几个关于这个问题的想法。

对于紧凑字典来说，通过索引和为键/值/哈希数组分配的额外空间消耗，与键/值/哈希数组的密度改善相比，空间节省是一个净胜利。然而，对于集合来说，情况要差得多，因为我们仍然需要索引和为键/值/哈希数组分配额外空间，但只能通过使三个数组中的两个变得更密集来抵消空间成本。换句话说，当你的键、值和哈希都浪费了空间时，紧凑化才更有意义。如果你失去了这三个中的一个，它就不再具有吸引力。

集合的使用模式与字典不同。前者有更多的命中或未命中查找，而后者往往有较少的缺失键查找。此外，一些针对集合操作的优化使得保留集合排序变得困难，而不影响性能。

我追求了一条改进集合性能的替代路径。我添加了线性探测来减少冲突的成本并提高缓存性能。这种改进与我为字典提倡的紧凑化方法不兼容。

目前，字典的排序副作用是不保证的，所以现在要开始坚持集合也变得有序是为时过早的。文档已经链接到一个创建有序集合的示例（https://code.activestate.com/recipes/576694/），但似乎几乎没有人使用。此外，现在Eric Snow已经给我们提供了一个快速的有序字典，使用MutableSet和OrderedDict构建OrderedSet比以往更容易，但我还没有观察到任何真正的兴趣，因为典型的集合对集合的数据分析实际上不需要也不关心排序。同样，快速成员测试的主要用途是无序的。

话虽如此，我确实认为可以在PyPI上添加其他集合实现的替代方案。特别是对于可排序数据的一些有趣的特殊情况，通过比较整个键范围可以加速集合对集合的操作（参见https://code.activestate.com/recipes/230113-implementation-of-sets-using-sorted-lists作为起点）。我记得，PyPI上已经有了用于类似集合的布隆过滤器和布谷鸟哈希的代码。

我理解，将一大块代码接受到Python核心中是令人兴奋的，但这不应该打开大门，让我们对其他数据类型进行更多的重写，除非我们确信这是有必要的。

– Raymond Hettinger 来自2016年9月的[Python-Dev] Python 3.6 dict becomes compact and gets a private version; and keywords become ordered。