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

Question

使用keyfunc时,性能大幅下降heapq.nlargest:

>>> 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调用make的数量nlargest与输入的大小呈预期对数关系.具体来说,nlargest(10, x)除了前10个元素之外x,元素x[i]有10/(i+1)可能位于前10个元素中l[:i+1],这是堆替换调用所必需的条件.通过期望的线性,预期的heapreplace调用数是这些概率的总和,并且该和是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倍!

Answer 2

说你的iterable有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被称为后者只有当一个元素是比较大的k"日最大迄今为止看到的.大部分时间它不是,因此这种迭代的循环几乎是纯粹的开销,调用Python级别的键函数只是为了发现结果不感兴趣.

但是,量化这一点超出了我的意义; 例如,在Python 3.6.5下的我的Win10盒子里,我只看到你的代码中的时序差异小于3倍.这并不让我感到惊讶 - 调用Python级别的函数比戳戳要贵得多列表迭代器并进行整数比较(两者都是"C速度").