时间戳

首页 > 解决方案 > 为什么 Python 集不保留插入顺序？

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

问题描述

最近我惊讶地发现，虽然 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 制作内置集合的同时保留顺序。

标签： pythonsetcpython

解决方案

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

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

理论上可以将 CPython 的 set 实现更改为类似于 compact dict，但在实践中存在缺陷，著名的核心开发人员反对进行这样的更改。

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

——吉多·范罗森

集合使用不同的算法，该算法不能修改为保留插入顺序。如果需要顺序，成套操作就会失去灵活性和优化。集合数学是根据无序集合定义的。简而言之，集合排序不是在不久的将来。

——雷蒙德·海廷格

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

总而言之，要点是：不同的使用模式（插入排序字典，如 **kwargs很有用，对集合不太有用），压缩集合的空间节省不太显着（因为只有键 + 哈希数组来致密，如与键 + 哈希 + 值数组相反），并且上述集合当前使用的线性探测优化与紧凑的实现不兼容。

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

2016 年 9 月 14 日下午 3:50，Eric Snow 写道：

然后，我会对集合做同样的事情。

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

这是正确的。在人们开始疯狂之前，这里有一些关于这个主题的想法。

  • 对于紧凑型字典，空间节省是一种净赢，索引消耗的额外空间和键/值/哈希数组的过度分配被提高的键/值/哈希数组密度所抵消。然而，对于集合，网络就不太有利了，因为我们仍然需要索引和过度分配，但只能通过仅致密三个数组中的两个来抵消空间成本。换句话说，当您为键、值和散列浪费空间时，压缩更有意义。如果你失去了这三个中的一个，它就不再具有吸引力。

  • 集合的使用模式与字典不同。前者有更多的命中或未命中查找。后者往往具有较少的缺失键查找。此外，对于 set-to-set 操作的一些优化使得很难在不影响性能的情况下保留 set ordering。

  • 我寻求其他途径来提高集合性能。我没有使用压缩（这并没有太多的空间优势，并且会产生额外的间接成本），而是添加了线性探测以降低冲突成本并提高缓存性能。这种改进与我提倡的字典压缩方法不兼容。

  • 目前，对字典的排序副作用是无法保证的，所以现在开始坚持集合也是有序的还为时过早。文档已经链接到创建 OrderedSet 的配方 ( https://code.activestate.com/recipes/576694/ )，但似乎吸收率几乎为零。此外，现在 Eric Snow 为我们提供了一个快速的 OrderedDict，从 MutableSet 和 OrderedDict 构建 OrderedSet 比以往任何时候都容易，但我再次没有观察到任何真正的兴趣，因为典型的 set-to-set 数据分析并不是真的需要或关心订购。同样，快速成员资格测试的主要用途是与订单无关。

  • 也就是说，我确实认为有空间向 PyPI 添加替代集实现。特别是，对于可排序数据有一些有趣的特殊情况，可以通过比较整个键范围来加速集合到集合的操作（参见 https://code.activestate.com/recipes/230113-implementation-of-设置使用排序列表 作为起点）。IIRC，PyPI 已经有类似集合的布隆过滤器和杜鹃散列的代码。

  • 我理解将一个主要代码块接受到 Python 核心中是令人兴奋的，但除非我们确定它是有保证的，否则不应打开闸门来参与对其他数据类型的更重大的重写。

——雷蒙德·海廷格

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

推荐阅读