理解Python中的RingBuffer环形缓冲区

大家好，又见面了，我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全系列IDE使用 1年只要46元 售后保障 童叟无欺

• 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())
     

     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(  )
     

  2. Python模块collections.deque

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

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

  3. Python模块pyringbuf

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

• References

1. 剖析Disruptor:为什么会这么快？（一）Ringbuffer的特别之处
2. 并发框架Disruptor译文
3. disruptor – BlogsAndArticles.wiki
4. Trisha’s Ramblings