[Python-Dev] decorate-sort-undecorate

Raymond Hettinger python at rcn.com
Thu Oct 16 10:26:50 EDT 2003

[Alex Martelli]
> I thought the idea being implemented avoided making a new list --
> i.e., that the idea being implemented is the equivalent of:
> # decorate
> for i, item in enumerate(thelist):
>     thelist[i] = CleverWrapper((key(item), item))
> # sort (with the new stability guarantee)
> thelist.sort()
> # undecorate
> for i, item in enumerate(thelist):
>     thelist[i] = item[1]
> where (the equivalent of):
> class CleverWrapper(tuple):
>     def __cmp__(self, other): return cmp(self[0], other[0])
> so, there is no allocation of another list -- just (twice) a
> of the existing one.  How _important_ that is to performance, I dunno,
> but wanted to double-check on my understanding of this anyway.

Yes, that is how it works in a nutshell ;-)

Of course, it looks more impressive and was harder to write in C.

Raymond Hettinger

More information about the Python-Dev mailing list