RetroSearch Browse

Sat Oct 18 11:14:19 EDT 2003 · https://mail.python.org/pipermail/python-dev/2003-October/038963.html

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

Home - News ( United States | United Kingdom | Italy | Germany ) - Football scores

Showing content from https://mail.python.org/pipermail/python-dev/2003-October/038963.html below:

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