[Python-Dev] decorate-sort-undecorate

[Raymond Hettinger]

[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
repopulation
> 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