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

[Alex Martelli]

Jeremy Fincher wrote:
   ...
>> I've shown how incredibly simple the sort-after-whatever-addition-
>> or-replacement approach is -- the insort one will require some more
>> coding, but IF it's a lot faster, sure.  But don't discount timsort's
>> performance -- it's often incredibly good.
> 
> If timsort is actually faster than bisect.insort in all cases, perhaps
> it's time for bisect.insort to be deprecated?  It's what I would
> naturally use for this case because "that's what it's made for," and
> it'd be unfortunate to point Python programmers to the *less*
> efficient way to do something.

operations that modify data are a tad harder to time with timeit.py,
but not impossible with some precautions...:

[alex at lancelot bo]$ timeit.py -c -s'import bisect' -s'LL=range(99,0,3)'
'L=LL[:]'

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

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

...so, yes -- insort can't hold a candle to a list's sort method when
what you're asking them is to do the very same job.  Of course,
bisect.insort_right, aka insort, has different specs -- e.g., if you
DO need to supply its lo and hi parameters, then you're considering
a very different problem from what the sort method is solving.  

But yes, bisect is basically an EXAMPLE -- a working example of the
peculiarly-hard-to-code-RIGHT bisection algorithm; maybe we should
mention that in the docs.  Lemme see if I can borrow the time machine
for the purpose... done.  Now, the docs do clearly say:

"""
The source code may be most useful as a working example of the algorithm
"""

Better, hm?-)


Alex