list.pop(0) vs. collections.dequeue

[Steve Howell]

On Jan 24, 1:51 pm, Daniel Stutzbach <dan... at stutzbachenterprises.com>
wrote:
> On Sun, Jan 24, 2010 at 1:53 PM, Steve Howell <showel... at yahoo.com> wrote:
> > I don't think anybody provided an actual link, but please correct me
> > if I overlooked it.
>
> I have to wonder if my messages are all ending up in your spam folder
> for some reason. :-)
>
> PEP 3128 (which solves your problem, but not using the implementation
> you suggest)http://www.python.org/dev/peps/pep-3128/
>
> Implementation as an extension module:http://pypi.python.org/pypi/blist/
>
> Related discussion:http://mail.python.org/pipermail/python-3000/2007-April/006757.htmlhttp://mail.python.org/pipermail/python-3000/2007-May/007491.html
>  be
> Detailed performance comparison:http://stutzbachenterprises.com/performance-blist
>
> I maintain a private fork of Python 3 with the blist replacing the
> regular list, as a way of rigorously testing the blist implementation.
>
> Although I originally proposed a PEP, I am content to have the blist
> exist as a third-party module.
>


Hi Daniel, I agree with what Raymond Hettinger says toward the top of
the PEP.  Blist, while extremely useful, does seem to have to trade
off performance of common operations, notably "get item", in order to
get better performance for other operations (notably insert/delete).
My algorithm does exactly N pops and roughly N list accesses, so I
would be going from N*N + N to N + N log N if switched to blist.  That
would be at least a theoretical gain over the current performance, but
if pop() were O(1), I could get the whole thing down to N time.