list.pop(0) vs. collections.dequeue

[Steve Howell]

On Jan 22, 11:10 pm, a... at pythoncraft.com (Aahz) wrote:
> In article <83082e19-9130-45a8-91f2-8601c1fda... at 22g2000yqr.googlegroups.com>,
> Steve Howell  <showel... at yahoo.com> wrote:
>
>
>
>
>
> >I really want to use list *normally* with all its perfectly good
> >semantics and reasonable implementation, except for its blind spot
> >with respect to popping the first element off the list.  The whole
> >reason I use CPython vs. C in the first place is that CPython
> >programmers can generally program basic data structures better than I
> >can.  But list.pop(0) is the exception.  And, with the possible
> >exception of dicts, lists are the most fundamental data structures
> >that Python has.
>
> >I know Python's number one concern will never be speed, but if Python
> >makes an O(1) operation into an unnecessarily O(N) operation for no
> >good reasons other than "it's too complicated, " or it "adds another
> >pointer to the structure," or "it adds another conditional check to
> >list_ass_slice for operations that aren't popping off the top," I
> >think it's reasonable to challenge the design philosophy.
>
> "Rough consensus and running code."
>
> You have a good point, but nobody will ever give your idea serious
> attention until there's a patch and benchmarks.

Another benchmark is that deques are slower than lists for accessing
elements.

showell at showell-laptop:~$ python foo.py
0.0215361118317 <- list
0.0429010391235 <- deque


    import time
    from collections import deque

    n = 40000
    lst = []
    for i in range(n):
        lst.append(i)

    t = time.time()
    for i in range(n):
        lst[i]
    print time.time() - t

    lst = deque(lst)
    t = time.time()
    for i in range(n):
        lst[i]
    print time.time() - t

So substituting deque for list suffers not just in convenience, but
also in performance.