Queues - Is Infinity all right?

[Jeremy Fincher]

Paul Rubin <http://phr.cx@NOSPAM.invalid> wrote in message news:<7xr81reorq.fsf at ruckus.brouhaha.com>...
> Peter Hansen <peter at engcorp.com> writes:
> > Checking the source, Queue is implemented as a sophisticated wrapper
> > around a standard Python list [].  That means adding an item is 
> > amortized O(1), while removing one is O(n).
> 
> Why is removing one O(n)?  That should be easy to fix, if true.

The queue implementation he's referring to works somewhat like this:

class queue(list):
  def enqueue(self, item):
    self.append(item)
  def dequeue(self):
    return self.pop(0)

It's the self.pop(0) that's the transgressor here.  All the elements
after it must be moved back one index, so it's O(n) in the size of the
queue.

Sure, it's a simple fix, and there are several ways to make O(1)
queues, but that implementation, aside from being simple, also has a
*very* low constant.  Having tested several competing O(1) queues
against this implementation, none were faster until the number of
items in the queue increased beyond several hundred, sometimes even
into the (low) thousands.

As a side note, the fastest O(1) queue algorithm in my testing was the
following:

class queue(object):
  __slots__ = ('back', 'front')
  def __init__(self, iterable):
    self.front = []
    self.back = []
    for item in iterable:
      self.back.append(item)
  def enqueue(self, item):
    self.back.append(item)
  def dequeue(self):
    if not self.front:
      self.back.reverse()
      self.front = self.back
      self.back = []
    return self.front.pop()

(Although its efficiency obviously depends on how well enqueues and
dequeues are intermixed; while still O(1), it's not highly efficient
when its average length is 1, obviously.)

Jeremy