Python Ring Buffer的實(shí)現(xiàn)

本文和大家分享的主要是python中RingBuffer的實(shí)現(xiàn)相關(guān)內(nèi)容，一起來看看吧，希望對(duì)大家學(xué)習(xí)python 有所幫助。

　　RingBuffer，或者說Circular Buffer,是一個(gè)長(zhǎng)度固定的緩沖區(qū)，當(dāng)從一端插入元素超過指定的最大長(zhǎng)度時(shí)，緩沖區(qū)另一端的元素會(huì)溢出。當(dāng)用戶僅對(duì)近期一定長(zhǎng)度的歷史記錄感興趣時(shí)，這種數(shù)據(jù)結(jié)構(gòu)就特別有用。

　　它有三個(gè)要素：

　　* 緩沖區(qū)的長(zhǎng)度固定

　　* 先進(jìn)先出

　　* 當(dāng)往緩沖區(qū)中增加或者刪除元素時(shí)，其它元素的位置保持不變。

　　本文介紹了三種實(shí)現(xiàn)方法及各自的特點(diǎn)。

　　# collections.dequeue實(shí)現(xiàn)

　　RingBuffer的一個(gè)直觀實(shí)現(xiàn)是使用Pyhton collections的dequeue(發(fā)音deck)：

　　``Pythonimport collectionsimport time

　　d = collections.deque(maxlen=1000)

　　tm1 = time.time()for i in range(int(1e6)):

　　d.append(i)

　　print(list(d)[:10])

　　d.clear()

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

　　執(zhí)行結(jié)果如下：

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

　　0.20seconds

　　支持的操作有pop, append;以及從左端操作的popleft, appendleft。但沒有緩沖區(qū)需要的read操作。緩沖區(qū)read操作包括兩個(gè)動(dòng)作，一是從緩沖區(qū)中讀取數(shù)據(jù)；二是在讀取后清除掉數(shù)據(jù)。我們可以通過list(d:dequeue)和clear的組合來實(shí)現(xiàn)這一功能。

　　# 一個(gè)有趣的自定義實(shí)現(xiàn)

　　David Ascher在[這篇文章](# Implementing a Ring Buffer [Book]?)里給出了一個(gè)自定義的實(shí)現(xiàn)：

　　``pythonclass 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 """

　　ret = self.data[self.cur:]+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) == self.max: #line 21

　　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

　　x = RingBuffer(1000)

　　import time

　　tm1 = time.time()for i in range(int(1e6)):

　　x.append(i)

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

　　tm2 = time.time()

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

　　執(zhí)行結(jié)果如下：

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

　　0.64seconds

　　這個(gè)實(shí)現(xiàn)的特點(diǎn)是，使用了數(shù)組，而不是雙端隊(duì)列來作為基礎(chǔ)存儲(chǔ)數(shù)據(jù)結(jié)構(gòu)。當(dāng)然由于Ring Buffer的訪問特性，我們也基本上只對(duì)隊(duì)頭、隊(duì)尾元素進(jìn)行操作，所以無論是使用數(shù)組還是雙端隊(duì)列，操作復(fù)雜度都是O(1)。

　　另一個(gè)值得一提的點(diǎn)是，它使用了動(dòng)態(tài)改變對(duì)象_class_實(shí)現(xiàn)的方式，避免了不必要的判斷語句操作，即在創(chuàng)建之初，緩沖區(qū)未滿時(shí)，每插入一個(gè)元素，都要在第19行處進(jìn)行一次判斷；而一旦緩沖區(qū)被充滿后，RingBuffer對(duì)象升級(jí)為__Full類，從而行為也從此改變--今后再向緩沖區(qū)添加新的元素時(shí)，不再進(jìn)行條件語句判斷。

　　盡管代碼做了足夠的優(yōu)化，python內(nèi)建dequeue的實(shí)現(xiàn)性能更高一些。

　　# 使用C語言的實(shí)現(xiàn)-pyringbuf

　　[sirlark]用C語言實(shí)現(xiàn)了一個(gè)開源的[RingBuffer]，可以通過pip來安裝使用。

　　pip install pyringbuf

這個(gè)模塊提供了push, pop, write, read等函數(shù)，使用示例如下：

　　>>> from ringbuf import RingBuffer

　　>>> R = RingBuffer(5)    #choose your buffer size

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

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

　　'a'

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

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

　　'bcde'

　　>>> R.read(1)

　　'f'

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

這個(gè)模塊以c語言源碼提供，使用前需要編譯。

 

來源： 黑斑馬筆記