efficient idiomatic queue?

[Delaney, Timothy]

> From: David Eppstein [mailto:eppstein at ics.uci.edu]
> 
> In article <mailman.1011223225.3777.python-list at python.org>,
>  "Delaney, Timothy" <tdelaney at avaya.com> wrote:
> 
> > So, it looks like there is a definite speed penalty with 
> the dict versions,
> > although the majority of that is probably namespace lookup 
> time (more
> > operations). A C version would probably do quite well.
> 
> It's good to see actual data, but I don't think this is a 
> fair comparison: 
> your queues always have at most one item in them, so you 
> never see how well 
> these versions scale to different lengths. Try replacing

Remind me to hit myself with a rubber chicken ...

Of course I completely invalidated the point of the entire exercise ... I
should have added all, then removed all (which in my mind I was doing). And
my comparison with list/array is incorrect as well ... I needed to change
every pop() to accept a position (and ignore it :) so I could pop(0) on the
list and array.

import time
import string
import array

class DictIntFifo:

	def __init__(self):
		self.data = {}
		self.nextin = 0
		self.nextout = 0

	def append(self, value):

		self.data[self.nextin] = value

		try:
			self.nextin += 1
		except OverflowError:
			self.nextin += long(1)

	def pop(self, pos=-1):
		value = self.data[self.nextout]
		del self.data[self.nextout]

		try:
			self.nextout += 1
		except OverflowError:
			self.nextout += long(1)

		return value

class DictLongFifo:

	def __init__(self):
		self.data = {}
		self.nextin = long(0)
		self.nextout = long(0)

	def append(self, value):

		self.data[self.nextin] = value
		self.nextin += 1

	def pop(self, pos=-1):
		value = self.data[self.nextout]
		del self.data[self.nextout]
		self.nextout += 1
		return value

class ListPrependFifo:
	""""""
	
	def __init__(self):
		""""""
		self.data = []

	def append(self, value):
		self.data.insert(0, value)

	def pop(self, pos=-1):
		return self.data.pop()

class ListAppendFifo:
	""""""
	
	def __init__(self):
		""""""
		self.data = []

	def append(self, value):
		self.data.append(value)

	def pop(self, pos=-1):
		return self.data.pop(0)

def test (fifo, iterations):
	""""""

	start = time.clock()

	for i in xrange(iterations):
		fifo.append(i)

	for i in xrange(iterations):
		j = fifo.pop(0)

	end = time.clock()

	try:
		name = fifo.__class__.__name__
	except:
		name = type(fifo)

	print "%-8s %-20s %-06f" % (iterations, name, end - start,)

for i in xrange(3):
	
	print
	test([], 10**(i + 3))
	test(array.array('i'), 10**(i + 3))
	test(DictIntFifo(), 10**(i + 3))
	test(DictLongFifo(), 10**(i + 3))
	test(ListPrependFifo(), 10**(i + 3))
	test(ListAppendFifo(), 10**(i + 3))

---------- Run ----------

1000     <type 'list'>        0.007721
1000     <type 'array'>       0.007273
1000     DictIntFifo          0.012430
1000     DictLongFifo         0.017795
1000     ListPrependFifo      0.013849
1000     ListAppendFifo       0.014851

10000    <type 'list'>        0.329070
10000    <type 'array'>       0.234557
10000    DictIntFifo          0.123809
10000    DictLongFifo         0.185284
10000    ListPrependFifo      0.329698
10000    ListAppendFifo       0.398269

100000   <type 'list'>        76.195043
100000   <type 'array'>       56.828019
100000   DictIntFifo          1.269020
100000   DictLongFifo         1.961017
100000   ListPrependFifo      60.693928
100000   ListAppendFifo       77.094517

So once you get to decently large quantities in the queue, the dict versions
make real sense over a basic list (Win2000).

Tim Delaney