[Python-Dev] decorate-sort-undecorate

[Alex Martelli]

On Tuesday 14 October 2003 11:06 pm, Geoffrey Talvola wrote:
   ...
> The point I'm trying to make it that a key function is usually more natural
> to use than a comparison function.  You're right, DSU isn't the only way to

I agree, with ONE important exception: when your desired sort order is e.g
"primary key ascending field X, secondary key descending field Y", writing
a key-extraction function can be an absolute BEAR (you have to know
the type of field Y, and even then how to build a key that will sort in 
descending order by it is generally anything but easy), while a comparison
function is trivial:

def compafun(a, b):
    return cmp(a.X,b.X) or cmp(b.Y,a.Y)

i.e., you obtain descending vs ascending order by switching the arguments
to builtin cmp, and join together multiple calls to cmp with 'or' thanks to
the fact that cmp returning 0 (equal on this key) is exactly what needs
to trigger the "moving on to further, less-significant keys".

In fact I find that the simplest general way to do such compares with a key 
extraction function is a wrapper:

class reverser(object):
    def __init__(self, obj): self.obj = obj
    def __cmp__(self, other): return cmp(other.obj, self.obj)

relying on the fact that an instance of reverser will only ever be compared
with another instance of reverser; now, for the same task as above,

def keyextract(obj):
    return obj.X, reverser(obj.Y)

does work.  However, the number of calls to reverser.__cmp__ is generally
O(N log N) [unless you can guarantee that most X subkeys differ] so that
the performance benefits of DSU are, alas, not in evidence any more here.
A C-coded 'reverser' would presumably be able to counteract this, though
(but I admit I have never had to write one in practice).


Alex