こんにちは、JS2IIUです。
今回はcollectionモジュールに含まれるデータ構造であるdequeについて紹介します。私は、通信データを受け入れて管理するためのローリングバッファにこのdequeを使っています。今回もよろしくお願いします。
1. dequeとは？
Pythonのcollectionsモジュールに含まれるdeque（double-ended queue）は、両端からの高速な要素の追加・削除を可能にするデータ構造です。リストと似ていますが、特定の操作においてパフォーマンスが大きく異なります。
1.1 リストとdequeの違い
| 操作 | dequeの時間計算量 | リストの時間計算量 |
|---|---|---|
| 末尾への追加 | O(1) | O(1) |
| 先頭への追加 | O(1) | O(n) |
| 末尾からの削除 | O(1) | O(1) |
| 先頭からの削除 | O(1) | O(n) |
リストでは先頭に要素を追加・削除する場合、すべての要素をシフトする必要があるためO(n)の時間がかかりますが、dequeではO(1)で実行できます。
2. dequeの主な特徴
2.1 スタック（LIFO）・キュー（FIFO）両方に対応
dequeは以下のメソッドを使うことで、スタックやキューとして利用できます。
append(item)：右端に要素を追加（enqueue、pushに相当）appendleft(item)：左端に要素を追加pop()：右端から要素を削除（LIFOのpopに相当）popleft()：左端から要素を削除（FIFOのdequeueに相当）
2.2 回転（rotate）操作
dequeは要素を回転させることが可能です。
rotate(n)：要素を右にn回転（負の値で左に回転）
例えば、rotate(1)を実行すると最後の要素が先頭に移動します。
3. 実践例：ローリングバッファ
以下は、dequeを使用して通信データを一定サイズで保持するローリングバッファを実装する例です。
3.1 サンプルコード
from collections import deque
def process_data():
buffer_size = 5
data_buffer = deque(maxlen=buffer_size)
# データをバッファに追加
for i in range(10):
data_buffer.append(i)
print(f"Buffer: {list(data_buffer)}")
# 最新のデータを処理
print("Processing the latest 3 items:")
for _ in range(3):
item = data_buffer.pop()
print(f"Processing: {item}")
process_data()3.2 コード解説
deque(maxlen=buffer_size)：最大長を指定することで、上限を超えた場合に古い要素が自動的に削除される。append()：新しいデータを右端に追加。pop()：最新のデータを取り出して処理。
このプログラムでは、新しいデータがバッファに追加されるたびに、古いデータが自動的に削除されます。
3.3 実行結果
Buffer: [0]
Buffer: [0, 1]
Buffer: [0, 1, 2]
Buffer: [0, 1, 2, 3]
Buffer: [0, 1, 2, 3, 4]
Buffer: [1, 2, 3, 4, 5]
Buffer: [2, 3, 4, 5, 6]
Buffer: [3, 4, 5, 6, 7]
Buffer: [4, 5, 6, 7, 8]
Buffer: [5, 6, 7, 8, 9]
Processing the latest 3 items:
Processing: 9
Processing: 8
Processing: 74. まとめ
dequeは両端からの高速な追加・削除を可能にし、スタック・キューの両方として使用できる強力なデータ構造です。特に、ローリングバッファのように最新データを一定数だけ保持する場合に非常に有効です。
5. 参考リンク
最後に、書籍のPRです。
24年9月に出版された「ハイパーモダンPython-信頼性の高いワークフローを構築するモダンテクニック」、Claudio Jolowicz著、嶋田、鈴木訳。開発環境の構築、プロジェクトの管理、テストに関して実践的な内容でとても参考になる一冊です。ぜひ手に取ってみてください。
最後まで読んでいただきありがとうございます。
コメント