efficient idiomatic queue?

[Tim Peters]

[David Eppstein]
> What is the idiomatic way in Python of implementing the following
> operations on a list of elements:
>  - return the element at the front of the list, without changing the list
>  - remove the element from the front of the list
>  - add a new element to the rear of the list
>
> My first choice would be L[0], del L[0], and L.append(),

Yes, that's "the usual".  L[-1], L.pop() and L.insert(0, item) (looking at
it "from the other end") is a less usual combo.

> however it seems from some brief experiments that the del operation
> takes time linear in the length of the list,

Yes, all the elements in L[1:] are physically moved left a slot.

> so this would be very inefficient for long lists.

Sure.

> I also tried replacing the del with L=L[1:] but that wasn't any
> better.

That makes a physical copy of the slice.

> A third possibility would be to have to variables L and i, and
> implement the three operations with L[i], i=i+1, and L.append(), which is
> fast but not good in space usage when the total number of operations is
> much larger than the length of the list.
>
> Is there a simple Pythonic way of implementing these three operations in
> constant (amortized) time per operation and space linear in the length of
> the list?

You can wrap your approch with index vrbls into a smarter class.

> The application this came up for me is a merge sort example for an
> algorithms class.

IME mergesort runs fastest if implemented in a more straightforward way,
using a continguous vector of the same length as the input vector for temp
storage, and swapping the roles of "real vector" and "temp vector" on
succeeding iterations.  Then there's no dynamic allocation beyond getting a
temp vector once at the start, and a fixed handful of auxiliary index
variables suffices to keep track of where you are.

> The application this came up for me is a merge sort example for an
> algorithms class.  So, I don't want to confuse the students with
> additional ode that has nothing to do with the actual algorithm,
> otherwise it would  be easy to do linked lists, or to do the third
> possibility above plus slicing L down to size when i grows too large, or
> something like that.

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.

BTW, is it necessary to destory the input lists?  Rather than remove the
element at the front of a list, most people <wink> would just increment an
index vrbl.  Then all mutation occurs only via .append() on the output list,
and your efficiency worry goes away.

saving-an-index-vrbl-isn't-worth-much-thought-ly y'rs  - tim