我有一个脚本，它使用由两个变量组成的键对字典进行多次调用。我知道我的程序将以相反的顺序再次遇到这两个变量，这使得将密钥存储为元组是可行的。（为行和列创建具有相同标签的矩阵）
因此，我想知道使用元组而不是冻结集作为字典键是否存在性能差异。
问问题
3526 次
4 回答
11
在快速测试中，显然它产生的差异可以忽略不计。
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
我真的会选择你代码中其他地方最好的东西。
于 2012-05-01T13:43:23.607 回答
8
没有做任何测试，我有一些猜测。对于frozensets，cpython存储计算后的哈希值；此外，迭代任何类型的集合都会产生额外的开销，因为数据存储稀疏。在 2 项集合中，这会对第一个散列造成显着的性能损失，但可能会使第二个散列非常快——至少当对象本身相同时。（即不是一个新的但等效的frozenset。）
对于tuples，cpython不存储hash，而是每次都计算。因此，使用 freezesets重复哈希可能会稍微便宜一些。但是对于这么短的元组，可能几乎没有区别；甚至有可能非常短的元组会更快。
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
请注意，我之前的时间安排是错误的；usingand创建了上述方法避免的时序不对称。这种新方法在这里为元组产生了预期的结果——时间差可以忽略不计：
>>> 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
而且，致命一击，将预先构建的frozenset的哈希时间与预先构建的元组的哈希时间进行比较：
>>> %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 结果的平均值。（他们对每个元组或 freezeset 进行两次哈希处理，一次是创建字典，一次是访问它。）
所有这一切的结果是，它可能无关紧要，除了我们这些喜欢挖掘 Python 内部结构和测试事物以被遗忘的人。
于 2012-05-01T13:49:01.443 回答
2
虽然您可以使用它timeit来查找（我鼓励您这样做，如果没有其他原因，只是为了了解它是如何工作的），最后几乎可以肯定它无关紧要。
frozensets 专门设计为可散列的，所以如果他们的散列方法是线性时间，我会感到震惊。只有当您需要在实时应用程序中在很短的时间内完成固定（大量）数量的查找时，这种微优化才有意义。
更新：查看对 Lattyware 答案的各种更新和评论 - 花了很多集体努力（好吧，相对而言），以消除混杂因素，并表明两种方法的性能几乎相同。性能命中不是他们假设的地方，在你自己的代码中也是一样的。
编写代码以工作，然后分析以查找热点，然后应用算法优化，然后应用微优化。
于 2012-05-01T13:44:35.483 回答
1
最佳答案（Gareth Latty's）似乎已经过时了。在 python 3.6 上，对 freezeset 进行散列似乎要快得多，但这在很大程度上取决于您要散列的内容：
sjelin@work-desktop:~$ ipython
Python 3.6.9 (default, Nov 7 2019, 10:44:02)
In [1]: import time
In [2]: def perf(get_data):
...: tuples = []
...: sets = []
...: for _ in range(10000):
...: t = tuple(get_data(10000))
...: tuples.append(t)
...: sets.append(frozenset(t))
...:
...: start = time.time()
...: for s in sets:
...: hash(s)
...: mid = time.time()
...: for t in tuples:
...: hash(t)
...: end = time.time()
...: return {'sets': mid-start, 'tuples': end-mid}
...:
In [3]: perf(lambda n: range(n))
Out[3]: {'sets': 0.32627034187316895, 'tuples': 0.22960591316223145}
In [4]: from random import random
In [5]: perf(lambda n: (random() for _ in range(n)))
Out[5]: {'sets': 0.3242628574371338, 'tuples': 1.117497205734253}
In [6]: perf(lambda n: (0 for _ in range(n)))
Out[6]: {'sets': 0.0005457401275634766, 'tuples': 0.16936826705932617}
In [7]: perf(lambda n: (str(i) for i in range(n)))
Out[7]: {'sets': 0.33167099952697754, 'tuples': 0.3538074493408203}
In [8]: perf(lambda n: (object() for _ in range(n)))
Out[8]: {'sets': 0.3275420665740967, 'tuples': 0.18484067916870117}
In [9]: class C:
...: def __init__(self):
...: self._hash = int(random()*100)
...:
...: def __hash__(self):
...: return self._hash
...:
In [10]: perf(lambda n: (C() for i in range(n)))
Out[10]: {'sets': 0.32653021812438965, 'tuples': 6.292834997177124}
其中一些差异足以在性能环境中产生影响，但前提是散列实际上是您的瓶颈（几乎从未发生过）。
我不知道是什么让frozensets几乎总是在~0.33秒内运行，而元组在0.2到6.3秒之间运行。需要明确的是，使用相同的 lambda 重新运行永远不会改变超过 1% 的结果，所以它不像是有错误。
在 python2 中结果是不同的，并且两者通常彼此更接近，这可能是 Gareth 没有看到相同差异的原因。
于 2020-12-20T03:55:21.327 回答