Как "ключевые" функции более эффективны, чем функции сравнения в отсортированном Python?

Question

В видео Преобразование кода в красивый идиоматический Python (ссылка начинается в 10:07), докладчик говорит, что использование key вместо функции сравнения cmp для сортировки более эффективно.Перефразируя: он утверждает, что из-за сравнения O (nlog (n)) функция сравнения будет вызываться 20 раз для списка элементов 1м (log2 (1m) ~ 20), тогда как использование key лучше, потому что оно вызываетсяровно один раз за ключ.

Я понимаю его мысль о том, что использование key более читабельно, но я не понимаю, как он определил, что он вызывается один раз для каждого ключа.Я бы подумал, что под капотом функция сортировки, имеющая параметр key, будет выглядеть примерно так:

def sort(sequence, key=None):
    if key is None:
        key = lambda x: x
    def compare(first, second):
        if key(first) < key(second): return -1
        if key(second) < key(first): return 1
        return 0
    # ... implement sorting algorithm

И, таким образом, будет одинаковая сложность по времени, если мы будем использовать ключевую функциюили функция сравнения.

Как функция ключа вызывается только один раз для каждого элемента, если есть O (nlog (n)) сравнений?Это Timsort подробности реализации?

Редактировать:

Чтобы ответить на комментарий с просьбой привести пример:

В python2, функция sorted принимает аргумент cmp, что-то вроде этого:

def compare(first, second):
    if len(first) < len(second): return -1
    if len(second) < len(first): return 1
    return 0

sorted(my_list, cmp=compare)

Однако вы также можете передать ключевую функцию, если хотите.Итак, для достижения того же эффекта, что и выше, вы должны сделать следующее:

sorted(my_list, key=len)

В видео автор утверждает, что второй вариант более эффективен, чем первый.

Answer 1

До того, как key и list.sort были напрямую поддержаны *1001*, существовала идиома, которая позволяла вам в любом случае получать его преимущества.Идиома называлась «Украсить-Сортировать-Украсить» (и, по-видимому, она также известна как Шварцевское преобразование ).

Вот как это работает:

def sort_with_key(data, keyfunc):
    decorated_data = [(keyfunc(x), i, x) for i, x in enumerate(data)]
    decorated_data.sort()
    return [x for key, i, x in decorated_data]

Тристроки функции соответствуют трем частям имени идиомы.

1. Первая строка «украшает» данные, создавая кортеж, объединяющий значение ключа и индекс прерывателя связей с каждым элементом извход.Это единственное место, где вызывается ключевая функция, поэтому есть только O(len(data)) вызовы.

2. Второй шаг прост.Мы сортируем оформленный список кортежей, используя метод сравнения по умолчанию.Поскольку кортежи сравниваются лексикографически, для большинства пар элементов необходимо сравнивать только ключевые значения.Если между значениями ключей есть какие-либо связи, индексное значение в середине кортежа нарушит его (всегда таким образом, что элементы остаются в том же относительном порядке, в котором они находились в списке ввода, что делает его устойчивой сортировкой).).Элементы из data никогда не сравниваются, поскольку значения разрешения конфликтов всегда будут различаться (так как они являются индексами исходного списка).

3. Последние шаги просты для понимания какЧто ж.Мы просто отбрасываем значения ключей и разрешения конфликтов, создавая список, содержащий только исходные элементы, в недавно отсортированном порядке.

Когда параметр key был добавлен к list.sort иsorted, это сделало функции сортировки способными сделать все это автоматически.Я не знаю точных деталей о том, как хранится значение ключа (вы можете прочитать исходный код , если вы действительно должны это знать), но его эффекты такие же, как и в DSU.Функция ключа вызывается один раз для каждого значения в списке ввода, и ее результаты сохраняются для последующего многократного сравнения, когда происходит фактическая сортировка.

Answer 2

Из документации :

Начиная с Python 2.4, list.sort () и sorted () добавили ключевой параметр, чтобы указать функцию, которая будет вызываться в каждом спискеэлемент до сравнения.

Обратите внимание на слово до : ключи вычисляются не вместо вызова cmp, но до этого.Для вычисления ключей требуется O (n), а для сортировки - O (n log (n)), поэтому общая сложность сортировки по-прежнему составляет O (n log (n)).

Отредактировано

Докладчик предлагает рассчитать длину строки перед сортировкой (через keys), что действительно требует n вызовов len.Если во время сортировки вызывается одна и та же функция (через cmp), количество вызовов будет не менее 2 n log (n).

Короче говоря, число сравнений одинаково в обоих случаях,но количество звонков на len отличается.