Daniel Lemire's blog

, 3 min read

FIFO Data Structure in Python

3 thoughts on “FIFO Data Structure in Python”

  1. 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.

  2. ade says:

    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)

  3. ade says:

    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