理解Python中的RingBuffer环形缓冲区_python ringbuffer

ringbuffer

Refered from Wikipedia, a ring buffer(环形缓冲区 or circular buffer, circular queue, cyclic buffer) is a data strcture that uses a single, fixed-size buffer as if it were connected end-to-end.

This structure lends itself easily to buffering data streams.

buffer

First, we should know what the “BUFFER” is in computer science.

According Wikipedia, a data buffer (or just buffer) is a region of a physical memory storage used to temporarily store data while it is being moved from one place to another.

Typically, the data is stored in a buffer as it is retrieved from an input device or just befor it is sent to an output device.

However, a buffer may be used when moving data between processes within a computer.

LMAX Disruptor 中 ringbuffer

LMAX是伦敦多元资产交易所的简称，https://www.lmax.com/

其开源的LMAX Disruptor可以处理数百万订单/秒。ringbuffer是其一大利器。

ringbuffer用于在不同上下文（线程）间传递数据的buffer。

ringbuffer是数据（数组内元素的内存地址是连续性存储的）比链表快。

Python中实现ringbuffer

网上相关资料不多。

1. 自己实现

   refer from ：

   class RingBuffer:
       def __init__(self, size):
           self.data = [None for i in range(size)]
       
       def append(self, x):
           self.data.pop(0) # remove the last one which index = -1
           self.data.append(x) # add at the index = -1
       
       def get(self):
           return self.data
   
   buf = RingBuffer(4)
   for i in range(10):
       buf.append(i)
       print(buf.get())
   1
   2
   3
   4
   5
   6
   7
   8
   9
   10
   11
   12
   13
   14
   15

   Python Cookbook by Alex Martelli, David Ascher 中有一种相对完善的实现：

   class RingBuffer:
       """ class that implements a not-yet-full buffer """
       def __init__(self,size_max):
           self.max = size_max
           self.data = []
   
       class __Full:
           """ 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 get(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_ _ = self._ _Full
   
       def get(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.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(  )
   1
   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
   36
   37
   38
   39

2. Python模块collections.deque

   class collections.deque([iterable[, maxlen]])

   deque对象返回一个新的双向队列对象。

3. Python模块pyringbuf

   这个模块在2015年之后就没有更新了

References