cringbuffer源码_PythonRingBuffer的实现

RingBuffer&＃xff0c;或者说Circular Buffer,是一个长度固定的缓冲区&＃xff0c;当从一端插入元素超过指定的最大长度时&＃xff0c;缓冲区另一端的元素会溢出。当用户仅对近期一定长度的历史记录感兴趣时&＃xff0c;这种数据结构就特别有用。

* 缓冲区的长度固定

* 先进先出

* 当往缓冲区中增加或者删除元素时&＃xff0c;其它元素的位置保持不变。

本文介绍了三种实现方法及各自的特点。

# collections.dequeue实现

RingBuffer的一个直观实现是使用Pyhton collections的dequeue(发音deck)&＃xff1a;

&＃96;&＃96;&＃96;Python

import collections

import time

d &＃61; collections.deque(maxlen&＃61;1000)

tm1 &＃61; time.time()

for i in range(int(1e6)):

d.append(i)

print(list(d)[:10])

d.clear()

tm2 &＃61; time.time()

print("{:.2f}seconds".format(tm2 - tm1))

执行结果如下&＃xff1a;

[999000, 999001, 999002, 999003, 999004, 999005, 999006, 999007, 999008, 999009]

0.20seconds

支持的操作有pop, append;以及从左端操作的popleft, appendleft。但没有缓冲区需要的read操作。缓冲区read操作包括两个动作&＃xff0c;一是从缓冲区中读取数据&＃xff1b;二是在读取后清除掉数据。我们可以通过list(d:dequeue)和clear的组合来实现这一功能。

# 一个有趣的自定义实现

David Ascher在[这篇文章](#Implementing a Ring Buffer [Book])里给出了一个自定义的实现&＃xff1a;

&＃96;&＃96;&＃96;python

class RingBuffer:

""" class that implements a not-yet-full buffer """

def __init__(self,size_max):

self.max &＃61; size_max

self.data &＃61; []

class __Full:

""" class that implements a full buffer """

def append(self, x):

""" Append an element overwriting the oldest one. """

self.data[self.cur] &＃61; x

self.cur &＃61; (self.cur&＃43;1) % self.max

def get(self):

""" return list of elements in correct order """

ret &＃61; self.data[self.cur:]&＃43;self.data[:self.cur]

self.data.clear()

return ret

def append(self,x):

"""append an element at the end of the buffer"""

self.data.append(x)

if len(self.data) &＃61;&＃61; self.max: #line 21

self.cur &＃61; 0

# Permanently change self&＃39;s class from non-full to full

self.__class__ &＃61; self.__Full

def get(self):

""" Return a list of elements from the oldest to the newest. """

return self.data

x &＃61; RingBuffer(1000)

import time

tm1 &＃61; time.time()

for i in range(int(1e6)):

x.append(i)

print(x.get()[:10])

tm2 &＃61; time.time()

print("{:.2f}seconds".format(tm2 - tm1))

执行结果如下&＃xff1a;

[999000, 999001, 999002, 999003, 999004, 999005, 999006, 999007, 999008, 999009]

0.64seconds

这个实现的特点是&＃xff0c;使用了数组&＃xff0c;而不是双端队列来作为基础存储数据结构。当然由于Ring Buffer的访问特性&＃xff0c;我们也基本上只对队头、队尾元素进行操作&＃xff0c;所以无论是使用数组还是双端队列&＃xff0c;操作复杂度都是O(1)。

另一个值得一提的点是&＃xff0c;它使用了动态改变对象_class_实现的方式&＃xff0c;避免了不必要的判断语句操作&＃xff0c;即在创建之初&＃xff0c;缓冲区未满时&＃xff0c;每插入一个元素&＃xff0c;都要在第19行处进行一次判断&＃xff1b;而一旦缓冲区被充满后&＃xff0c;RingBuffer对象升级为__Full类&＃xff0c;从而行为也从此改变--今后再向缓冲区添加新的元素时&＃xff0c;不再进行条件语句判断。

尽管代码做了足够的优化&＃xff0c;python内建dequeue的实现性能更高一些。

# 使用C语言的实现-pyringbuf

[sirlark](#sirlark)用C语言实现了一个开源的[RingBuffer](#pyringbuf 0.1b2 : Python Package Index)&＃xff0c;可以通过pip来安装使用。

pip install pyringbuf

这个模块提供了push, pop, write, read等函数&＃xff0c;使用示例如下&＃xff1a;

>>> from ringbuf import RingBuffer

>>> R &＃61; RingBuffer(5) #choose your buffer size

>>> R.push("a") #push a single character into the buffer

>>> R.pop() #pop a single character

&＃39;a&＃39;

>>> R.write("bcdef") #fill buffer with many characters at once

>>> R.read(4) #read many characters at once

&＃39;bcde&＃39;

>>> R.read(1)

&＃39;f&＃39;

>>> R.read(1) #returns an empty string if the buffer is empty

这个模块以c语言源码提供&＃xff0c;使用前需要编译。