为什么使用键函数要慢得多?

说你的Iterable有 N 元素。不管是分类还是做 nlargest ,将调用键函数 n 时代。在分类时,这些开销基本上被埋没在 N * log2(N) 其他行动。但是在做的时候 最大的 属于 k 物品,只有大约 N * log2(k) 其他操作,当 K 比 n .

在你的例子中, N = 1234567 和 k = 10 ,所以其他操作的比率,排序 最大的 ,大致是:

>>> log2(1234567) / log2(10)
6.0915146640862625

这接近6是纯粹的巧合;-)这是重要的定性点:使用键函数的开销对于 最大的 而不是对随机排序的数据进行排序,前提是 K 比 n .

事实上,这大大低估了 最大的 ,因为 O(log2(k)) heapreplace 只有当下一个元素大于 K 是迄今为止见过的最大的。大多数情况下不是这样,因此这样一个迭代的循环几乎是纯粹的开销,调用python级别的键函数只是为了发现结果并不有趣。

不过,我无法量化它;例如,在python 3.6.5下的win10框中,我只看到代码中的时间差小于3的一个因子。这并不奇怪-调用python级别的函数是 许多的 比插入列表迭代器和进行整数比较(都是“以C速度”)更昂贵。

额外的通话费用 lambda n: n 很多次真的很贵。

In [17]: key = lambda n: n

In [18]: x = [random() for _ in range(1234567)]

In [19]: %timeit nlargest(10, x)
33.1 ms ± 2.71 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)

In [20]: %timeit nlargest(10, x, key=key)
133 ms ± 3.7 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)

In [21]: %%timeit
    ...: for i in x:
    ...:     key(i)
    ...: 
93.2 ms ± 978 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)

In [22]: %%timeit
    ...: for i in x:
    ...:     pass
    ...: 
10.1 ms ± 298 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)

如你所见,打电话的费用 key 在所有元素上几乎占了全部开销。

关键评估同样昂贵 sorted ,但由于排序的总工作成本更高,因此键调用的开销占总开销的百分比较小。您应该将使用密钥的绝对开销与 nlargest 或 排序的 ,而不是开销占基数的百分比。

In [23]: %timeit sorted(x)
542 ms ± 13.5 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

In [24]: %timeit sorted(x, key=key)
683 ms ± 12.1 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

如你所见 钥匙 调用约占使用此密钥的开销的一半 排序的 在这个输入上,其余的开销可能来自于在排序本身中重新排列更多数据的工作。

你可能想知道 最大的 每一个元素都能做那么少的工作。对于无键情况,大多数迭代都发生在以下循环中:

for elem in it:
    if top < elem:
        _heapreplace(result, (elem, order))
        top = result[0][0]
        order -= 1

或者对于带钥匙的情况:

for elem in it:
    k = key(elem)
    if top < k:
        _heapreplace(result, (k, order, elem))
        top = result[0][0]
        order -= 1

关键的认识是 top < elem 和 top < k 几乎从来没有人拿过树枝。一旦算法找到了10个相当大的元素,剩下的大部分元素都将小于当前的10个候选元素。在很少需要替换堆元素的情况下,这只会使进一步的元素更难通过需要调用的bar heapreplace .

在随机输入中,heapreplace调用的数量 最大的 make在输入大小上应为对数。特别是 nlargest(10, x) ,除了前10个元素 x 元素 x[i] 有一个 10/(i+1) 进入前十名的概率 l[:i+1] ,这是heapreplace调用所必需的条件。根据期望的线性关系,heapplace调用的期望数量是这些概率的和,这个和是o(log(len(x)))。(这个分析用10代替任何常数,但是对于一个变量需要稍微复杂一点的分析。) n 在里面 nlargest(n, l) )

对于排序后的输入,每个元素都将通过 if 检查:

In [25]: sorted_x = sorted(x)

In [26]: %timeit nlargest(10, sorted_x)
463 ms ± 26 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

比未分类的箱子贵10倍多!