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

Question

Резкое снижение производительности при использовании ключевой функции в 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, но в противном случае реализация выглядит более или менее одинаково.

Почему производительность снижается при использовании ключевой функции?Это происходит только из-за дополнительных накладных расходов на вызов функции, или алгоритм каким-то образом кардинально изменился с помощью ключевой функции?

Для сравнения, sorted занимает около 30% попадания с теми же данными и лямбда-выражением.

Answer 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»).

Answer 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.

При случайном вводе количество вызовов, заменяемых в heap 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) требуется чуть более сложный анализ.)

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