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. :)
Here is a simple ring buffer implemented on top of deque:
from collections import deque
class ring_buffer(deque):
def __init__(self, capacity):
deque.__init__(self) assert capacity > 0
self.capacity = capacity def append(self, x):
while len(self) >= self.capacity:
self.popleft()
deque.append(self, x)
rb = ring_buffer(3)
for i in range(5):
rb.append(i)
print list(rb)Kent
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
_______________________________________________ Tutor maillist - [email protected] http://mail.python.org/mailman/listinfo/tutor
