In-place decorate-sort-undecorate - best implementation?

[Tom Anderson]

Subtitle: the war on temporary objects continues!

The page on python performance tips on the python.org wiki
(<http://wiki.python.org/moin/PythonSpeed/PerformanceTips>) suggests the
following code for sorting a list using decorate-sort-undecorate, but
doing it in-place:

def sortby_inplace(somelist, n):
somelist[:] = [(x[n], x) for x in somelist]
somelist.sort()
somelist[:] = [val for (key, val) in somelist]

Doesn't the use of list comps there generate two temporary lists? Isn't
that quite inefficient? Wouldn't it be better to use a good old fashioned
loop?

def sortby_inplace(somelist, n):
for i in xrange(len(somelist)):
somelist = (somelist[n], somelist)
somelist.sort()
for i in xrange(len(somelist)):
somelist = somelist[1]

Testing this on a 10k-element list of (float, float, float,
float) tuples gives me a speedup of 35%. On a million-element list it's
only 4%, but hey, who sorts million-element lists anyway?

I don't have python 2.4; anyone care to check how they compare there? I
used the following timer function:

import time
import random
n = 10000
r = random.random
l = [(r(), r(), r(), r()) for i in xrange(n)]

def time(sorter):
l2 = []
l2.extend(l)
t0 = time.time()
sorter(l2, 2)
t1 = time.time()
return t1 - t0

tom

 

[Benji York]

I don't have python 2.4; anyone care to check how they compare there? I
used the following timer function:

I think on 2.4 the new "key" option to list.sort would be the fastest
way to accomplish what you want.