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

## はじめに
先日開催された「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
```python
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
```python
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
```python
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
```python
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
```python
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秒でした。

```python
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