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

[Jeremy Fincher]

Alex Martelli <aleaxit at yahoo.com> wrote in message news:<bXdob.70443$e5.2563561 at news1.tin.it>...
> Jeremy Fincher wrote:
> > Any reason he shouldn't just use bisect.insort?
> 
> What about measuring the performance of the two approaches?

I'll do that when I get back to my own computer.  It's interesting, of
course, because although the point of bisect.insort is to use O(log n)
binary search to find the place to insert an element, it's still O(n)
because list.insert is O(n).  So if timsort is close to O(n) for
nearly-sorted lists, I wonder if it would actually be faster than
bisect.insort because it's coded in C.

> 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.

Jeremy