はじめに
先日開催された「AtCoder Beginner Contest 158」のD問題でdequeを使用すると良い問題が出題されたのでPythonでの使い方についてまとめたいと思います。
D - String Formation
https://atcoder.jp/contests/abc158/tasks/abc158_d
dequeとは
Pythonのコンテナデータ型の１種。
データの追加を先頭、末尾両方に対してO(1)のコストで実施できる。
通常のlistだと先頭に追加する場合にO(n)のコストで実施できる。
末尾だけでなく先頭にもデータを追加するような場合に役立ちます。
メソッド紹介
末尾にデータを追加 append
Listと同じように「append」メソッドを使用します。
先頭にデータを追加 appendleft
「appendleft」メソッドを使用します。
Listでは「insert」メソッドを使用する。
サンプルコード1
from collections import deque
d = deque('a')
d.append('b')
d.appendleft('c')
print(d)
# -> deque(['c', 'a', 'b'])
print(''.join(d))
# -> cab
浅いコピー copy
dequeの浅いコピーを作成する。
浅いコピーについては以下を参照。
copy --- 浅いコピーおよび深いコピー操作
https://docs.python.org/ja/3/library/copy.html
サンプルコード2
from collections import deque
d1 = deque([1, 2, 3, 4, 5])
d2 = d1.copy()
print(d1)
# -> deque([1, 2, 3, 4, 5])
print(d2)
# -> deque([1, 2, 3, 4, 5])
d1.append(6)
print(d1)
# -> deque([1, 2, 3, 4, 5, 6])
print(d2)
# -> deque([1, 2, 3, 4, 5])
要素の数え上げ count
deque内の引数に等しい値の数を数える。
要素の位置 index
deque内の引数に等しい値の位置を返す。
見つからない場合は、ValueErrorを発生させる。
要素の取り出し pop popleft
pop:dequeの右側の要素を削除して返す。
popleft:dequeの左側の要素を削除して返す。
要素の削除 remove
deque内の引数に等しい最初の値を削除する。
見つからない場合は、ValueErrorを発生させる。
要素の反転 reverse
deque内の要素の並びを反転させる。
サンプルコード3
from collections import deque
d = deque([1, 2, 3, 4, 5])
d.insert(2, 5)
print(d)
# -> deque([1, 2, 5, 3, 4, 5])
print(d.count(5))
# -> 2
print(d.index(2))
# -> 1
print(d.index(5))
# -> 2
print(d.index(5, 4, 6))
# -> 5
print(d.pop())
# -> 5
print(d)
# -> deque([1, 2, 5, 3, 4])
print(d.popleft())
# -> 1
print(d)
# -> deque([2, 5, 3, 4])
d.remove(5)
print(d)
# -> deque([2, 3, 4])
d.reverse()
print(d)
# -> deque([4, 3, 2])
イテラブルな要素を追加 extend
インテラブルな要素を右側に追加する。
イテラブルな要素を左に追加 extendleft
インテラブルな要素を左側に追加する。
要素をズラす rotate
引数の値だけ要素を右に移動する。
末端を超える要素は先頭に移動する。
負の数を指定すると左に移動する。
サンプルコード4
from collections import deque
d = deque([1, 2, 3, 4, 5])
li = [6,7,8,9]
d.extend(li)
print(d)
# -> deque([1, 2, 3, 4, 5, 6, 7, 8, 9])
d.extendleft(li)
print(d)
# -> deque([9, 8, 7, 6, 1, 2, 3, 4, 5, 6, 7, 8, 9])
d.rotate(1)
print(d)
# -> deque([9, 9, 8, 7, 6, 1, 2, 3, 4, 5, 6, 7, 8])
d.rotate(-1)
print(d)
# -> deque([9, 8, 7, 6, 1, 2, 3, 4, 5, 6, 7, 8, 9])
d.clear()
print(d)
# -> deque([])
最大長の指定 maxlen
dequeの最大要素数を指定する。
最大要素数を超えて追加すると逆側の要素が削除される。
サンプルコード5
from collections import deque
li = [1, 2, 3, 4, 5]
d = deque(li, 3)
print(d)
# ->deque([3, 4, 5], maxlen=3)
d2 = deque([], 3)
for i in range(10):
d2.append(i)
print(d2)
# -> deque([7, 8, 9], maxlen=3)
Listと性能比較
（お試しくらいの気持ちで実施しています）
単純に偶数なら右、奇数なら左に値を追加する処理を1,000,000回実施して性能を比較しました。
Listは約147秒、dequeは約0.3秒でした。
from collections import deque
import time
start = time.time()
li = []
for i in range(1000000):
if i % 2 == 0:
li.append(i)
else:
li.insert(0, i)
elapsed_time = time.time() - start
print(elapsed_time)
# -> 147.49888038635254
start = time.time()
d = deque([])
for i in range(1000000):
if i % 2 == 0:
d.append(i)
else:
d.appendleft(i)
elapsed_time = time.time() - start
print(elapsed_time)
# -> 0.3092050552368164
感想
コンテストではdequeを知らなかったので、最大要素数の倍のListを作成して最初の要素を真ん中に追加して対応しました。
dequeを知っていればもっと楽に解けたと思うのでデータ構造もしっかり学びたいなと思いました。
計算量は理解していても、実際に処理時間を比較すると差が出るなと思いました。
参考
collections --- コンテナデータ型
https://docs.python.org/ja/3/library/collections.html#collections.deque
Python で「両端キュー」として使えるデータ型 collections.deque
https://kakakakakku.hatenablog.com/entry/2019/01/04/214907
【Python】処理にかかる時間を計測して表示
https://qiita.com/fantm21/items/3dc7fbf4e935311488bc