为什么使用按键功能这么慢？

Question

在 heapq.nlargest 中使用 keyfunc 时会严重影响性能：

>>> from random import random
>>> from heapq import nlargest
>>> data = [random() for _ in range(1234567)]
>>> %timeit nlargest(10, data)
30.2 ms ± 1.19 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)
>>> %timeit nlargest(10, data, key=lambda n: n)
159 ms ± 6.32 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

我预计会有少量额外费用，大概是 30%，而不是 400%。这种退化似乎可以在几种不同的数据大小上重现。您可以在源代码中看到 if key is None 的特殊情况处理，但其他实现看起来或多或少相同。

为什么使用按键功能会导致性能下降如此严重？仅仅是因为额外的函数调用开销，还是通过使用 keyfunc 从根本上改变了算法？

相比之下，sorted 使用相同的数据和 lambda 约占 30%。

Answer 1

多次调用 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 或 sorted 进行比较，而不是将开销作为基数的百分比进行比较。

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)

如您所见，key 调用的成本约占此输入上使用此键和 sorted 的开销的一半，其余开销可能来自在排序本身中混洗更多数据。

您可能想知道 nlargest 如何设法为每个元素做这么少的工作。对于无键情况，大多数迭代发生在以下循环中：

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 个候选元素。在极少数需要替换堆元素的情况下，这只会让更多元素更难通过调用 heapreplace.

所需的标准

在随机输入上，heapreplace 调用的次数 nlargest 预期与输入大小成对数。具体来说，对于 nlargest(10, x)，除了 x 的前 10 个元素外，元素 x[i] 有 10/(i+1) 的概率在 l[:i+1] 的前 10 个元素中，这是 heapreplace 调用的必要条件。根据期望的线性，heapreplace 调用的期望次数是这些概率的总和，并且该总和是 O(log(len(x)))。（此分析适用于将 10 替换为任何常量，但需要对 nlargest(n, l) 中的变量 n 进行稍微复杂的分析。）

排序输入的性能故事会非常不同，其中每个元素都会通过 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 多倍！

Answer 2

假设您的可迭代对象有 N 个元素。无论是排序还是做nlargest，关键函数都会被调用N次。排序时，该开销大部分被埋没在大约 N * log2(N) 其他操作之下。但是在做nlargest个k项的时候，其他的操作大概只有N * log2(k)个，当k比N小很多的时候就小很多了。

在你的例子中，N = 1234567 和 k = 10，所以其他操作的比率，排序超过 nlargest，大致是：

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

这接近 6 纯属巧合 ;-) 重要的是定性点：使用键函数的开销对于 nlargest 比对随机排序的数据排序要重要得多，前提是 k 比 N.

小得多

事实上，这大大低估了 nlargest 的相对负担，因为 O(log2(k)) heapreplace 仅在下一个元素大于 [=16] 时才会在后者中调用=]'迄今为止最大的。大多数时候不是这样，因此这种迭代的循环几乎是纯粹的开销，调用 Python 级关键函数只是为了发现结果并不有趣。

不过，量化这超出了我的范围；例如，在我的 Python 3.6.5 下的 Win10 机器上，我只看到你的代码中的时间差异略小于 3 的因数。这并不让我感到惊讶 - 调用 Python- level 函数 比查找列表迭代器和进行整数比较（两者都 "at C speed"）昂贵 。

为什么使用按键功能这么慢？

Why is using a key function so much slower?

python

heap

python-3.x