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

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

集合和字典针对不同的用例进行了优化。 集合的主要用途是快速的成员资格测试，该测试与订单无关。
对于dicts，查找成本是最关键的 *** 作，而密钥更可能出现。对于集合，元素的存在或不存在是事先未知的，因此集合实现需要针对发现和未发现的情况进行优化。同样，对通用集合 *** 作（​​例如联合和相交）的一些优化使得在不降低性能的情况下很难保留集合顺序。

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

• dictobject.c

  -大师，v3.5.9

• setobject.c

  -大师，v3.5.9
• issue18771-变更集可减少Python 3.4中设置对象的哈希冲突的成本。

这将是 可能 在理论上改变的CPython的一套实施类似于紧凑快译通，但在实践中也有缺点，和显着的核心开发者反对做出这样的改变。

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

– Guido van Rossum

集合使用其他算法，该算法不太适合保留插入顺序。如果需要订购，按套设置 *** 作会失去灵活性和优化性。集合数学是根据无序集合定义的。简而言之，设置顺序不是在不久的将来。

–雷蒙德·海廷格（Raymond
Hettinger）

可以在python-dev邮件列表中找到有关是否为3.7压缩集合以及为何反对集合的详细讨论。

总而言之，要点是：不同的使用模式（插入排序命令如**
kwargs是有用的，对于集合而言则较少），压缩集的空间节省意义不大（因为只有键+哈希数组可用于密化，因为相对于键+哈希+值数组），并且当前设置的上述线性探测优化与紧凑型实现不兼容。

我将在下面复制雷蒙德的帖子，其中涵盖了最重要的方面。

2016年9月14日下午3:50，埃里克·斯诺（Eric Snow）写道：

然后，我将对集合进行相同的 *** 作。

除非我有误解，否则雷蒙德反对对设置进行类似的更改。

那就对了。在人们开始疯狂奔跑之前，这里有一些关于这个问题的想法。

*对于紧凑型dict，节省空间是一项净赢，索引消耗了额外的空间，并且键/值/哈希数组的超额分配被键/值/哈希数组的密度提高所抵消。但是，对于集合而言，网络的不利程度要低得多，因为我们仍然需要索引和过度分配，但是只能通过压缩三个阵列中的两个来抵消空间成本。换句话说，当浪费键，值和哈希的空间时，压缩更为有意义。如果您输掉了这三者中的一者，它将不再具有吸引力。

*集的使用模式与字典不同。前者有更多的命中或未命中查询。后者往往缺少丢失的键查找。同样，对设置到设置 *** 作的一些优化使得很难在不影响性能的情况下保留设置顺序。

*我寻求替代途径来改善布景表现。我没有进行压缩（这不会节省太多空间，并且不会招致额外的间接费用），而是添加了线性探测以减少冲突的成本并提高缓存性能。这种改进与我提倡的字典压缩方法不兼容。

• 目前，字典的排序副作用尚无保证，因此现在过早地坚持认为集合也已排序还为时过早。这些文档已经链接到用于创建OrderedSet的配方（
  https://pre.activestate.com/recipes/576694/），但似乎吸收率几乎为零。另外，既然Eric
  Snow给了我们快速的OrderedDict，现在比以往任何时候都更容易从MutableSet和OrderedDict构建OrderedSet，但是我再也没有观察到任何真正的兴趣，因为典型的按组设置数据分析并没有需要或关心订购。同样，快速成员资格测试的主要用途是与订单无关的。

*就是说，我确实认为有空间向PyPI添加替代集实现。特别是，对于可订购数据，存在一些有趣的特殊情况，其中可以通过比较整个键范围来加快设置 *** 作（请参阅
https://pre.activestate.com/recipes/230113-implementation-
of-
为起点设置使用排序列表）。IIRC，PyPI已经具有用于类似集合的布隆过滤器和布谷鸟哈希的代码。

• 我了解到，将一大段代码接受到Python内核中是令人兴奋的，但是除非我们确定有必要，否则不应向进行其他数据类型的更大型重写的闸门打开。

–雷蒙德·海廷格（Raymond Hettinger）

从[Python-Dev]起，Python
3.6字典变得紧凑并获得了私有版本；并于2016年9月对关键字进行了排序。