Сортировка Python 3: Пользовательский сопоставитель удален в пользу ключа - почему?

17

В Python 2.4 вы можете передать пользовательский сопоставитель для сортировки.

Давайте возьмем список -

list=[5,1,2,3,6,0,7,1,4]

Чтобы сначала отсортировать четные числа, а затем коэффициенты, мы можем сделать следующее:

evenfirst=lambda x,y:1 if x%2>y%2 else -1 if y%2>x%2 else x-y
list.sort(cmp=evenfirst)
list == [0, 2, 4, 6, 1, 1, 3, 5, 7] # True

В Python 3 вы можете передать только key (которая также поддерживается в Python 2.4).

Конечно, такая же сортировка может быть достигнута в Python 3 с правом key :

list.sort(key=lambda x:[x%2,x])

Мне интересно узнать о том, как больше не поддерживать пользовательские сопоставления, особенно когда кажется, что это может быть реализовано достаточно легко.

Верно ли, что во всех случаях или в большинстве случаев требуемый порядок сортировки имеет естественный key ?

В приведенном выше примере, например, такой ключ существует - и на самом деле код становится более кратким, используя его. Это всегда так?

(Я знаю об этом рецепте для преобразования сравнения с ключом, но в идеале не нужно брать такие обходные пути, если он может быть встроен в язык.)

    
задан KalEl 04.09.2013 в 16:48
источник
  • В этом видео Raymond Hettinger объясняет, почему cmp был удален: преобразование кода в красивый, идиоматический Python (переход к 10:05, пользовательский порядок сортировки) –  Ashwini Chaudhary 04.09.2013 в 16:54
  • FWIW, cmp_to_key теперь существует в functools, поэтому вам не нужен внешний рецепт. –  DSM 04.09.2013 в 18:03

2 ответа

7

Производительность.

Функция cmp вызывается каждый раз, когда алгоритму сортировки требуется сравнение между двумя элементами.

Напротив, объект key может быть кэширован . То есть алгоритм сортировки должен получить ключ один раз для каждого элемента, а затем сравнить ключи. Для каждого сравнения не требуется вводить новый ключ.

    
ответ дан OdraEncoded 04.09.2013 в 17:03
6

Сортировка по ключам четко определена, что означает, что результат не зависит от того, какой (стабильный) алгоритм сортировки вы используете. Нет никакой патологической ключевой функции. Вы можете предложить random.random() , но это просто перетасовывает список.

В то время как сортировка с помощью функции сравнения хорошо определена, только если функция транзитивна и антисимметрична, которую Python не может ни тестировать, ни доказывать. Что произойдет, если вы сортируете по абсурду функции сравнения lambda(x, y): 1 ? Вы не можете сказать, результат зависит от алгоритма. Некоторые алгоритмы могут даже не заканчиваться.

    
ответ дан Colonel Panic 04.09.2013 в 17:45
  • Согласовано - хотя предотвращение логических ошибок не должно быть причиной отказа от функциональности. Если это не так, его можно также отбросить по другим причинам и не влиять на сложность кода. –  KalEl 06.09.2013 в 21:07
  • @KalEl: функциональность все еще присутствует; если тип, с которым вы работаете, поддерживает стабильный, естественный компаратор, вы можете получить ключ от этого с помощью functools.cmp_to_key () –  SingleNegationElimination 06.09.2013 в 23:09