Caution
お使いのブラウザはJavaScriptが実行できない状態になっております。
当サイトはWebプログラミングの情報サイトの為、
JavaScriptが実行できない環境では正しいコンテンツが提供出来ません。
JavaScriptが実行可能な状態でご閲覧頂くようお願い申し上げます。
collections.deque() / collections.OrderedDict()
『collections.deque』は両端キュー（double-ended queue）を提供するクラスで、先頭・末尾どちらからでも高速にO(1)で要素を追加・削除できます。通常のリストで先頭操作を行うとO(n)のコストがかかりますが、dequeを使えば先頭操作もO(1)で実行できます。また『collections.OrderedDict』は挿入順を保持する辞書で、Python 3.7以降の通常の辞書も挿入順を保証しますが、OrderedDictは順序に基づく比較や移動操作を提供します。
構文
from collections import deque, OrderedDict # dequeの生成 dq = deque([初期要素], maxlen=最大長) # OrderedDictの生成 od = OrderedDict()
関数・メソッド一覧
| 関数・メソッド | 概要 |
|---|---|
| deque(iterable) | 両端キューを生成する。maxlenを指定すると最大長を制限できる。 |
| dq.append(x) | 右端に要素xを追加する。 |
| dq.appendleft(x) | 左端に要素xを追加する。 |
| dq.pop() | 右端の要素を取り出して返す。 |
| dq.popleft() | 左端の要素を取り出して返す。 |
| dq.rotate(n) | 要素をn個分右に回転する（負の値で左回転）。 |
| dq.extend(iterable) | 右端に複数の要素を追加する。 |
| dq.extendleft(iterable) | 左端に複数の要素を逆順で追加する。 |
| OrderedDict() | 挿入順を保持する辞書を生成する。 |
| od.move_to_end(key) | 指定したキーを末尾（または先頭）に移動する。 |
| od.popitem(last=True) | 末尾（last=Falseで先頭）のアイテムを取り出す。 |
サンプルコード
from collections import deque, OrderedDict
# dequeの基本操作
dq = deque([1, 2, 3])
dq.append(4) # 右端に追加 → [1, 2, 3, 4]
dq.appendleft(0) # 左端に追加 → [0, 1, 2, 3, 4]
print(dq) # deque([0, 1, 2, 3, 4])
dq.pop() # 右端を取り出す → 4
dq.popleft() # 左端を取り出す → 0
print(dq) # deque([1, 2, 3])
# rotate: n個分右に回転
dq.rotate(1)
print(dq) # deque([3, 1, 2])
# maxlenを指定すると溢れた要素が自動的に削除される
dq2 = deque(maxlen=3)
for i in range(5):
dq2.append(i)
print(dq2) # deque([2, 3, 4], maxlen=3)
# OrderedDictの基本操作
od = OrderedDict()
od['a'] = 1
od['b'] = 2
od['c'] = 3
print(list(od.keys())) # ['a', 'b', 'c']
# キーを末尾に移動
od.move_to_end('a')
print(list(od.keys())) # ['b', 'c', 'a']
# キーを先頭に移動
od.move_to_end('a', last=False)
print(list(od.keys())) # ['a', 'b', 'c']
# popitemで末尾のアイテムを取り出す
key, val = od.popitem(last=True)
print(key, val) # c 3
概要
『deque』は最大長（maxlen）を設定することで、固定サイズのキューやスライディングウィンドウとして活用できます。maxlenを超えて要素を追加すると、反対側の端から要素が自動的に押し出されます。キュー（FIFO）やスタック（LIFO）の用途にも適しており、リストの代わりにdequeを使うことで先頭操作のパフォーマンスを大幅に改善できます。
『OrderedDict』はPython 3.7以降では通常の辞書も挿入順を保証するようになりましたが、OrderedDictには『move_to_end()』や順序を考慮した等値比較など、通常の辞書にはない機能があります。LRU（Least Recently Used）キャッシュの実装などに利用されます。
記事の間違いや著作権の侵害等ございましたらお手数ですがこちらまでご連絡頂ければ幸いです。
シェアする