集合和字典针对不同的用例进行了优化。集合的主要用途是快速成员测试,不考虑顺序。对于字典来说,查找操作的成本是最关键的,而且键更有可能存在。对于集合来说,元素的存在与否事先是不知道的,因此集合的实现需要同时优化找到和未找到的情况。此外,一些常见集合操作(如并集和交集)的优化使得保留集合顺序而不降低性能变得困难。
虽然这两种数据结构都是基于哈希的,但普遍存在一种误解,即集合只是使用空值实现的字典。即使在CPython 3.6之前的紧凑字典实现之前,集合和字典的实现已经有了显著的差异,并且代码复用很少。例如,字典使用随机探测,而集合使用线性探测和开放寻址的组合,以提高缓存局部性。初始线性探测(在CPython中默认为9步)将检查一系列相邻的键/哈希对,通过减少哈希冲突处理的成本来提高性能-连续内存访问比分散的探测更便宜。
从理论上讲,将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。