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

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