При сортирование в 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('name')) ... >>> timeit.timeit('with_op(lst[:])', setup='from __main__ import with_op, lst, itemgetter', number=1000) 0.1422731876373291Итого, 20х прироста скорости в сравнении с первым вариантом — неплохо, правда?
Разобрались со скоростью, насчет понятности. Я не считаю, что использование `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`.
Автор: leron
