Python 循環バッファ

Zeeshan Afridi 2023年6月21日

Python Python Buffer

Python での効率的な循環バッファー
Python で循環バッファーを実装する
Python 循環バッファの利点
Python 循環バッファーの欠点
まとめ

循環バッファーは、リングバッファーの別名です。バッファーは、エンドツーエンドで接続されているかのように、単一の固定サイズのバッファーを使用するデータ構造です。

この構造は、データストリームを管理するのに役立ちます。一方の端で新しいデータを常に追加し、もう一方の端から古いデータを削除できます。バッファがいっぱいになると、新しいデータが最も古いデータを上書きします。

Python での効率的な循環バッファー

効率的な循環バッファーは、データの効率的な挿入と削除を可能にするデータ構造です。

循環バッファは通常、配列として実装されます。配列のヘッドポインターは最初の要素を指し、テールポインターは配列の最後の要素を指します。

ヘッドポインターとテールポインターは、配列の末尾に到達するとラップアラウンドします。循環バッファーへの挿入は、ヘッドポインターをインクリメントし、その位置の配列にデータを書き込むことによって行われます。

循環バッファーからの削除は、テールポインターをインクリメントすることによって行われます。そのデータは配列から削除されませんが、ヘッドポインターとテールポインターは実質的にそれをスキップします。

循環バッファは、一定量のメモリしか必要としないため、効率的なデータ構造です。実装も簡単です。

class Buffer:
    def __init__(self, size):
        self.data = [None for i in range(size)]

    def append(self, x):
        self.data.pop(0)
        self.data.append(x)

    def get(self):
        return self.data


buf = Buffer(4)
for i in range(10):
    buf.append(i)
    print(buf.get())

出力：

[None, None, None, 0]
[None, None, 0, 1]
[None, 0, 1, 2]
[0, 1, 2, 3]
[1, 2, 3, 4]
[2, 3, 4, 5]
[3, 4, 5, 6]
[4, 5, 6, 7]
[5, 6, 7, 8]
[6, 7, 8, 9]

Python で循環バッファーを実装する

Python で効率的な循環バッファーを実装する方法は多数あります。一般的なアプローチの 1つは、キューの前と後ろの両方からの要素の削除と追加を効率的にサポートするように設計された collections.dequeue オブジェクトを使用することです。

もう 1つの方法は、リストを使用して、先頭と末尾のインデックスを別々に追跡することです。

どのアプローチが最適かを知りたい場合は、アプリケーション固有の要件によって異なります。たとえば、要素を頻繁にバッファに追加および削除する必要があり、順序が重要でない場合は、dequeue アプローチが最適な場合があります。

一方、要素がバッファに 1 回だけ追加されてから何度も読み出される場合、または順序が重要な場合は、リストアプローチの方が適している可能性があります。

Python で `collections.enqueue` と `collections.dequeue` を使用して循環キューを実装する

まず、関数 collections.enqueue を使用してキューに値を追加します。次に、循環キューで collection.dequeue を使用して、キューから要素を削除できます。

その仕組みを理解するために、Python での循環キューの実際の例を見てみましょう。

コード例:

# implememting circular queue in python
class CircularQueue:
    def __init__(collections, k):
        collections.k = k
        collections.queue = [None] * k
        collections.head = collections.tail = -1

    # this function will insert (Enqueue) an element into the circular queue
    def enqueue1(collections, data):

        if (collections.tail + 1) % collections.k == collections.head:
            print("The queue is full\n")

        elif collections.head == -1:
            collections.head = 0
            collections.tail = 0
            collections.queue[collections.tail] = data
        else:
            collections.tail = (collections.tail + 1) % collections.k
            collections.queue[collections.tail] = data

    # this function will delete (dequeue) an element from the circular
    def dequeue1(collections):
        if collections.head == -1:
            print("The circular queue is empty\n")

        elif collections.head == collections.tail:
            temp = collections.queue[collections.head]
            collections.head = -1
            collections.tail = -1
            return temp
        else:
            temp = collections.queue[collections.head]
            collections.head = (collections.head + 1) % collections.k
            return temp

    # This function is used to print the queue
    def printCQueue1(collections):
        if collections.head == -1:
            print("Circular queue is empty")

        elif collections.tail >= collections.head:
            for i in range(collections.head, collections.tail + 1):
                print(collections.queue[i], end=" ")
            print()
        else:
            for i in range(collections.head, collections.k):
                print(collections.queue[i], end=" ")
            for i in range(0, collections.tail + 1):
                print(collections.queue[i], end=" ")
            print()


obj = CircularQueue(5)

# adding data to the queue
for i in range(1, 6):
    obj.enqueue1(i)

print("Display queue")
obj.printCQueue1()

# removing data from the queue
print("\nDelete Value:", obj.dequeue1())
print("Delete Value:", obj.dequeue1())


print("\nTwo values were deleted from the queue")
print("The new queue has 3 values now")
obj.printCQueue1()

出力：

Display queue
1 2 3 4 5

Delete Value: 1
Delete Value: 2

Two values were deleted from the queue
The new queue has 3 values now
3 4 5