Почему использование ключевой функции намного медленнее?

При использовании keyfunc в heapq.nlargest наблюдается резкое 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 занимает около 30% попадания с теми же данными и лямбдой.

Ответ 1

Предположим, что ваш итеративный элемент имеет 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, чтобы обнаружить, что результат не интересен.

Количественная оценка, которая выше меня; например, в моем блоке Win10 под Python 3.6.5, я вижу только разницу во времени в вашем коде немного меньше, чем в 3 раза. Это меня не удивляет - вызов функции уровня на Python намного дороже, чем ковычка итератор списка и сравнение целого числа (оба "на скорости C").

Ответ 2

Дополнительные накладные расходы на вызов 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.

На случайном входе количество вызовов nlargest делает логарифмическим по размеру ввода. В частности, для nlargest(10, x), помимо первых 10 элементов x, элемент x[i] имеет вероятность 10/(i+1) быть в первых 10 элементах l[:i+1], который является условием, необходимым для вызова heapreplace. По линейности математического ожидания ожидаемое количество вызовов в heapreplace является суммой этих вероятностей, и эта сумма равна O (log (len (x))). (Этот анализ выполняется с заменой 10 на любую константу, однако для переменной n в nlargest(n, l) требуется немного более сложный анализ 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 раз дороже, чем несортированный случай!