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[i] = (somelist[i][n], somelist[i])
 	somelist.sort()
 	for i in xrange(len(somelist)):
 		somelist[i] = somelist[i][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

-- 
No hay banda