efficient circular buffer?

Question

I want to create an efficient circular buffer in python (with the goal of taking averages of the integer values in the buffer).

Is this an efficient way to use a list to collect values?

def add_to_buffer( self, num ):
    self.mylist.pop( 0 )
    self.mylist.append( num )

What would be more efficient (and why)?

Solution 1

I would use collections.deque with a maxlen arg

>>> import collections
>>> d = collections.deque(maxlen=10)
>>> d
deque([], maxlen=10)
>>> for i in xrange(20):
...     d.append(i)
... 
>>> d
deque([10, 11, 12, 13, 14, 15, 16, 17, 18, 19], maxlen=10)

There is a recipe in the docs for deque that is similar to what you want. My assertion that it's the most efficient rests entirely on the fact that it's implemented in C by an incredibly skilled crew that is in the habit of cranking out top notch code.

Solution 2

Although there are already a great number of great answers here, I could not find any direct comparison of timings for the options mentioned. Therefore, please find my humble attempt at a comparison below.

For testing purposes only, the class can switch between a list-based buffer, a collections.deque-based buffer, and a Numpy.roll-based buffer.

Note that the update method adds only one value at a time, to keep it simple.

import numpy
import timeit
import collections


class CircularBuffer(object):
    buffer_methods = ('list', 'deque', 'roll')

    def __init__(self, buffer_size, buffer_method):
        self.content = None
        self.size = buffer_size
        self.method = buffer_method

    def update(self, scalar):
        if self.method == self.buffer_methods[0]:
            # Use list
            try:
                self.content.append(scalar)
                self.content.pop(0)
            except AttributeError:
                self.content = [0.] * self.size
        elif self.method == self.buffer_methods[1]:
            # Use collections.deque
            try:
                self.content.append(scalar)
            except AttributeError:
                self.content = collections.deque([0.] * self.size,
                                                 maxlen=self.size)
        elif self.method == self.buffer_methods[2]:
            # Use Numpy.roll
            try:
                self.content = numpy.roll(self.content, -1)
                self.content[-1] = scalar
            except IndexError:
                self.content = numpy.zeros(self.size, dtype=float)

# Testing and Timing
circular_buffer_size = 100
circular_buffers = [CircularBuffer(buffer_size=circular_buffer_size,
                                   buffer_method=method)
                    for method in CircularBuffer.buffer_methods]
timeit_iterations = 1e4
timeit_setup = 'from __main__ import circular_buffers'
timeit_results = []
for i, cb in enumerate(circular_buffers):
    # We add a convenient number of convenient values (see equality test below)
    code = '[circular_buffers[{}].update(float(j)) for j in range({})]'.format(
        i, circular_buffer_size)
    # Testing
    eval(code)
    buffer_content = [item for item in cb.content]
    assert buffer_content == range(circular_buffer_size)
    # Timing
    timeit_results.append(
        timeit.timeit(code, setup=timeit_setup, number=int(timeit_iterations)))
    print '{}: total {:.2f}s ({:.2f}ms per iteration)'.format(
        cb.method, timeit_results[-1],
        timeit_results[-1] / timeit_iterations * 1e3)

On my system this yields:

list:  total 1.06s (0.11ms per iteration)
deque: total 0.87s (0.09ms per iteration)
roll:  total 6.27s (0.63ms per iteration)

Solution 3

popping from the head of a list causes the whole list to be copied, so is inefficient

You should instead use a list/array of fixed size and an index which moves through the buffer as you add/remove items

Solution 4

Based on MoonCactus's answer, here is a circularlist class. The difference with his version is that here c[0] will always give the oldest-appended element, c[-1] the latest-appended element, c[-2] the penultimate... This is more natural for applications.

c = circularlist(4)
c.append(1); print(c, c[0], c[-1])    #[1] (1/4 items)              1  1
c.append(2); print(c, c[0], c[-1])    #[1, 2] (2/4 items)           1  2
c.append(3); print(c, c[0], c[-1])    #[1, 2, 3] (3/4 items)        1  3
c.append(8); print(c, c[0], c[-1])    #[1, 2, 3, 8] (4/4 items)     1  8
c.append(10); print(c, c[0], c[-1])   #[2, 3, 8, 10] (4/4 items)    2  10
c.append(11); print(c, c[0], c[-1])   #[3, 8, 10, 11] (4/4 items)   3  11
d = circularlist(4, [1, 2, 3, 4, 5])  #[2, 3, 4, 5]

Class:

class circularlist(object):
    def __init__(self, size, data = []):
        """Initialization"""
        self.index = 0
        self.size = size
        self._data = list(data)[-size:]

    def append(self, value):
        """Append an element"""
        if len(self._data) == self.size:
            self._data[self.index] = value
        else:
            self._data.append(value)
        self.index = (self.index + 1) % self.size

    def __getitem__(self, key):
        """Get element by index, relative to the current index"""
        if len(self._data) == self.size:
            return(self._data[(key + self.index) % self.size])
        else:
            return(self._data[key])

    def __repr__(self):
        """Return string representation"""
        return (self._data[self.index:] + self._data[:self.index]).__repr__() + ' (' + str(len(self._data))+'/{} items)'.format(self.size)

Solution 5

ok with the use of deque class, but for the requeriments of the question (average) this is my solution:

>>> from collections import deque
>>> class CircularBuffer(deque):
...     def __init__(self, size=0):
...             super(CircularBuffer, self).__init__(maxlen=size)
...     @property
...     def average(self):  # TODO: Make type check for integer or floats
...             return sum(self)/len(self)
...
>>>
>>> cb = CircularBuffer(size=10)
>>> for i in range(20):
...     cb.append(i)
...     print "@%s, Average: %s" % (cb, cb.average)
...
@deque([0], maxlen=10), Average: 0
@deque([0, 1], maxlen=10), Average: 0
@deque([0, 1, 2], maxlen=10), Average: 1
@deque([0, 1, 2, 3], maxlen=10), Average: 1
@deque([0, 1, 2, 3, 4], maxlen=10), Average: 2
@deque([0, 1, 2, 3, 4, 5], maxlen=10), Average: 2
@deque([0, 1, 2, 3, 4, 5, 6], maxlen=10), Average: 3
@deque([0, 1, 2, 3, 4, 5, 6, 7], maxlen=10), Average: 3
@deque([0, 1, 2, 3, 4, 5, 6, 7, 8], maxlen=10), Average: 4
@deque([0, 1, 2, 3, 4, 5, 6, 7, 8, 9], maxlen=10), Average: 4
@deque([1, 2, 3, 4, 5, 6, 7, 8, 9, 10], maxlen=10), Average: 5
@deque([2, 3, 4, 5, 6, 7, 8, 9, 10, 11], maxlen=10), Average: 6
@deque([3, 4, 5, 6, 7, 8, 9, 10, 11, 12], maxlen=10), Average: 7
@deque([4, 5, 6, 7, 8, 9, 10, 11, 12, 13], maxlen=10), Average: 8
@deque([5, 6, 7, 8, 9, 10, 11, 12, 13, 14], maxlen=10), Average: 9
@deque([6, 7, 8, 9, 10, 11, 12, 13, 14, 15], maxlen=10), Average: 10
@deque([7, 8, 9, 10, 11, 12, 13, 14, 15, 16], maxlen=10), Average: 11
@deque([8, 9, 10, 11, 12, 13, 14, 15, 16, 17], maxlen=10), Average: 12
@deque([9, 10, 11, 12, 13, 14, 15, 16, 17, 18], maxlen=10), Average: 13
@deque([10, 11, 12, 13, 14, 15, 16, 17, 18, 19], maxlen=10), Average: 14

View more solutions

Comments

[Admin]

Agree. No matter how elegant or inelegant it may look or whatever language is used. In reality, the less you bother garbage collector (or heap manager or paging/mapping mechanisms or whatever does actual memory magic) the better.

[John La Rooy]

+1 Yes it's the nice batteries included way. Operations for the circular buffer are O(1) and as you say the extra overhead is in C, so should still be quite fast

[Christian]

@RocketSurgeon It's not magic, it's just that it's an array whose first element is deleted. So for an array of size n this means n-1 copy operations. No garbage collector or similar device is involved here.

[Andre Blum]

I agree. Doing so is also much easier than some people think. Just use an ever increasing counter, and use the modulo operator (% arraylen) when accessing the item.

[scls]

I get TypeError: 'numpy.float64' object is not callable when trying to call average method

[scls]

Yes... in fact I guess that deque uses numpy arrays internally (after removing @property it works fine)

[Admin]

I guarantee that deque does not use numpy arrays internally. collections is part of the standard library, numpy is not. Dependencies on third party libraries would make for a terrible standard library.

[MoonCactus]

idem, you may check my post above, that is how I did it

[lvella]

I don't like this solution because the docs doesn't guarantee O(1) random access when maxlen is defined. O(n) is understandable when the deque can grow to infinity, but if maxlen is given, indexing an element should be constant time.

[e-satis]

My guess is that its implemented as a linked list and not an array.

[Bas Swinckels]

+1 for using numpy, but -1 for not implementing a circular buffer. The way you implemented it, you are shifting all data every time you add a single element, this costs O(n) time. To implement a proper circular buffer, you should have both an index and a size variable, and you need to correctly handle the case when the data 'wraps around' the end of the buffer. When retrieving data, you might have to concatenate two sections at the start and end of the buffer.

[djvg]

But numpy.roll returns a copy of the array, right?

[djvg]

Seems about right, if the timings in my answer below are correct.

[Mateen Ulhaq]

Shouldn't your __getitem__ be a bit more powerful: self._data[(key + self._index + 1) % self._size]?

[MoonCactus]

Why would you want to shift by +1 ? Now, yes, see Basj variant below for the idea

[MoonCactus]

Good addition. Python lists already allow negative indices, but (-1), e.g. would not return the expected value once the circular buffer is full, since the "last" addition to the list ends up within the list.

[Basj]

It does work @MoonCactus, see the 6 examples I gave on top of the answer; in the last ones, you can see c[-1] is always the right element. __getitem__ does it right.

[MoonCactus]

oh yes, I mean mine failed, not yours, sorry :D I will make my comment clearer! -- oh I cannot, the comment is too old.

[Orwellophile]

nice simple solution. i added an optional argument to allow initialization of the list from existing data, it's more pythonpathetic that way.

[PolyMesh]

I did some speed tests of this vs deque. This is about 7 times slower than deque.

[d8aninja]

@PolyMesh awesome, you should let the author know!

[PolyMesh]

what would be the point of that? It's an old published document. The point of my comment is to let others know that this answer is out of date and to use deque instead.

[d8aninja]

@PolyMesh it was probably still slower when he published it; instructions for contacting the author are in the intro to the book. I'm just relating one, possible alternative. Also, "If only speed were the best metric; alas it may only be a good one."

[xitrium]

This answer is very misleading - Python's deque appears to be quite fast, but converting from and to numpy arrays slows it down considerably in the benchmarks you link to.

[Connor]

@d8aninja deque also has a .clear() function. Which this does not (and from what I can tell, cannot)

[d8aninja]

@Connor this is an instructive example from a cookbook, meant to be simplistic and intended for people to start with making their own (hence, "cookbook"). Deque is awesome, I'm glad you're enjoying it.

[Mike T.]

Apart from keeping count of the number of items processed is there a way of Iterating over the member of this circular list just once? for i in c: iterates forever... Thanks – Mike T.

[user1504]

Your timing code has a flaw. You call append 40000 times after setting max_size to 1000000, so you only ever test the append method of the underlying list.

[MoonCactus]

You are right; but I hardly see how it would become slower than dequeue when it happens (appends are slower than replacement - due to possible memory reallocation). Since my code was enhanced by @basj above (who naturally gets more credits for it), I leave it for others to spend more time on this and check this ;)

[OrangeDog]

@Ivella if maxlen is given, then n has a fixed bound, therefore everything by definition is constant time ;)

[Joost Kremers]

There seem to be two problems with this code. First, when the list isn't full yet, the index doesn't wrap. If I do c=circularlist(5, [1,2]) I cannot do c[2], but once the list is full, it's possible to do c[5]. Second, c=circularlist(5); c.append(1) should yield the same list as c=circularlist(5, [1]), but it does not. In the former case, c.index is 1, in the latter, however, it is 0.

[blubberdiblub]

@OrangeDog O(maxlen) is no different from O(n). Just a different variable name used for the same idea. Hence it's not constant time. The access time (in the worst case) is roughly proportional to maxlen, which is runtime-controlled (the deque is allocated at runtime). What Ivella was referring to is that it's possible (in theory) to vary the implementation and keep using a linked list for the unbounded case and for the bounded case allocate a fixed contiguous chunk of memory. However, that would potentially waste memory if the fill level commonly stays significantly below the bound.

[blubberdiblub]

The actual python implementation (see here: github.com/python/cpython/blob/main/Modules/… ) uses a hybrid of both ideas: a linked list of fixed size chunks. I.e. it splits the deque up into equally sized pieces of memory, internally. That will alleviate some of the cost of a purely linked list implementation, but the access time for inner items of a long deque is still O(maxlen) (a.k.a. O(n))

[Bas Swinckels]

-1 As can be seen in the source of numpy.roll, it calculates slices for the first and second half of the old array, creates a new array (with empty_like) and then copies the swapped halves to the new one. This is O(n), since you always copy the whole array.