Danny, Thanks for the informative response. After I sent the email I realized that a circular buffer is a FIFO with fixed capacity, and that is what I want to implement. I think I recall seeing a recipe in the Python Cookbook (1st).
If you or anyone else know of other recipes/implementations please let me know so I can save on the cut-and-paste. :) Marcus ps -- as for the need for a circular buffer vs. FIFO: I think my dsp background pushed me toward the CB. My app involves data acquisition for extended periods of time. I can't grow the FIFO infinitely, but it is no big deal if a few samples get overwritten. Does this make sense? On Thu, 31 Mar 2005 01:19:24 -0800 (PST), Danny Yoo <[EMAIL PROTECTED]> wrote: > > > 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
