queue.Queueよりcollections.deque方が速いbfs書けますよというお話[AtCoder]

結論

タイトルの通りです

注意

AtCoderのコードテストで動かして実行時間などをテストしてます。また、間違ってる点があったらコメント等で指摘くださると勉強になります。

初めに

まず、キューとは何でしょうか？
有名なデータ構造として、キュー、そしてスタックというものがあります。
細かい点に関しては検索してもらうとして、キューは先に入れたデータを先に取り出す、先入れ先出しのFIFO(First In First Out)でデータを格納し、スタックは先に入れたデータを後に取り出す、先入れ後出しのLIFO(Last In First Out)でデータを格納するデータ構造となっています。
僕はキューは店の行列、スタックは山積みの本のイメージで覚えています。
このスタックキューは、競プロでは幅優先探索(BFS)や深さ優先探索(DFS)でおなじみです。

さて、Python ではスタックキューとして、queue.Queue(以下queue)とcollections.deque(以下dequqe)を使うことができます。
僕はqueueの方をよく使っていたのですがdequeの方が速かったので記事にしてみました。

実験

早速実行速度を確かめてみましょう。

from queue import Queue

q=Queue()
for i in range(10**6):
  q.put(i)

from collections import deque

q=deque()
for i in range(10**6):
  q.append(i)

この両方をAtCoderのコードテスト上で実行すると

	実行時間(ms)	メモリ(KB)
queue	2314	46284
deque	160	45724

単純な末尾挿入でも実行時間にだいぶ差が出てしまうことがわかります。競技プログラミングにおいてはqueueは基本的に避けた方がよさそうです。
(queueが全く使えないかというとそうではなくて、マルチスレッドではqueueに分があるようです。詳しくは知らない)

という事で検証終わり！w

......なのですが、そもそもなぜdequeは速いのでしょうか...？

dequeとリスト

Pythonにはリストというものがあります。いわゆる配列みたいなやつです。(厳密には配列ではない)

このリスト、末尾に挿入するのは速いのですが、実は末尾以外に挿入しようとすると激遅です。末尾に挿入と先頭に挿入で速度を比べてみましょう。

ls=[]
for i in range(10**6):
  ls.append(i)

ls=[]
for i in range(10**6):
  ls.insert(0,i)

	実行時間(ms)	メモリ(KB)
append	140	45080
insert	10504	12528

挿入だけでこんなに時間を食っているとお話になりませんね。

プログラミングをやっていると当然末尾以外に挿入したいときは出てきます。その時はどうすればいいのでしょうか
感のいい人なら気づいているかもしれませんが、そういうときに用いるのがdequeです。

定義見ながら書き下していくのもアレ(面倒)なのでドキュメントを引用します。

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

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

collections.deque --- コンテナデータ型 — Python 3.7.3 ドキュメント

つまるところ、先頭に挿入するのが速いという事です。

from collections import deque

q=deque()
for i in range(10**6):
  q.appendleft(i)

	実行時間(ms)	メモリ(KB)
appendleft	145	45740

appendleft()は先頭に要素を追加します。リストと比べてかなり高速にできるのがわかります。そういったわけで、スタックとキューを実装する際にもdequeを使用すると実行時間が短くて済むわけですね。
dequeすごい！

じゃあ、全部dequeでよくね？
といった気持ちがわいてきますがdequeでは、末尾と先頭以外に操作を加えようとするとむしろ遅くなるようです。残念。