efficient idiomatic queue?

[Delaney, Timothy]

> >class DictFifo:
> >    def __init__(self):
> >        self.data = {}
> >        self.nextin = 0
> >        self.nextout = 0
> >    def append(self, value):
> >        self.data[self.nextin] = value
> >        self.nextin += 1
> >    def pop(self):
> >        value = self.data[self.nextout]
> >        del self.data[self.nextout]
> >        self.nextout += 1
           return value

:)

>     def __init__(self):
>         self.data = {}
>         self.nextin = 0L
>         self.nextout = 0L
> 
> to make sure that you can use it for more than two billion 
> entries.  ;-)
> 
> I haven't tested this, but I think that if you expect queues to be
> large, this might actually be a fast, clear implementation.

I just tested it with the following code. Everything is wrapped in classes
to maintain similar overhead. Note that for DictIntFifo, OverflowError is
caught to allow conversion to long in any version of Python. I've also
included a normal list and array for comparison.

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):
		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):
		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):
		return self.data.pop()

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

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

	def pop(self):
		return self.data.pop(0)

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

	start = time.clock()

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

	end = time.clock()

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

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

for i in xrange(4):
	
	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))

1000     <type 'list'>        0.003968
1000     <type 'array'>       0.004607
1000     DictIntFifo          0.012154
1000     DictLongFifo         0.015508
1000     ListPrependFifo      0.010499
1000     ListAppendFifo       0.010357

10000    <type 'list'>        0.039399
10000    <type 'array'>       0.046923
10000    DictIntFifo          0.120931
10000    DictLongFifo         0.156747
10000    ListPrependFifo      0.105777
10000    ListAppendFifo       0.105253

100000   <type 'list'>        0.394604
100000   <type 'array'>       0.459258
100000   DictIntFifo          1.214058
100000   DictLongFifo         1.568331
100000   ListPrependFifo      1.060692
100000   ListAppendFifo       1.046310

1000000  <type 'list'>        4.071518
1000000  <type 'array'>       4.640713
1000000  DictIntFifo          12.192316
1000000  DictLongFifo         15.778213
1000000  ListPrependFifo      10.700729
1000000  ListAppendFifo       10.636400

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.

Nonetheless, it is a good example of separating interface from
implementation.

Tim Delaney