使用冻结集上的元组作为字典的键是否存在性能差异？

Question

我有一个脚本,它使用由两个变量组成的键对字典进行多次调用.我知道我的程序将以相反的顺序再次遇到这两个变量,这使得将密钥存储为元组是可行的.(为行和列创建具有相同标签的矩阵)

因此,我想知道在字典键的冻结集上使用元组是否存在性能差异.

Answer 1

在一个快速测试中,显然它的差异可以忽略不计.

python -m timeit -s "keys = list(zip(range(10000), range(10, 10000)))" -s "values = range(10000)" -s "a=dict(zip(keys, values))" "for i in keys:" "  _ = a[i]"
1000 loops, best of 3: 855 usec per loop

python -m timeit -s "keys = [frozenset(i) for i in zip(range(10000), range(10, 10000))]" -s "values = range(10000)" -s "a=dict(zip(keys, values))" "for i in keys:" "  _ = a[i]"
1000 loops, best of 3: 848 usec per loop

我真的会选择代码中其他地方最好的东西.

Answer 2

没有做过任何测试,我有一些猜测.对于frozensets,cpython 在计算后存储哈希值; 此外,迭代任何类型的集合会产生额外的开销,因为数据被稀疏地存储.在一个2项集合中,这会对第一个哈希造成显着的性能损失,但可能会使第二个哈希非常快 - 至少在对象本身是相同的时候.(即不是一个新的但等效的冷冻集.)

对于tuples,cpython不存储哈希值,而是每次都计算它.因此,对于frozensets来说,重复散列可能会稍微便宜一些.但对于这么短的元组,可能几乎没有区别; 甚至可能非常短的元组会更快.

Lattyware目前的时间安排与我的推理方式相当吻合; 见下文.

为了测试我对哈希新旧对抗的不对称性的直觉,我做了以下几点.我相信时间上的差异完全是由于额外的哈希时间.顺便说一下,这是非常微不足道的:

>>> fs = frozenset((1, 2))
>>> old_fs = lambda: [frozenset((1, 2)), fs][1]
>>> new_fs = lambda: [frozenset((1, 2)), fs][0]
>>> id(fs) == id(old_fs())
True
>>> id(fs) == id(new_fs())
False
>>> %timeit hash(old_fs())
1000000 loops, best of 3: 642 ns per loop
>>> %timeit hash(new_fs())
1000000 loops, best of 3: 660 ns per loop

请注意我之前的时间错误; 使用and创建了上述方法避免的时序不对称性.这种新方法在这里产生元组的预期结果 - 可忽略的时序差异:

>>> tp = (1, 2)
>>> old_tp = lambda: [tuple((1, 2)), tp][1]
>>> new_tp = lambda: [tuple((1, 2)), tp][0]
>>> id(tp) == id(old_tp())
True
>>> id(tp) == id(new_tp())
False
>>> %timeit hash(old_tp())
1000000 loops, best of 3: 533 ns per loop
>>> %timeit hash(new_tp())
1000000 loops, best of 3: 532 ns per loop

并且,恩典,将预构建的冻结集的哈希时间与预先构造的元组的哈希时间进行比较:

>>> %timeit hash(fs)
10000000 loops, best of 3: 82.2 ns per loop
>>> %timeit hash(tp)
10000000 loops, best of 3: 93.6 ns per loop

Lattyware的结果看起来更像是因为它们是新旧frozensets的平均结果.(它们会在创建字典时对每个元组或冻结集进行两次哈希处理,一次访问它.)

所有这一切的结果是它可能无关紧要,除了我们这些喜欢在Python的内部挖掘和测试遗忘的人.