3.1.2. リングバッファ¶

Code: ringbuffer.py

Test: test_ringbuffer.py

リングバッファとは¶

Circular buffer (Wikipedia)

固定長の配列を用いて両端キューの機能を実現するデータ構造のこと。

実装¶

概要¶

両端キューとして使用可能な、長さ \(n\) のリングバッファを実装する。

実装のポイント¶

リングバッファの末尾に、バッファの先頭を指すindexと要素数を記録するようにした。

計算量¶

操作	メソッド	計算量
初期化	`ringbuffer`	\(\mathcal{O}(n)\)
末尾に追加	`rb_append`	\(\mathcal{O}(1)\)
先頭に追加	`rb_appendleft`	\(\mathcal{O}(1)\)
末尾を削除	`rb_pop`	\(\mathcal{O}(1)\)
先頭を削除	`rb_popleft`	\(\mathcal{O}(1)\)
末尾を参照	`rb_peek`	\(\mathcal{O}(1)\)
先頭を参照	`rb_peekleft`	\(\mathcal{O}(1)\)
要素数を取得	`rb_size`	\(\mathcal{O}(1)\)

コード¶

[1]:

import numpy as np
from numba import njit, i8


def ringbuffer(size: int) -> i8[:]:
    q = np.zeros((size+2, ), dtype=np.int64)
    q[-2] = 0
    q[-1] = 0
    return q


@njit((i8[:], i8), cache=True)
def rb_append(q: i8[:], v: i8) -> None:
    head, size = q[-2], q[-1]
    qmax = q.size - 2
    tail = (head + size) % qmax
    q[tail] = v
    q[-1] += 1


@njit((i8[:], i8), cache=True)
def rb_appendleft(q: i8[:], v: i8) -> None:
    head, size = q[-2], q[-1]
    qmax = q.size - 2
    head = (head - 1) % qmax
    q[head] = v
    q[-2] = head
    q[-1] += 1


@njit(i8(i8[:]), cache=True)
def rb_pop(q: i8[:]) -> i8:
    head, size = q[-2], q[-1]
    qmax = q.size - 2
    tail = (head + size - 1) % qmax
    v = q[tail]
    q[-1] -= 1
    return v


@njit(i8(i8[:]), cache=True)
def rb_popleft(q: i8[:]) -> i8:
    head, size = q[-2], q[-1]
    qmax = q.size - 2
    v = q[head]
    head = (head + 1) % qmax
    q[-2] = head
    q[-1] -= 1
    return v


@njit(i8(i8[:]), cache=True)
def rb_peek(q: i8[:]) -> i8:
    head, size = q[-2], q[-1]
    qmax = q.size - 2
    tail = (head + size - 1) % qmax
    v = q[tail]
    return v


@njit(i8(i8[:]), cache=True)
def rb_peekleft(q: i8[:]) -> i8:
    head, size = q[-2], q[-1]
    v = q[head]
    return v


@njit(i8(i8[:]), cache=True)
def rb_size(q: i8[:]) -> i8:
    return q[-1]

使用例¶

[2]:

q = ringbuffer(100)
rb_append(q, 1)
rb_append(q, 2)
rb_append(q, 3)
rb_append(q, 4)
print(rb_pop(q))
print(rb_peek(q))
print(rb_popleft(q))
print(rb_peekleft(q))
print(rb_size(q))