リングバッファ

date: 2022-06-29 excerpt: リングバッファ(ring buffer)について

tag: algorithm data structure データ構造 ring buffer

リングバッファ(ring buffer)について

概要

リング状のリストを想像する

各種実装

リストとカーソルで実装する場合

データ挿入時は、tailカーソルから考えて、headに追いついたら入れられない
データ参照時は、headカーソルから考えて、tailに追いついたら未参照のデータはない
データの保持数は、リストのサイズ-1

pythonでの実装例

class RingBuffer:
    def __init__(self, size):
        self.size = size + 1
        self.que = [None]*self.size
        self.head = 0
        self.tail = 0

    def enqueue(self, v):
        nxt = (self.tail + 1)%self.size
        if nxt == self.head:
            print("これ以上データを入れられません")
        else:
            self.que[self.tail] = v
            self.tail = nxt
            print(f"データを{v}を追加しました")
        print(self.que)
    def dequeue(self):
        if self.head == self.tail:
            print("取り出すデータが存在しません")
            return None
        else:
            v = self.que[self.head]
            self.head = (self.head+1)%self.size
            return v

rb = RingBuffer(size=10)
for i in range(10):
    rb.enqueue(i)

for i in range(11):
    v = rb.dequeue()
    print(v)

データが循環する、queueを利用して実装する場合

インデックス操作を入れないため、実装がシンプルで考えやすい
左側からデータが入っていき、一杯になったら古い分はデータが捨てられる
参照してもデータを消すことは無い(再利用する)

pythonでの実装例

import collections
class RingBuffer:
    def __init__(self, size):
        self.que = collections.deque([None]*size)

    def enqueue(self, v):
        self.que.popleft()
        self.que.append(v)

    def dequeue(self):
        v = self.que.pop()
        self.que.appendleft(v)
        return v

rb = RingBuffer(size=10)
for i in range(10):
    rb.enqueue(i)

for i in range(11):
    v = rb.dequeue()
    print(v)