Почему при использовании 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% же. Почему производительность снижается, если передается ключевая функция? Для сравнения: sorted замедляется примерно на 30% с теми же исходными данными и keyfunc.

Предположим, что итерируемый объект имеет N элементов. Не важно, будет выполняться sorted или nlargest, ключевая функция будет вызываться N раз. В случае сортировки накладные расходы над другими операциями составляют примерно N * log2(N). Но при выполнении nlargest от k элементов, только приблизительно N * log2(k), что намного меньше, если k существенно меньше N.

В примере выше N = 1234567 и k = 10, поэтому соотношение сортировки и nlargest над другими операциями примерно равно:

>>> log2(1234567) / log2(10)
6,0915146640862625

Близость к значению 6 — случайное совпадение. Важен качественный вопрос: если k значительно меньше N, накладные расходы в связи с использованием ключевой функции гораздо более значительны для nlargest, чем для сортировки случайно упорядоченных данных.

Фактически это значительно занижает относительные накладные расходы для nlargest, потому что в последнем вызывается heapreplace сложностью O (log2(k)) только в том случае, когда следующий элемент больше, чем самый большой k-й из уже просмотренных. В большинстве случаев это не так, и поэтому цикл на такой итерации представляет собой почти чистые накладные расходы: вызывает ключевую функцию Python-уровня, чтобы определить, что результат не представляет интереса.


По материалам Тима Петерса.