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