On Wed, 30 Mar 2005, Marcus Goldfish wrote:
> I need to implement a FIFO with a fixed maximum capacity. Hi Marcus, Out of curiosity, why do you require a first-in-first-out queue with a maximum capacity? > Would limiting the max capacity of the FIFO improve performance by > allowing one to preallocate the FIFO buffer? Possibly, but at the cost of having a FIFO that can get full. Depending on the domain, this might be ok for you. But most programs suffer from hardcoded limits that really shouldn't have been hardcoded in the first place. You may want to see if having a queue with unlimited size is really a performance drag on your system: have you done any profiling yet? The second implementation that you quoted earlier: > http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/210459 is similar to a nicer one by Jeremy Fincher: ###### class ListSubclassFifo(list): __slots__ = ('back',) def __init__(self): self.back = [] def enqueue(self, elt): self.back.append(elt) def dequeue(self): if self: return self.pop() else: self.back.reverse() self[:] = self.back self.back = [] return self.pop() ###### (See: http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/68436) Since these implementations guarantee O(1) "constant" time access for a queue, even without a hardcoded bound limit, you aren't losing much. Can you use this implementation? Finally, there's a 'deque' in the 'collections' Standard Library module that you might be able to use: http://www.python.org/doc/lib/module-collections.html which also should define constant-time guarantees for insertion and removal. So you might just be able to use that, and not have to copy-and-paste any code at all. *grin* Best of wishes to you! _______________________________________________ Tutor maillist - [email protected] http://mail.python.org/mailman/listinfo/tutor
