[Python-Dev] decorate-sort-undecorate

[Tim Peters]

[Ian Bicking]
> When doing DSU sorting, the in-place sorting isn't really a
> performance win, is it?  You already have to allocate and populate an
> entire alternate list with the sort keys, though I suppose you could
> have those mini key structs point to the original list.

IIUC, Raymond's patch actually (re)uses the original list object to hold
(pointers to) the wrapper objects.  No additional list is allocated.  Since
the wrapper objects hold (pointers to) the original objects, it's easy to
make the list point back to the original objects at the end.  It's better
this way than hand-rolled DSU coded in Python, although the same effect
*could* be gotten via

    class Wrapper:
        def __init__(self, key, obj):
            self.key = key
            self.obj = obj
        def __lt__(a, b):
            return a.key < b.key

    for i, obj in enumerate(L):
        L[i] = Wrapper(key(obj), obj)
    L.sort()
    for i, w in enumerate(L):
        L[i] = w.key

assuming no exceptions occur along the way.

> Anyway, while it's obviously in bad taste to propose .sort change its
> return value based on the presence of a key, wouldn't it be good if we
> had access to the new sorted list, instead of always clobbering the
> original list?  Otherwise people's sorted() functions will end up
> copying lists unnecessarily.

Give it an optional clobber argument -- your own sort function doesn't
*have* to copy the list.