A ring buffer is a buffer with a fixed size. When it fills up, adding another element overwrites the first. It's particularly useful for the storage of log information. There is no direct support in Python for this kind of structure but it's easy to construct one.
Here is a suggestion of implementation optimized for element insertion.
Python, 35 lines
Download
Copy to clipboard1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 | class RingBuffer:
def __init__(self,size_max):
self.max = size_max
self.data = []
def append(self,x):
"""append an element at the end of the buffer"""
self.data.append(x)
if len(self.data) == self.max:
self.cur=0
self.__class__ = RingBufferFull
def get(self):
""" return a list of elements from the oldest to the newest"""
return self.data
class RingBufferFull:
def __init__(self,n):
raise "you should use RingBuffer"
def append(self,x):
self.data[self.cur]=x
self.cur=(self.cur+1) % self.max
def get(self):
return self.data[self.cur:]+self.data[:self.cur]
# sample of use
x=RingBuffer(5)
x.append(1); x.append(2); x.append(3); x.append(4)
print x.__class__,x.get()
x.append(5)
print x.__class__,x.get()
x.append(6)
print x.data,x.get()
x.append(7); x.append(8); x.append(9); x.append(10)
print x.data,x.get()
|
This recipe use class dynamic setting. This allows to have different implementations for the same interface and to select which one to use, according to object state. This may not work with new classes of Python 2.2 (eg classes derived from built-in types).
Tags: algorithms
I like the technique of assigning to __class__. I've always liked the idea of ring buffers (bounded queues, or whatever people choose to call them). But the inefficiency of testing if the ring is full, and if so doing something different, is a nuisance, especially in a language like Python where there's no difficulty in allowing the list to grow without bound - other than the massive memory cost involved!!!
The idea of assigning to __class__ to switch behaviours when the ring gets full is a very nice one - it's a one-off operation, so it doesn't make the steady-state case less efficient.
Presumably, you could define the helper class (for the bounded case) inside the main class, which makes it more obvious that it isn't meant for general use.
Perhaps reassign methods rather than reassign __class__. I guess you could define two methods, _full_get and _full_append, and instead of reassigning self.__class__, reassign like this:
I think this will still work with new style Python 2.2 classes.
This is a neat technique, which I was about to use when I found out that in 2.6 you can use collections.deque with the maxlen parameter for the same effect. Nifty!