How to write sort key functions for descending values?

The move in recent versions of Python to passing a key function to sort() from the previous cmp function is making it trickier for me to perform complex sorts on certain objects.

For example, I want to sort a set of objects from newest to oldest, with a set of string tie-breaker fields. So I want the dates in reverse order but the strings in their natural order. With a comparison function I can just reverse the comparison for the date field compared to the string fields. But with a key function I need to find some way to invert/reverse either the dates or the strings.

It's easy (although ugly) to do with numbers - just subtract them from something - but do I have to find a similar hack for dates (subtract them from another date and compare the timedeltas?) and strings (...I have no idea how I'd reverse their order in a locale-independent way).

I know of the existence of functools.cmp_to_key() but it is described as being "primarily used as a transition tool for programs being converted to Python 3 where comparison functions are no longer supported". This implies that I should be able to do what I want with the key method - but how?

The most generic way to do this is simply to sort separately by each key in turn. Python's sorting is always stable so it is safe to do this:

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

will (assuming the relevant definitions for the key functions) give you the data sorted by descending date and ascending tiebreakers.

Note that doing it this way is slower than producing a single composite key function because you will end up doing two complete sorts, so if you can produce a composite key that will be better, but splitting it out into separate sorts gives a lot of flexibility: given a key function for each column you can make any combination of them and specify reverse for any individual column.

For a completely generic option:

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

and for completeness, though I really think it should be avoided where possible:

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

The reason I think you should avoid this you go back to having n log n calls to the comparison function compared with n calls to the key function (or 2n calls when you do the sorts twice).

The slow-but-elegant way to do this is to create a value wrapper that has reversed ordering:

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

If you don't have functools.total_ordering, you'd have to implement all 6 comparisons, e.g.:

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))

How to write sort key functions for descending values?

Related

Recent Posts