efficient idiomatic queue?

[Magnus Lie Hetland]

In article [...], David Eppstein wrote:
>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(), however it 
>seems from some brief experiments that the del operation takes time linear 
>in the length of the list, so this would be very inefficient for long 
>lists.
[snip]
>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?

The simplest one I can think of is the trusty old linked list...

>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 
>code that has nothing to do with the actual algorithm, otherwise it would 
>be easy to do linked lists,

Hm. Well, it doesn't take *that* much code...

class Node:
    def __init__(self, obj):
        self.value = obj

dummy = Node(None)
dummy.next = dummy

class Queue:
    def __init__(self):
        self.head = self.tail = dummy
    def put(self, obj):
        self.tail.next = Node(obj)
        self.tail = self.tail.next
    def peek(self): return self.head.value
    def get(self):
        result = self.head
        self.head = self.head.next
        return result.value

I'm sure you can simplify it even further without much trouble, using
lists instead of node objects etc... Oh, well. If you don't want it
you don't want it.

BTW: The speedup is quite dramatic:

Problem size: 10
List version: 0.000274896621704
Queue version: 0.000545978546143
Problem size: 100
List version: 0.00122201442719
Queue version: 0.00465798377991
Problem size: 1000
List version: 0.0175099372864
Queue version: 0.0498030185699
Problem size: 10000
List version: 0.939693927765
Queue version: 0.538775920868
Problem size: 100000
List version: 91.8680340052
Queue version: 5.83884394169

(Repeated "problem size" times: Add integer, peek integer, remove
integer. The time is from time.time())

Sadly, the standard library object Queue also uses a list in its
implementation, so there is no help there ;)

--
Magnus Lie Hetland                                  The Anygui Project
http://hetland.org                                  http://anygui.org