Bar*_*son 30 python cpython set
我最近惊讶地发现，虽然 dicts 保证在 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 实现的相同效率改进也不适用于集合吗？
我不是在寻找指向有序集实现的指针或使用 dicts 作为集合的替代品的方法。我只是想知道为什么 Python 团队没有在他们为 dicts 这样做的同时使内置集保留顺序。
wim*_*wim 27
集合和字典针对不同的用例进行了优化。集合的主要用途是快速成员资格测试，它与顺序无关。对于dicts来说，查找的代价是最关键的操作，key最有可能出现。对于集合，元素的存在与否事先是未知的，因此集合实现需要针对找到和未找到的情况进行优化。此外，对常见集合操作（例如并集和交集）的一些优化使得在不降低性能的情况下难以保持集合排序。
虽然这两种数据结构都是基于散列的，但一个常见的误解是认为集合只是作为具有空值的字典来实现的。甚至在 CPython 3.6 中的紧凑 dict 实现之前，set 和 dict 实现就已经存在显着差异，几乎没有代码重用。例如，dicts 使用随机探测，但集合使用线性探测和开放寻址的组合，以提高缓存局部性。初始线性探测（CPython 中默认为9 步）将检查一系列相邻的键/哈希对，通过降低哈希冲突处理的成本来提高性能 - 连续内存访问比分散探测便宜。
dictobject.c-大师，v3.5.9setobject.c-大师，v3.5.9这将是可能在理论上改变的CPython的一套实施类似于紧凑快译通，但在实践中也有缺点，和显着的核心开发者反对做出这样的改变。
集合保持无序。（为什么？使用模式不同。另外，不同的实现。）
集合使用不同的算法，该算法无法修改以保留插入顺序。如果需要顺序，Set-to-set 操作将失去其灵活性和优化。集合数学是根据无序集合定义的。简而言之，集合排序不是在不久的将来。
有关是否为 3.7 压缩集以及为什么决定反对的详细讨论，可以在 python-dev 邮件列表中找到。
总之，要点是：不同的使用模式（诸如 **kwargs 之类的插入排序字典很有用，对于集合来说不太有用），压缩集合的空间节省不太显着（因为只有键 + 哈希数组来致密化，如与键 + 散列 + 值数组相反），并且前面提到的当前使用的线性探测优化与紧凑的实现不兼容。
我将在下面复制 Raymond 的帖子，其中涵盖了最重要的要点。
2016 年 9 月 14 日下午 3:50，埃里克·斯诺写道：
然后，我会对套装做同样的事情。
除非我误解了，否则雷蒙德反对对布景做出类似的改变。
这是正确的。在人们开始疯狂之前，这里有一些关于这个主题的想法。
对于紧凑型字典，空间节省是一个净胜利，索引消耗的额外空间和键/值/哈希数组的过度分配被键/值/哈希数组的改进密度所抵消。然而，对于集合，网络不太有利，因为我们仍然需要索引和过度分配，但只能通过仅增密三个数组中的两个来抵消空间成本。换句话说，当您为键、值和散列浪费了空间时，压缩更有意义。如果你失去了这三个中的一个，它就不再有吸引力了。
集合的使用模式与字典不同。前者有更多的命中或未命中查找。后者往往具有较少的丢失键查找。此外，对 set-to-set 操作的一些优化使得在不影响性能的情况下很难保持 set 的顺序。
我寻求替代途径来提高集合性能。我没有进行压缩（这不会占用太多空间并且会产生额外的间接访问成本），而是添加了线性探测以降低冲突成本并提高缓存性能。这种改进与我为字典提倡的压缩方法不兼容。
目前，字典的排序副作用是不确定的，所以现在开始坚持集合也被排序还为时过早。文档已经链接到创建 OrderedSet ( https://code.activestate.com/recipes/576694/ )的配方， 但似乎吸收率几乎为零。此外，现在 Eric Snow 给了我们一个快速的 OrderedDict，从 MutableSet 和 OrderedDict 构建一个 OrderedSet 比以往任何时候都容易，但我再次没有观察到任何真正的兴趣，因为典型的 set-to-set 数据分析并没有真正需要或关心订购。同样，快速成员资格测试的主要用途是与订单无关。
也就是说，我确实认为有空间向 PyPI 添加替代集实现。特别是，对于可排序的数据有一些有趣的特殊情况，其中可以通过比较整个键范围来加速 set-to-set 操作（参见 https://code.activestate.com/recipes/230113-implementation-of-集合使用排序列表 作为起点）。IIRC，PyPI 已经有类似集合的布隆过滤器和布谷鸟散列的代码。
我理解将主要代码块接受到 Python 核心中是令人兴奋的，但除非我们确定这是必要的，否则不应打开闸门以进行其他数据类型的更多主要重写。
— 雷蒙德·赫廷格
从[Python-Dev] Python 3.6 dict 变得紧凑并获得私有版本；和关键字变得有序，2016 年 9 月。
讨论
你的问题是密切相关的，并且已经在 python-devs 上进行了大量讨论。R. Hettinger在该帖子中分享了一系列理由。在T. Peters 给出详细答复后不久，问题的状态似乎没有答案。一段时间后（约 2022 年），有关python-ideas 的讨论在其他地方重新点燃。
简而言之，保留插入顺序的现代字典的实现是独特的，并且不被认为适合集合。特别是，字典在任何地方都可以用来运行Python（例如__dict__在对象的命名空间中）。现代字典背后的一个主要动机是减少大小，使 Python 整体上内存效率更高。相比之下，在 Python 核心中，集合不如字典那么普遍，因此阻止了这种重构。另请参阅 R. Hettinger关于现代 dict 实现的演讲。
观点
Python 中集合的无序性质与数学集合的行为类似。订单无法保证。
相应的数学概念是无序的，强加这样的顺序会很奇怪 - R. Hettinger
如果在 Python 中将任何类型的顺序引入到集合中，那么这种行为将符合完全独立的数学结构，即有序集合（或 Oset）。Osets 在数学中发挥着独立的作用，特别是在组合数学中。奥塞特的一项实际应用是在改变铃声中观察到的中观察到的。
无序集合与支撑大多数现代数学的非常通用且普遍存在的数据结构一致，即集合论。我认为 Python 中的无序集合是很好的。
另请参阅扩展此主题的相关帖子：