alwayssortedlist (was Re: On PEP 322 (ireverse))

[Alex Martelli]

Tim Peters wrote:
   ...
>> alex at lancelot bo]$ timeit.py -c -s'import bisect' -s'LL=range(99,0,3)'
>> 'L=LL[:]; bisect.insort(L, 33)'
>> 100000 loops, best of 3: 4.4 usec per loop
> 
> Well, range(99,0,3) produces an empty list, so it's not timing something
> interesting.  Change it to, e.g., range(0,999,3).  bisect.insort() will

Ooops.  Typo once, and bash readline will let you propagate that typo
N times most easily.  Silly me -- I should have noted the times were too
good.  Sorry!

> eventually beat the pants off list.sort(), and the more expensive element
> comparisons are, the shorter the list at which insort first wins.  Up

Yes, and even with a list of integers insort gets on top pretty fast,
e.g., even just with 100 items or so:

[alex at lancelot bo]$ timeit.py -c -s'import bisect' -s'LL=range(0, 333, 3)'
'L=LL[:]; L.append(33); L.sort()'
10000 loops, best of 3: 17 usec per loop

[alex at lancelot bo]$ timeit.py -c -s'import bisect' -s'LL=range(0, 333, 3)'
'L=LL[:]; bisect.insort(L, 33)'
100000 loops, best of 3: 12.4 usec per loop

    [snip snip]

thanks for the clear explanation (and for upholding bots' honor...).


Alex