FIFO Data Structure in Python
This post is obselete, see this more recent discussion.
For some odd reason, Python doesn’t come with a good FIFO data structure (as of 2.4). Here’s one.
class Fifo:
def __init__(self):
self.data = [[], []]
def append(self, value):
self.data[1].append(value)
def pop(self):
if not self.data[0]:
self.data.reverse()
self.data[0].reverse()
return self.data[0].pop()
def __len__(self):
return len(self.data[0])+len(self.data[1])
def tolist(self):
temp= self.data[0][:]
temp.reverse()
return temp+self.data[1]
Why not try something simpler like this:
class Fifo:
def __init__(self):
self.items = []
def append(self, item):
self.items.append(item)
def pop(self):
item = self.items[0]
del self.items[0]
return item
def __len__(self):
return len(self.items)
def tolist(self):
#defensive copy
return self.items[:]
import unittest
class FifoTest(unittest.TestCase):
def testItemsArePoppedInSameOrderTheyWereRemoved(self):
fifo = Fifo()
fifo.append(’a')
fifo.append(’b')
fifo.append(’c')
self.assertEquals(’a', fifo.pop())
self.assertEquals(’b', fifo.pop())
self.assertEquals(’c', fifo.pop())
def testFifoLengthChangesAsItemsAreRemoved(self):
fifo = Fifo()
fifo.append(’a')
fifo.append(’b')
fifo.append(’c')
self.assertEquals(3, len(fifo))
fifo.pop()
self.assertEquals(2, len(fifo))
fifo.pop()
self.assertEquals(1, len(fifo))
fifo.pop()
self.assertEquals(0, len(fifo))
def testFifoCanBeConvertedToList(self):
fifo = Fifo()
fifo.append(’a')
fifo.append(’b')
fifo.append(’c')
self.assertEquals(['a','b','c'], fifo.tolist())
if __name__ == ‘__main__’:
suite = unittest.TestSuite()
suite.addTest(unittest.makeSuite(FifoTest))
unittest.TextTestRunner(verbosity=3).run(suite)
Comment by ade — 30/4/2006 @ 17:16
Because the expected popping time of your solution is linear with respect to the size of the list. Specifically, doing “del self.items[0]” can be tremendously expensive since Python needs to copy the entire array to a new location in memory. Doing so thousands of times is highly inefficient.
Comment by Daniel Lemire — 30/4/2006 @ 19:49
Thanks I hadn’t realised that. Come to think of it the list class has a pop method I could have used.
Anyway if you’re interested in a highly-performant Fifo class then take a look at the bottom of this Python Cookbook entry: http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/68436
Comment by ade — 1/5/2006 @ 5:27