search
LoginSignup
17

More than 1 year has passed since last update.

posted at

Pythonのデータが「deque」の使い方

はじめに

先日開催された「AtCoder Beginner Contest 158」のD問題でdequeを使用すると良い問題が出題されたのでPythonでの使い方についてまとめたいと思います。

D - String Formation
https://atcoder.jp/contests/abc158/tasks/abc158_d

dequeとは

Pythonのコンテナデータ型の1種。
データの追加を先頭、末尾両方に対して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

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
What you can do with signing up
17