Сортировки: 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`.