Set 与 frozenset 性能

Question

我正在修补 Python 的 set 和 frozenset 集合类型。

最初，我假设 frozenset 会提供比 set 更好的查找性能，因为它是不可变的，因此可以利用存储项目的结构。

然而，关于以下实验，情况似乎并非如此：

import random
import time
import sys

def main(n):
    numbers = []
    for _ in xrange(n):
        numbers.append(random.randint(0, sys.maxint))
    set_ = set(numbers)
    frozenset_ = frozenset(set_)

    start = time.time()
    for number in numbers:
        number in set_
    set_duration = time.time() - start

    start = time.time()
    for number in numbers:
        number in frozenset_
    frozenset_duration = time.time() - start

    print "set      : %.3f" % set_duration
    print "frozenset: %.3f" % frozenset_duration


if __name__ == "__main__":
    n = int(sys.argv[1])
    main(n)

我使用 CPython 和 PyPy 执行了这段代码，结果如下：

> pypy set.py 100000000
set      : 6.156
frozenset: 6.166

> python set.py 100000000
set      : 16.824
frozenset: 17.248

似乎 frozenset 在 CPython 和 PyPy 中的查找性能实际上较慢。有谁知道为什么会这样？我没有研究实现。

Answer 1

frozenset 和 set 实现在很大程度上是共享的； set 只是添加了变异方法的 frozenset，具有完全相同的哈希表实现。见 Objects/setobject.c source file; the top-level PyFrozenSet_Type definition shares functions with the PySet_Type definition.

这里没有针对 frozenset 的优化，因为在测试成员资格时不需要计算 in 和 frozenset 中的项目的哈希值。您用来测试 against 集合的项目仍然需要计算它们的哈希值，以便在集合哈希表中找到正确的位置，以便您可以进行相等性测试。

因此，您的计时结果可能由于系统上的其他进程运行而关闭；您测量了挂钟时间，没有禁用 Python 垃圾收集，也没有重复测试相同的东西。

尝试运行使用 timeit module 进行测试，其中一个值来自 numbers 而另一个不在集合中：

import random
import sys
import timeit

numbers = [random.randrange(sys.maxsize) for _ in range(10000)]
set_ = set(numbers)
fset = frozenset(numbers)
present = random.choice(numbers)
notpresent = -1
test = 'present in s; notpresent in s'

settime = timeit.timeit(
    test,
    'from __main__ import set_ as s, present, notpresent')
fsettime = timeit.timeit(
    test,
    'from __main__ import fset as s, present, notpresent')

print('set      : {:.3f} seconds'.format(settime))
print('frozenset: {:.3f} seconds'.format(fsettime))

每个测试重复 100 万次并产生：

set      : 0.050 seconds
frozenset: 0.050 seconds

Answer 2

两种不同数据类型的原因不是为了性能，而是功能。因为 frozensets 是不可变的，所以它们可以用作字典中的键。集不能用于此目的。

Set 与 frozenset 性能

Set vs. frozenset performance

python

performance

set

frozenset