在 Python 中将集合转换为冻结集的复杂性

Question

在 Python 中“冻结”集合的计算复杂度是多少？

例如，第二行是否在

a = {1,2,3}
b = frozenset(a)

需要 O(n) 时间？或者它只是在恒定时间内创建的“视图”？

Answer 1

b

不是

a

的视图。您可以通过

id

检查：

a = {1, 2, 3}
b = a

id(a) == id(b)  # True

b = frozenset({1, 2, 3})

id(a) == id(b)  # False

因此，

b

的变化将不会反映在

a

中。当然，您可以自己测试一下。由于

frozenset

采用可迭代作为参数，因此它必须迭代每个参数。这是一个 O(n) 的过程。

顺便说一句，

frozenset

没有什么特别的，即使从

set

创建

set

也具有 O(n) 时间复杂度：

for i in [10**5, 10**6, 10**7]:
    a = set(range(i))
    %timeit set(a)

100 loops, best of 3: 3.33 ms per loop
10 loops, best of 3: 30.2 ms per loop
1 loop, best of 3: 421 ms per loop   

Answer 2

虽然复杂性没有改变，但运行时有所不同，具体取决于 freezeset 初始值设定项的输入是迭代器、列表、元组还是集合。

我在 ZSH 中运行了以下 shell 脚本：

for i in 5 6 7
do
    for f in '' 'list' 'tuple' 'set'
    do
        echo "i=$i f=$f"
        python -m timeit -s "x=$f(range(10**$i))" 'frozenset(x)'
    done
done

使用 Python 3.11.2 在我的笔记本电脑上产生以下结果：

i=5 f=
100 loops, best of 5: 2.37 msec per loop
i=5 f=list
200 loops, best of 5: 1.31 msec per loop
i=5 f=tuple
200 loops, best of 5: 1.41 msec per loop
i=5 f=set
500 loops, best of 5: 609 usec per loop
i=6 f=
10 loops, best of 5: 25.6 msec per loop
i=6 f=list
20 loops, best of 5: 14.4 msec per loop
i=6 f=tuple
20 loops, best of 5: 14.5 msec per loop
i=6 f=set
50 loops, best of 5: 5.97 msec per loop
i=7 f=
1 loop, best of 5: 256 msec per loop
i=7 f=list
2 loops, best of 5: 144 msec per loop
i=7 f=tuple
2 loops, best of 5: 148 msec per loop
i=7 f=set
5 loops, best of 5: 76.4 msec per loop

从输入集初始化冻结集始终是最快的；从列表和元组初始化是绑定的；直接从

range

迭代器初始化是最慢的（可能是因为它包括迭代，这是在其他迭代器的设置过程中发生的）。

这对我来说意味着 freezeset 能够重用集合的更多状态 - 即使它必须制作副本以保持不可变。对于其他可迭代类型，frozenset 必须从头开始构建其状态。