PythonのListよりも早い？Listとdequeのパフォーマンスを比較してみる

データアナリティクス事業本部＠札幌の佐藤です。

Pythonでパフォーマンスと考えると、まずはdequeを思い浮かべると思います。
でもListと比べ早いくらいしか考えたことがなかったので、実際にどのくらい早いものなのか調べてみたいと思います。

そもそもdequeとは

deque（デック）は両端キューとも呼ばれます。
またdequeはデータ構造のひとつなので、Python固有ものではありません。

Pythonのリファレンス上では

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

list オブジェクトでも同様の操作を実現できますが、これは高速な固定長の操作に特化されており、内部のデータ表現形式のサイズと位置を両方変えるような pop(0) や insert(0, v) などの操作ではメモリ移動のために O(n) のコストを必要とします。
ref:deque オブジェクト

「スタックとキューを一般化したもの」という記載の通り、配列の両端に対するアクセスが早いという特徴があります。
追加・削除での時間計算量はO(1)なので、早いらしいというのが分かりますね。

基本的な使い方はListと同様です。

# Listの場合
>> list_array = []
>> list_array.append("姫石らき")
>> list_array.append("友希あいね")
>> list_array.pop()
'友希あいね'

# dequeの場合
>> from collections import deque
>> deque_array = deque()
>> deque_array.append("姫石らき")
>> deque_array.append("友希あいね")
>> deque_array.pop()
'友希あいね'

ちょっと違うのは先頭の要素に対して追加・削除があるという点になります。
appendleft() で先頭の要素に対し追加します。

>> from collections import deque
>> deque_array = deque()
>> deque_array.append("姫石らき")
>> deque_array.append("友希あいね")
>> deque_array.appendleft("湊みお")
>> deque_array
deque(['湊みお', '姫石らき', '友希あいね'])

また、popleft() で先頭の要素を返すこともできます。

>> from collections import deque
>> deque_array = deque()
>> deque_array.append("姫石らき")
>> deque_array.append("友希あいね")
>> deque_array.popleft()
'姫石らき'

Listにキャストすることもできます。

>> from collections import deque
>> deque_array = deque()
>> deque_array.append("姫石らき")
>> list_array = list(deque_array)
>> print(list_array)
['姫石らき']

List vs deque（先頭要素）

まずは、先頭への走査について調べたいと思います。
100,000の要素を持つデータを1000回ループして先頭の要素を取り出す処理を繰り返してみます。

# Listの場合
>> import time
>> start = time.time()
>> list_array = list(range(100000))
>> for i in range(1000):
>>     list_array.pop(0)
>> elapsed_time = time.time() - start
>> print ("elapsed_time:{0}".format(elapsed_time) + "[sec]")

1回目　elapsed_time:0.05488991737365723[sec]
2回目　elapsed_time:0.04288434982299805[sec]
2回目　elapsed_time:0.054895877838134766[sec]

10回実行して平均0.047844052secでした。
Listの pop() で0番目を指定した場合、末端から先頭まで走査するので遅いのは当然です。

続いてdeque

# dequeの場合
>> from collections import deque
>> import time
>> start = time.time()
>> deque_array = deque(range(100000))
>> for i in range(1000):
>>     deque_array.popleft()
>> elapsed_time = time.time() - start
>> print ("elapsed_time:{0}".format(elapsed_time) + "[sec]")

1回目　elapsed_time:0.008365631103515625[sec]
2回目　elapsed_time:0.007332801818847656[sec]
3回目　elapsed_time:0.008947134017944336[sec]

10回実行して平均0.00744257secでした。

この結果から、配列の先頭に対する速度はdequeのほうが早いということが分かりました。
何となく想像通りって感じですね。

では配列の中間の要素に対してはどうでしょうか。

List vs deque（中間の要素）

今回は要素数100,000の配列を1,000,000回ループします。
ループ中で20番目の要素を削除、そのあと20番目の要素を追加します。

配列の末端に対する走査は確かにdequeはO(1)なのでdequeが早いです、ただ配列の中間となると話が違います。
削除の平均計算量はO(n)、Listもdequeも同じ土俵に立っているといえるはずです。

今回は memory_profiler のライブラリを使用してメモリの使用率の観点からも見てみます。
※処理時間がちょっと大きいのはこのライブラリを使用しているからです。
※検証自体はjupyter notebook上で行っています。

# Listの場合
>> %load_ext memory_profiler
>> from memory_profiler import profile
>> import time
>> 
>> start = time.time()
>> 
>> list_array = list(range(10000))
>> for i in range(1000000):
>>     list_array.remove(20)
>>     list_array.insert(20, 20)
>> %memit
>> 
>> elapsed_time = time.time() - start
>> print ("elapsed_time:{0}".format(elapsed_time) + "[sec]")

〇処理時間
1回目　elapsed_time:25.979241132736206[sec]
2回目　elapsed_time:26.479660749435425[sec]
3回目　elapsed_time:26.32246232032776[sec]

〇メモリ使用量
1回目　peak memory: 60.84 MiB, increment: 0.02 MiB
2回目　peak memory: 61.12 MiB, increment: 0.09 MiB
3回目　peak memory: 60.88 MiB, increment: 0.05 MiB

# dequeの場合
>> %load_ext memory_profiler
>> from memory_profiler import profile
>> from collections import deque
>> import time
>> 
>> start = time.time()
>> 
>> deque_array = deque(range(10000))
>> for i in range(1000000):
>>     deque_array.remove(20)
>>     deque_array.insert(20, 20)
>> %memit
>> 
>> elapsed_time = time.time() - start
>> print ("elapsed_time:{0}".format(elapsed_time) + "[sec]")

〇処理時間
1回目　elapsed_time:21.0693142414093[sec]
2回目　elapsed_time:21.471088647842407[sec]
3回目　elapsed_time:21.121334075927734[sec]

〇メモリ使用量
1回目　peak memory: 60.82 MiB, increment: 0.02 MiB
2回目　peak memory: 60.92 MiB, increment: 0.06 MiB
3回目　peak memory: 60.91 MiB, increment: 0.02 MiB

この観点でもdequeのほうが早いですね。
メモリ使用量の観点ではあまり変わりませんでした。

追加検証：List vs deque（末端の要素）

追加検証として、 append() で末端の要素を100,000回追加してみて処理時間が大体同じかどうかを検証します。

# Listの場合
>> import time
>> start = time.time()
>> list_array = list(range(1000))
>> for i in range(100000):
>>     list_array.append(0)
>> 
>> elapsed_time = time.time() - start
>> print ("elapsed_time:{0}".format(elapsed_time) + "[sec]")

1回目　elapsed_time:0.017949581146240234[sec]
2回目　elapsed_time:0.019548416137695312[sec]
3回目　elapsed_time:0.019548416137695312[sec]

10回実行して平均0.019243765secでした。

メモリ使用量はこのような感じです。
1回目　peak memory: 62.02 MiB, increment: 0.04 MiB
2回目　peak memory: 61.51 MiB, increment: 0.21 MiB
3回目　peak memory: 61.83 MiB, increment: 0.26 MiB

# dequeの場合
>> from collections import deque
>> import time
>> start = time.time()
>> deque_array = deque(range(1000))
>> for i in range(100000):
>>     deque_array.append(0)
>> 
>> elapsed_time = time.time() - start
>> print ("elapsed_time:{0}".format(elapsed_time) + "[sec]")

1回目　elapsed_time:0.023968935012817383[sec]
1回目　elapsed_time:0.023933887481689453[sec]
1回目　elapsed_time:0.01991128921508789[sec]

10回実行して平均0.020917204secでした。

メモリ使用量はこのような感じです。
1回目　peak memory: 61.68 MiB, increment: 0.40 MiB
2回目　peak memory: 61.60 MiB, increment: 0.38 MiB
3回目　peak memory: 61.50 MiB, increment: 0.37 MiB

末端の要素を追加する場合、若干ですがListのほうが早いようです。
メモリの使用量はあまり変わらないように見えますね。

じゃあdeque使えばいいじゃん

dequeのほうが早いということは分かりましたが、必ずしもdequeを使えばいいというわけでもないと思います。
というのもdeque側には sort() がありません（ソート済みが前提）ので、もし要素をソートする必要があればListを使用したほうが良いですね。

最後に

Listとdequeは似ていますが、パフォーマンスはdequeのほうがよさそうです。
ただ、一般的な認知度はListだと思いますので、そのあたりも含めてどれを使うべきか考慮していきたいですね。

「アイカツ！」シリーズが好きなので、データは関連するキャラクターに寄せました。
最新シリーズ『アイカツオンパレード！』はテレビ東京系 毎週土曜日 午前10時30分～/BSテレ東毎週月曜日夕方5時～から好評放送中です！

参考

python: deque vs list performance comparison