Python Cookbook 2Nd Edition Jun 1002005 [Electronic resources] نسخه متنی

Recipe 6.11. Implementing a Ring Buffer

Credit: Sébastien Keim, Paul Moore, Steve
Alexander, Raymond Hettinger

Problem

You want to define a buffer with a fixed size, so that, when it fills
up, adding another element overwrites the first (oldest) one. This
kind of data structure is particularly useful for storing log and
history information.

Solution

This recipe changes the buffer object's class on the
fly, from a nonfull buffer class to a full buffer class, when the
buffer fills up:

class RingBuffer(object):
"" class that implements a not-yet-full buffer ""
def _ _init_ _(self, size_max):
self.max = size_max
self.data = [  ]
class _ _Full(object):
"" class that implements a full buffer ""
def append(self, x):
"" Append an element overwriting the oldest one. ""
self.data[self.cur] = x
self.cur = (self.cur+1) % self.max
def tolist(self):
"" return list of elements in correct order. ""
return self.data[self.cur:] + self.data[:self.cur]
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
# Permanently change self's class from non-full to full
self._ _class_ _ = _ _Full
def tolist(self):
"" Return a list of elements from the oldest to the newest. ""
return self.data
# sample usage
if _ _name_ _ == '_ _main_ _':
x = RingBuffer(5)
x.append(1); x.append(2); x.append(3); x.append(4)
print x._ _class_ _, x.tolist( )
x.append(5)
print x._ _class_ _, x.tolist( )
x.append(6)
print x.data, x.tolist( )
x.append(7); x.append(8); x.append(9); x.append(10)
print x.data, x.tolist( )

Discussion

A ring buffer is a buffer with a fixed size. When it fills up, adding
another element overwrites the oldest one that was still being kept.
It's particularly useful for the storage of log and
history information. Python has no direct support for this kind of
structure, but it's easy to construct one. The
implementation in this recipe is optimized for element insertion.

The notable design choice in the implementation is that, since these
objects undergo a nonreversible state transition at some point in
their lifetimesfrom nonfull buffer to full buffer (and
behavior changes at that point)I modeled that by changing
self._ _class_ _. This works just as well for
classic classes as for new-style ones, as long as the old and new
classes of the object have the same slots (e.g., it works fine for
two new-style classes that have no slots at all, such as
RingBuffer and _ _Full in this
recipe). Note that, differently from other languages, the fact that
class _ _Full is implemented inside class
RingBuffer does not imply any special relationship
between these classes; that's a good thing, too,
because no such relationship is necessary.

Changing the class of an instance may be strange in many languages,
but it is an excellent Pythonic alternative to other ways of
representing occasional, massive, irreversible, and discrete changes
of state that vastly affect behavior, as in this recipe. Fortunately,
Python supports it for all kinds of classes.

Ring buffers (i.e., bounded queues, and
other names) are quite a useful idea, but the inefficiency of testing
whether the ring is full, and if so, doing something different, is a
nuisance. The nuisance is particularly undesirable in a language like
Python, where there's no difficultyother than
the massive memory cost involvedin allowing the list to grow
without bounds. So, ring buffers end up being underused in spite of
their potential. The idea of assigning to _ _class_
_ to switch behaviors when the ring gets full is the key to
this recipe's efficiency: such class switching is a
one-off operation, so it doesn't make the
steady-state cases any less efficient.

Alternatively, we might switch just two methods, rather than the
whole class, of a ring buffer instance that becomes full:

class RingBuffer(object):
def _ _init_ _(self,size_max):
self.max = size_max
self.data = [  ]
def _full_append(self, x):
self.data[self.cur] = x
self.cur = (self.cur+1) % self.max
def _full_get(self):
return self.data[self.cur:]+self.data[:self.cur]
def append(self, x):
self.data.append(x)
if len(self.data) == self.max:
self.cur = 0
# Permanently change self's methods from non-full to full
self.append = self._full_append
self.tolist = self._full_get
def tolist(self):
return self.data

This method-switching approach is essentially equivalent to the
class-switching one in the recipe's solution, albeit
through rather different mechanisms. The best approach is probably to
use class switching when all methods must be
switched in bulk and method switching only when you need finer
granularity of behavior change. Class switching is the only approach
that works if you need to switch any special
methods in a new-style class, since intrinsic lookup of special
methods during various operations happens on the class, not on the
instance (classic classes differ from new-style ones in this aspect).

You can use many other ways to implement a ring buffer. In Python
2.4, in particular, you should consider subclassing the new type
collections.deque, which supplies a
"double-ended queue", allowing
equally effective additions and deletions from either
end:

from collections import deque
class RingBuffer(deque):
def _ _init_ _(self, size_max):
deque._ _init_ _(self)
self.size_max = size_max
def append(self, datum):
deque.append(self, datum)
if len(self) > self.size_max:
self.popleft( )
def tolist(self):
return list(self)

or, to avoid the if statement when at steady
state, you can mix this idea with the idea of switching a method:

from collections import deque
class RingBuffer(deque):
def _ _init_ _(self, size_max):
deque._ _init_ _(self)
self.size_max = size_max
def _full_append(self, datum):
deque.append(self, datum)
self.popleft( )
def append(self, datum):
deque.append(self, datum)
if len(self) == self.size_max:
self.append = self._full_append
def tolist(self):
return list(self)

With this latest implementation, we need to switch only the
append method (the tolist method
remains the same), so method switching appears to be more appropriate
than class switching.

See Also

The Reference Manual and Python in
a Nutshell sections on the standard type hierarchy and
classic and new-style object models; Python 2.4 Library
Reference on module
collections.