Подтвердить что ты не робот

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

В 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?

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

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

4b9b3361

Ответ 1

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

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

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

Ответ 2

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

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