主页 / coding / 问题 / 79352669
Accepted
Stefan Pochmann
Asked: 2025-01-13 23:24:07 +0800 CST

为什么 {2,3,10} 和 {x,3,10} (x=2) 的顺序不同？

  • 772

集合是无序的，或者说它们的顺序是一个实现细节。我对这个细节很感兴趣。我看到了一个让我惊讶的案例：

print({2, 3, 10})
x = 2
print({x, 3, 10})

输出（在线尝试！）：

{3, 10, 2}
{10, 2, 3}

尽管相同的元素以相同的顺序写入，但它们的排序却不同。这是怎么发生的？这是故意为之吗？例如，为了优化查找速度？

我的sys.version和sys.implementation：

3.13.0 (main, Nov  9 2024, 10:04:25) [GCC 14.2.1 20240910]
namespace(name='cpython', cache_tag='cpython-313', version=sys.version_info(major=3, minor=13, micro=0, releaselevel='final', serial=0), hexversion=51183856, _multiarch='x86_64-linux-gnu')
python

1 个回答

  1. Best Answer

    它是由以下几个因素决定的：

    1. 哈希桶冲突 - 对于最小set大小，8（CPython 的实现细节）2和10在它们的缩减哈希码上发生冲突（同样是实现细节，是2和10；mod 8，它们都是 2）。无论哪个先插入，都将“获胜”并获得桶索引 2，另一个将被探测操作移动。探测操作（同样是 CPython 实现细节）首先检查线性相邻的桶是否有空桶（因为它通常会找到一个，而更好的内存局部性可以提高缓存性能），并且只有在没有找到空桶时，它才会开始随机跳跃算法来查找空桶（它不能进行纯线性探测，因为这会很容易触发将set操作从摊销平均情况更改O(1)为的病态情况O(n)）。

    2. 编译时优化：在现代 CPython 中，长度至少为三个元素的常量文字的sets 和s 在编译时被构造为不可变容器（分别为和）。在运行时，它会构建一个空的/ ，然后使用不可变容器对其进行s/ ，而不是对每个元素执行单独的加载和s/ 。这意味着当您使用 构建时，您实际上是在执行（使用从缓存中提取的 ），而是通过在堆栈上加载 和 来构建的，然后作为单个操作构建。listfrozensettuplesetlistupdateextendaddappends = {2, 3, 10}s = set()s.update(frozenset({2, 3, 10}))frozensets = {x, 3, 10}x310set

    这两个意味着您实际上是以不同的方式构建它；{x, 3, 10}插入2，然后3，然后10，因此存储桶2和3已填满，并10重新定位（探测策略显然将其放在存储桶0或1中，在存储桶之前2）。当您执行时{2, 3, 10}，在编译时它会创建一个frozenset({3, 10, 2})，然后在运行时，它会创建空的set，然后通过迭代来更新它frozenset，这已经对元素进行了重新排序，因此现在它们不再按2、、顺序添加，并且“首选”存储桶的竞争由不同的元素赢得。310

    综上所述，的行为{x, 3, 10}等同于：

    s = set()
s.add(x)
s.add(3)
s.add(10)

    可以预见的是，它将桶 2 和 3 分配给2它们3自己，同时10被转移到桶 0 或 1。

    相比之下，{2, 3, 10}构建一个（注意：在转换为之后，frozenset({3, 10, 2})它的顺序是这样的；如果您尝试运行该行，您会看到不同的顺序），然​​后用它创建一个空的。有一个优化的代码路径可以从另一个/填充一个空的，它只是直接复制内容（而不是逐个迭代和插入），因此缓存中的顺序在从它创建的每个缓存中都保留，就像您运行：frozensetprintupdatesetsetsetfrozenset{3, 10, 2}frozensetset

    s = set()
s.update(frozenset({2, 3, 10}))

    但性能更佳（因为frozenset在编译时创建一次，并且每次set初始化时都廉价地加载）。

    • 19

相关问题