Как написать ключевые функции сортировки Python для нисходящих значений

Перемещение в последних версиях Python для передачи ключевой функции в sort() из предыдущей функции cmp делает меня более сложным для выполнения сложных видов на определенных объектах.

Например, я хочу сортировать набор объектов от самых новых до самых старых, с набором полей тай-брейка. Поэтому я хочу, чтобы даты были в обратном порядке, но строки в их естественном порядке. С помощью функции сравнения я могу просто изменить сравнение поля даты по сравнению со строковыми полями. Но с ключевой функцией мне нужно найти способ инвертировать/изменить либо даты, либо строки.

Легко (хотя и некрасиво) делать с цифрами - просто вычтите их из чего-то - но мне нужно найти подобный хак для дат (вычесть их из другой даты и сравнить timedeltas?) и строки (... я не знаю, как бы я изменил их порядок независимо от языка).

Я знаю о существовании functools.cmp_to_key(), но он описан как "в основном используемый в качестве инструмента перехода для программ, преобразованных в Python 3, где функции сравнения больше не поддерживаются". Это означает, что я должен иметь возможность делать то, что хочу с помощью ключевого метода, но как?

Ответ 1

Медленный, но элегантный способ сделать это - создать обертку значений, которая имеет обратное упорядочение:

from functools import total_ordering
@total_ordering
class ReversedOrder:
    def __init__(self, value):
        self.value = value
    def __eq__(self, other):
        return other.value == self.value
    def __lt__(self, other):
        return other.value < self.value

Если у вас нет functools.total_ordering, вам нужно будет выполнить все 6 сравнений, например:

import operator
class ReversedOrder:
    def __init__(self, value):
        self.value = value
for x in ['__lt__', '__le__', '__eq__', '__ne__', '__ge__', '__gt__']:
    op = getattr(operator, x)
    setattr(ReversedOrder, x, lambda self, other, op=op: op(other.value, self.value))

Ответ 2

Самый общий способ сделать это - просто сортировать по отдельности по каждому ключу по очереди. Сортировка Python всегда стабильна, поэтому безопасно это сделать:

sort(data, key=tiebreakerkey)
sort(data, key=datekey, reverse=True)

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

Обратите внимание, что выполнение этого способа происходит медленнее, чем создание одной составной ключевой функции, потому что вы в конечном итоге выполните две полные сортировки, поэтому, если вы можете создать составной ключ, который будет лучше, но разделить его на отдельные виды, много гибкости: с учетом ключевой функции для каждого столбца вы можете сделать любую комбинацию из них и указать обратное для любого отдельного столбца.

Для полностью общего варианта:

keys = [ (datekey, True), (tiebreakerkey, False) ]
for key, rev in reversed(keys):
    sort(data, key=key, reverse=rev)

и для полноты, хотя я действительно думаю, что этого следует избегать, где это возможно:

from functools import cmp_to_key
sort(data, key=cmp_to_key(your_old_comparison_function))

Я думаю, что вам следует избегать этого, вы возвращаетесь к тому, чтобы n log n вызывал функцию сравнения по сравнению с вызовами n к ключевой функции (или 2n звонки, когда вы делаете сортировки дважды).

Ответ 3

Я думаю, что документы неполны. Я интерпретирую слово "в первую очередь" как означающее, что есть еще причины использовать cmp_to_key, и это один из них. cmp был удален, потому что это была "привлекательная неприятность": люди будут тяготеть к нему, хотя key был лучшим выбором.

Но ваш случай явно лучше как функция cmp, поэтому используйте cmp_to_key для его реализации.

Ответ 4

Сортировка дважды, один раз на каждой клавише и один раз обратный.

(Python sort stable, то есть он не изменяет порядок исходного списка, если только он не должен.)

_{Неважно, какой порядок вы выполняете, если вам интересно, как сортируются равные элементы.}

Ответ 5

Для String вы можете использовать некоторое общепризнанное максимальное значение (например, 2 ^ 16 или 2 ^ 32) и использовать chr(), unicode(), ord() для выполнения математики, как и для целых чисел.

В одной из моих работ я знаю, что имею дело со строками в utf8, а их ординалы ниже 0xffff, поэтому я написал:

def string_inverse(s):
    inversed_string = ''
    max_char_val = 0xffff
    for c in s:
        inversed_string += unicode(max_char_val-ord(c))
    return inversed_string        

result.sort(key=lambda x:(x[1], string_inverse(x[0])), reverse=True)

x имеет тип: (string, int), поэтому я получаю, чтобы злоупотреблять SQL:

select * from result order by x[1] desc, x[0] asc;