Python で「両端キュー」として使えるデータ型 collections.deque

最近「Python チュートリアル 第3版」を読んでいて，11章で紹介されている collections.deque を実際に使ったことがなく，ドキュメントを読みながら動作確認をした．Python 3.2 と Python 3.5 で追加されたメソッドもあり，メモ程度にまとめておこうと思う．

Pythonチュートリアル 第3版

deque (double-ended queue) とは？

ドキュメントを読むと collections.deque の説明は以下のように書かれている．特に「どちらの側からも append と pop が可能」という点がポイントで「スタックとしてもキューとしても」使うことができる．正直言って，最初に deque を見たときに「デキュー」と読むのかな？と思ったけど，正しくは「デック」だった．「デキュー」は dequeue だから間違える人もいそう．日本語だと「両端キュー」とも言う．

• 8.3. collections — コンテナデータ型 — Python 3.6.5 ドキュメント

Deque とは、スタックとキューを一般化したものです (この名前は「デック」と発音され、これは「double-ended queue」の省略形です)。Deque はどちらの側からも append と pop が可能で、スレッドセーフでメモリ効率がよく、どちらの方向からもおよそ O(1) のパフォーマンスで実行できます。

前提

今回は Python 3.7.1 で動作確認をした．

$ python --version
Python 3.7.1

基本操作

まず，以下の基本操作を試した．

• append()
• appendleft()
• pop()
• popleft()

append() と pop() は deque オブジェクトの右側を操作し，appendleft() と popleft() は名前の通り，deque オブジェクトの左側を操作する．

from collections import deque

d = deque(['B', 'C', 'D'])

# deque(['B', 'C', 'D'])
print(d)

# deque(['B', 'C', 'D', 'E'])
d.append('E')
print(d)

# deque(['A', 'B', 'C', 'D', 'E'])
d.appendleft('A')
print(d)

# E
print(d.pop())

# A
print(d.popleft())

# deque(['B', 'C', 'D'])
print(d)

最大長

deque オブジェクトを作成するときに，第2引数に maxlen を指定することができる（オプション）．maxlen を指定すると deque オブジェクトの最大長となる．

class collections.deque([iterable[, maxlen]])

さらに maxlen() を使うと，deque オブジェクトの最大長を確認できる．そして，気になるのは指定した maxlen を超えたときの挙動で，ドキュメントには「追加したのと反対側から要素が捨てられる」と書いてあった．

長さが制限された deque がいっぱいになると、新しい要素を追加するときに追加した要素数分だけ追加したのと反対側から要素が捨てられます。

実際に 6 を append() すると，左側にある 1 が捨てられて，もう1度 1 を appendleft() すると，右側にある 6 が捨てられた．ドキュメントの通りに「反対側」から捨てられた．

from collections import deque

# deque([1, 2, 3, 4, 5], maxlen=5)
# 5
d = deque([1, 2, 3, 4, 5], 5)
print(d)
print(d.maxlen)

# deque([2, 3, 4, 5, 6], maxlen=5)
d.append(6)
print(d)

# deque([1, 2, 3, 4, 5], maxlen=5)
d.appendleft(1)
print(d)

さらに deque オブジェクトを作成するときに，既に maxlen を超えている状態にしたところ，左側から捨てられた．

from collections import deque

# deque([4, 5, 6], maxlen=3)
# 3
d = deque([1, 2, 3, 4, 5, 6], 3)
print(d)
print(d.maxlen)

反転

次に Python 3.2 で追加された reverse() を確認した．reverse() は deque オブジェクトを反転し None を返すため，破壊的にオブジェクトを更新する．

from collections import deque

d = deque([1, 2, 3, 4, 5])

# deque([5, 4, 3, 2, 1])
d.reverse()
print(d)

浅いコピー

次に Python 3.5 で追加された copy() を確認した．copy() は deque オブジェクトの「浅いコピー」を作成できる．

from collections import deque

d1 = deque([1, 2, 3, 4, 5])
d2 = d1.copy()

# deque([1, 2, 3, 4, 5])
# deque([1, 2, 3, 4, 5])
print(d1)
print(d2)

d1.append(6)

# deque([1, 2, 3, 4, 5, 6])
# deque([1, 2, 3, 4, 5])
print(d1)
print(d2)

Python の「浅いコピー」に関しては以下に書いてある．

• 8.10. copy — 浅いコピーおよび深いコピー操作 — Python 3.6.5 ドキュメント

インデックス検索

次に Python 3.5 で追加された index() を確認した．index() は deque オブジェクトの中から指定した値の位置を返す．複数該当する場合は，最初の位置を返す．該当しない場合は ValueError 例外を返す．

from collections import deque

# 1
d = deque([1, 2, 3, 4, 5])
print(d.index(2))

挿入

次に Python 3.5 で追加された insert() を確認した．insert() は deque オブジェクトの任意の場所に値を挿入する．左右以外にも挿入できるため，スタックとキューでは行えない操作もできる．当然ながら，中央部分に挿入する場合は O(n) の計算量になる．

from collections import deque

d = deque([1.0, 2.0, 3.0, 4.0, 5.0])

# deque([1.0, 2.0, 3.0, 4.0, 5.0])
print(d)

d.insert(3, 3.5)

# deque([1.0, 2.0, 3.0, 3.5, 4.0, 5.0])
print(d)

動作確認 : PyCharm Python Console

インタラクティブに動作確認をする場合に「PyCharm Python Console」を使っている．Python インタプリタではなく IPython を使うとして，「PyCharm Python Console」を使うと，同時に変数なども確認できて便利．

ドキュメント化 : Jupyter Notebook

動作確認をしながらメモを残す場合に，インラインコメントを付ける以外に「Jupyter Notebook」を使って，Markdown でドキュメント化してしまう方法もある．特に仮想サーバを構築する必要もなく，ローカル環境で jupyter notebook と実行すれば良くて，お手軽に使うことができる．

jupyter.org

以下は collections.deque のドキュメントにあるサンプルコードを「Jupyter Notebook」でドキュメント化して，さらに GitHub に push している．「コメント」と「コード」と「実行結果」を確認できるので，今後見直す場合にも効率的に思い出せる．

GitHub は2015年に対応していて，そのまま .ipynb を push すると，GitHub で「Jupyter Notebook」を閲覧することができる．

blog.github.com

まとめ

• Python で使ったことがなかった collections.deque の動作確認をした
  • deque は「デキュー」ではなく「デック」と読む
• collections.deque には Python 3.2 と Python 3.5 で追加されたメソッドもあった
  • insert() を使うと任意の場所に値を挿入できる（もはや「両端キュー」ではない）
• 動作確認には「PyCharm Python Console」を使って，ドキュメント化には「Jupyter Notebook」を使うと便利