list.pop(0) vs. collections.dequeue

[Daniel Stutzbach]

On Mon, Jan 25, 2010 at 12:24 PM, Steve Howell <showell30 at yahoo.com> wrote:

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

Actually, the latest version of blist is competitive for "get item" and
similar operations.  See:

http://stutzbachenterprises.com/performance-blist/item
http://stutzbachenterprises.com/performance-blist/set-item
http://stutzbachenterprises.com/performance-blist/lifo
http://stutzbachenterprises.com/performance-blist/shuffle

I added a flat cache of the leaf nodes, yielding O(1) get/set item
operations whenever those operations dominate over insert/delete
operations.  The cache adds around 1.5% memory overhead.


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

If I understand correctly, you feel strongly that a list.pop(0) that runs in
O(n) time is "broken", but you're comfortable with a list.pop(1) that runs
in O(n) time.  Is that correct?

How do you feel about a bisect.insort(list, item) that takes O(n) time?

Different people are bound to have different opinions about which operations
are most important and where lies the best tradeoff between different
operations (as well as code complexity).   I am not sure why you feel so
strongly that particular spot is best.

Obviously, I prefer a slightly different spot, but I also respect the core
developers' choice.

--
Daniel Stutzbach, Ph.D.
President, Stutzbach Enterprises, LLC <http://stutzbachenterprises.com>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.python.org/pipermail/python-list/attachments/20100125/eb13d60b/attachment.html>