Сортировки: key vs cmp

    При сортирование в Python 2 есть как минимум два способа это сортирование «настроить»: это параметры key и cmp. Первый был добавлен только в Python 2.4, а второй был удален в Python 3.0. Эти факты как-бы наводят на мысль что key действительно лучше. Кто с этим не согласен или не уверен — прошу под кат.

    Сначала небольшой экскурс в документацию, чтобы все не выглядело слишком сумбурно.

    Для сортировки в Python обычно используют или built-in `sorted`, или `list.sort`. На самом деле вызов
    sorted(iterable, **kwargs) 
    эквивалентен коду
    lst = list(iterable); lst.sort(**kwargs); lst 
    так что дальше сосредоточимся именно на `list.sort`.

    `list.sort` принимает три необязательных параметра: `key` — функция (на самом деле любой callable объект), которая принимает элемент списка и возвращает объект, который будет использоваться при сравнения во время сортировки вместо оригинального элемента списка; `cmp` — функция, которая принимает два элементы списка и возвращает -1, 0 или 1 в зависимости от отношения между переданными параметрами; `reversed` — если `True`, то список буде отсортирован в обратном порядке.

    Так вот, что использовать, если, например, надо отсортировать список объектов по полю `id`? Посмотрим на `cmp` и `key` подходы:

    lst.sort(cmp=lambda x, y: cmp(x['id'], y['id']))  # Неплохо и даже понятно

    lst.sort(key=lambda x: x['id'])  # Короче, быстрее, понятней

    Что бы не быть голословным на счёт скорости, пара тестов:

    
    >>> lst = [{'id': x, 'name': 'test'} for x in xrange(1000)]
    >>> random.shuffle(lst)
    >>> def with_cmp(lst):
    ...     lst.sort(cmp=lambda x, y: cmp(x['id'], y['id']))
    ...
    >>> def with_key(lst):
    ...     lst.sort(key=lambda x: x['id'])
    ...
    >>> timeit.timeit('with_cmp(lst[:])', setup='from __main__ import with_cmp, lst', number=1000)
    2.7731389999389648
    >>> timeit.timeit('with_key(lst[:])', setup='from __main__ import with_key, lst', number=1000)
    0.55310797691345215
    

    Почему такая большая разница? Дело в том, что в случае наличия параметра `key` его значение применяется для всех элементов списка только один раз в начале сортировки (сорцы), в то время как значения `cmp` используется при каждом сравнении! Учитывая то, что тим-сорт (разбор алгоритма), который используется в Python, имеет среднюю оценку nlog(n), можно предположить, что в нашем примере lambda из `cmp` вызывалась в несколько раз чаще.

    На самом деле можно (и нужно) сделать еще быстрее — использовав не медленную Python-функцию, а нативную, написанную на C. Здесь очень помогает библиотека operator. Вот как будут выглядеть результаты с operator.itemgetter (еще есть docs.python.org/library/operator.html#operator.attrgetter, methodcalled и много другого вкусного):

    >>> from operator import itemgetter
    >>> def with_op(lst):
    ...     lst.sort(key=itemgetter('id'))
    ...
    >>> timeit.timeit('with_op(lst[:])', setup='from __main__ import with_op, lst, itemgetter', number=1000)
    0.4054520057716877

    Итого, 20 7х прироста скорости в сравнении с первым вариантом — неплохо, правда?

    Разобрались со скоростью, насчет понятности. Я не считаю, что использование `key`\`cmp` должно быть делом вкуса, ибо последний — это отличный пример абстракции, которая течет. Все отлично, пока в функции-значении параметра `cmp` используется built-in `cmp`, которая прячет за собой детали механизма сортировки, но что вы будете делать, когда вас попросят предсказать вывод следующего кода:

    >>> def numeric_compare(x, y):
            return x - y
    >>> sorted([5, 2, 4, 1, 3], cmp=numeric_compare)

    Вы конечно помните, что `cmp` должна возвращать -1, 0 или 1, но что именно? Если `x` больше `y`, то должно быть 1 или -1? Если вернуть 2, будет ошибка или 2 будет интерпретировано как 1? Конечно, найти ответы на вопросы вопросы можно за полминуты, но зачем искать? Я считаю, лучше пользоваться, более качественной абстракцией, то есть параметром `key`.

    Предупреждая вопросы, соглашусь, что наверно есть редкостные примеры задач, где `key` недостаточно. Но это именно исключения, и для них также есть рецепты (например, такой — Sorting Mini-HOW TO:cmp_to_key).

    Спасибо за внимание.


    P.S. Задачка. Почему так странно ведет себя следующий код:

    >>> ls = [(1,2,3), (2,1,3), (2,3,1)]
    >>> ls.sort(key=reversed)
    >>> ls
    [(1, 2, 3), (2, 3, 1), (2, 1, 3)]
    >>> ls.sort(key=reversed)
    >>> ls
    [(2, 1, 3), (1, 2, 3), (2, 3, 1)]
    Ответ:
    `reversed` возвращает объект типа `<type 'reversed'>`, для которого неопределенны rich-comparsion методы. Следовательно, `list.sort` для сравнения использует `id` объектов, которые постоянно изменяются. Используйте `operator.itemgetter(slice(None, None, -1))` вместо `reversed`.
    Метки:
    Поделиться публикацией
    Реклама помогает поддерживать и развивать наши сервисы

    Подробнее
    Реклама
    Комментарии 15
    • +2
      Один вопрос. Как отсортировать с помощью key по двум ключам в разном порядке?
      Например, по ключу age по возрастанию а по name по убыванию?
      Начинать городить на выходе tuple вида (-age, name)?
      • +3
        Так и приходится:
        key = lambda obj: (obj.age, -obj.iq, obj.weight)
        • 0
          А теперь что делать если два поля в разную сторону — текстовые.
          • –2
            Такая сортировка — это уже целая фича, и было бы странно, если бы стандартная библиотека предоставляла такие возможности.

            Один из вариантов реализации — определить rich compasion методы для объекта. Если критерии сортировки меняются — перед каждой сортировкой обвёртывать в объект с нужной конфигурацией сравнения.
            • +5
              Эта фича была в стандартной библиотеке, пока не выпилили cmp :)))
              • 0
                Ну, выпилили и выпилили. Светлая ей память. А стандартная библиотека стала только лучше от этого.
                • 0
                  functools.cmp_to_key(func) не?
                  • 0
                    Оно-оно, знаю. Просто уровень магии и извращения в питоне растёт версия от версии.
        • 0
          Спасибо большое за информацию. Похоже key вычисляется один на элемент в первом проходе, а далее сортировка одних лишь ключей происходит, а cmp вызывается многократно для каждого конкретного элемента при сравнении его с другими.
          • –1
            Python 2.7.2

            >>>ls = [(1,2,3), (2,1,3), (2,3,1)]
            >>>ls.sort(key=reversed)
            >>>ls
            >>>[(1, 2, 3), (2, 1, 3), (2, 3, 1)]
            • –1
              >> На ночь глядя

              image
              • +1
                в тесте 02 должно быть lst.sort(key=opr)
                в тесте 12 локилизация opr заметно ускорит дело
              • +2
                Пример

                def with_op(lst):
                lst.sort(key=itemgetter('name'))


                неправильный, должно быть itemgetter('id'), возможно, оно будет медленнее
                • 0
                  Но быстрее, чем с key=lambda x: x['id'] ( т. е. lst.sort(key=operator.itemgetter('id')) быстрее выполняется, чем lst.sort(key=lambda x: x['id']) )
                  • 0
                    Да, Вы правы, там опечатка. Исправленный вариант в 2-3 раза медленнее.

                  Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.