[Tutor] a FIFO with fixed capacity?

[Kent Johnson]

Marcus Goldfish wrote:
> 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
> <dyoo at hkn.eecs.berkeley.edu> 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  -  Tutor at python.org
> http://mail.python.org/mailman/listinfo/tutor
>