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
RetroSearch is an open source project built by @garambo | Open a GitHub Issue
Search and Browse the WWW like it's 1997 | Search results from DuckDuckGo
HTML:
3.2
| Encoding:
UTF-8
| Version:
0.7.4