[Python-Dev] The Trick (was Re: copysort patch, was Re: inline sort option) (original) (raw)

Alex Martelli aleaxit at yahoo.com
Sat Oct 18 11:14:19 EDT 2003

On Saturday 18 October 2003 02:26 pm, Alex Martelli wrote: ...oops...

x = dict.fromkeys(range(99999))

here, x.keys() IS already sorted, so the importance of The Trick is emphasized because the sort itself has little work to do:

turns out to be identical between the two with The Trick (4.4e+04 usec with timeit.py -c on my box) while without The Trick copysort would slow down to about 5.5e+04 usec.

I've changed the initialization of x to

x = dict.fromkeys(map(str,range(99999)))

so that x.keys() is not already sorted (still has several runs that the sort will exploit -- perhaps representative of some real-world sorts...;-) and the numbers change to about 240 milliseconds with The Trick (or with separate statements to get and sort the keys), 265 without -- so, more like 10% advantage, NOT 20%-ish (a list.copysort method, from Raymond's patch, has 240 milliseconds too -- indeed it's just about the same code I was using in the standalone function I posted, give or take some level of indirectness in C calls that clearly don't matter much here).

Of course, the % advantage will vary with the nature of the list (how many runs that sort can exploit) and be bigger for smaller lists (given we're comparing O(N) copy efforts vs O(N log N) sorting efforts).

Alex

More information about the Python-Dev mailing list