efficient idiomatic queue?

[Tim Peters]

[Tim]
>> It seems that your only objection to your original idea was
>> that it's "very inefficient for long lists".  Why?  That is, if
>> you're only trying to get across the idea of the algorithm, speed
>> doesn't seem relevant ("assume these primitives take constant time;
>> then here's the interesting result: ...").
>> If you're actually worried about efficiency implications of details, I'd
>> expect you'd be keen to teach about those too.

[David Eppstein]
> It's an algorithms design and analysis class.  If I'm going to tell the
> students that some algorithm takes O(n log n) time, it would be
> helpful if the code I show them actually takes O(n log n) instead of
> something slower  that one could make efficient only with more detailed
> knowledge of Python's implementation details.

Well, I suggested two ways to do that, in Python today.  If Python *did*
have a list type "efficient at both ends", I don't think you'd be doing your
students a favor by having to add "and, by the way, this implementation is
only efficient in Python -- in any other language it would crawl, due to
implementation details we won't cover here".

BTW, Icon has an "efficient at both ends" list, but indexing isn't
constant-time there (it uses a doubly-linked list of buckets under the
covers -- or did last time I was familiar with its implementation).

> I realize implementation speed is not the primary concern of Python
> language designers,

Nothing is <wink>.  But you misread this case:  efficiency of *typical* list
operations is so important that we'd be loathe to slow those down in an
effort to cater to unusual operations.  That's why Guido tossed ABC's list
implementation (using AVL trees under the covers) in favor of contiguous
vectors to begin with.  "Almost all" programs ran much faster under Python
than they did under ABC as a result.

> but for Python programmers I think Python's relatively slow speeds make
> it especially important to be careful about asymptotics:  there's less
> slack for using a bad algorithm and letting today's gigahertz
> computers hide your inefficiencies.

We've moved heaven and earth just to make appending an item at a time
efficient in extreme cases across 50 uncooperative platform malloc()
implementations; I expect you underestimate the difficulty of coding fast
portable data structures (not asymptotics, but the infinitely detailed pain
of avoiding pitfalls in real platform libraries and compilers).  Note that I
wouldn't be *opposed* to making Python's list an efficent deque in all
cases, but I don't know how to do it without slowing typical uses.

> ...
> List destruction is not necessary.  The index variable approach is
> probably best in this example, since merge sort doesn't need the full
> power of a queue (each list has all its appends before it is scanned).

Even better (according to me), your students would learn an algorithm that's
efficient even if written in something other than Python.

> I was just hoping that Python's powerful list processing primitives would
> let me simplify the code by avoiding those extra index variables.  And a
> queue is such a basic data structure that I thought surely Python already
> allowed it to be implemented efficiently with its built-in list
> operations.

A plain list works fine for most uses of queues; they have to get pretty big
before memcpy() is a burden.  For big queues, one person (Courageous?) did
code up a more-efficient extension type, but there is no "popular" extension
for this; that suggests demand is low.

> Actually, the merge step in merge sort is a great example for simple
> generators, or would be if not for the difficulty of keeping track of the
> first item of each input iterator:

This is a case where unbounded streams are much easier to live with (see the
"merge" function in test_generators.py -- not having to worry about
end-of-stream allows to eliminate most of the code, and all uses of
StopIteration).

> def merge(A,B):
>         try:
>                 Afirst=A.next()
>                 Aempty=0
>         except StopIteration:
>                 Aempty=1
>         try:
>                 Bfirst=B.next()
>                 Bempty=0
>         except StopIteration:
>                 Bempty=1
>         while not Aempty and not Bempty:
>                 if Afirst < Bfirst:
>                         yield Afirst
>                         try:
>                                 Afirst=A.next()
>                         except StopIteration:
>                                 Aempty=1
>                 else:
>                         yield Bfirst
>                         try:
>                                 Bfirst=B.next()
>                         except StopIteration:
>                                 Bempty=1
>         if not Aempty:
>                 yield Afirst
>                 while 1:
>                         yield A.next()
>         if not Bempty:
>                 yield Bfirst
>                 while 1:
>                         yield B.next()
>
> def mergesort(L):
>         if len(L) < 2:
>                 return iter(L)
>         else:
>                 return merge(mergesort(L[:len(L)//2]),
>                              mergesort(L[len(L)//2:]))
>
> This (like the closely related heap sort) has the advantage that if you
> start sorting n items, but only end up looking at the first k items of
> sorted output, it takes time O(n + k log n), so the time is
> nonlinear only when k is large. But this is way too much code for a
> blackboard, and the students are confused enough by slices...

I appreciate the abstract loveliness of this, but it's hard to see under all
the syntactic hair.  A lazy functional language (like Haskell) is much more
pleasant for writing algorithms in this style.