您好, 欢迎来到 !    登录 | 注册 | | 设为首页 | 收藏本站

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

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

集合和字典针对不同的用例进行了优化。 对于dicts,查找成本是最关键的操作,而密钥更可能出现。对于集合,元素的存在或不存在是事先未知的,因此集合实现需要针对发现和未发现的情况进行优化。同样,对通用集合操作(??例如联合和相交)的一些优化使得在不降低性能的情况下很难保留集合顺序。

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

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

集保持无序。(为什么?使用方式不同。另外,实现方式也不同。)

Guido van Rossum

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

雷蒙德·海廷格Raymond Hettinger)

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

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

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

2016年9月14日下午3:50,埃里克·斯诺(Eric SNow)写道:

然后,我将对集合进行相同的操作。

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

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

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

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

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

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

–雷蒙德·海廷格(Raymond Hettinger)

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

python 2022/1/1 18:37:55 有256人围观

撰写回答


你尚未登录,登录后可以

和开发者交流问题的细节

关注并接收问题和回答的更新提醒

参与内容的编辑和改进,让解决方法与时俱进

请先登录

推荐问题


联系我
置顶