queueの実行速度について

はい電電です．一ヶ月ぶりにブログ書きますね．最近は部屋が暑すぎたり，将来の不安から夜に起きたりしてしまってよくないです．ちょっと暑すぎるので，簡易自作冷風機でも作ろうかなと考えています．まあ昨日扇風機をポチったので冷風機を作ったらまた書くと思います．

今回はqueueの実行速度についてちょっと気になったのでしらべました．

さて今回は先日行われたAtCoder ABC132の復習をしていて，E問題で深さ優先を使ったんですが，TLEを連発しました．

終わってみて解法をみたり，他の方のコードをみてみても特に違うことはなかったのでちょっとコードを変えてみたりしたんですが，TLEを連発しました（おい）．

投げすぎ

さすがにこんだけ投げて違うということは大きな間違いをしているんだろうなと思って，何が違うのかなと精査してみたところ，queueのライブラリを僕は

import queue
q = Queue.queue

を使っていたんですが，
他の方は

from collections import deque
q = deque()

を使っていました．で実際にdeque()を使ってみたら，テスト通ったのでこっちの方がはやいみたいです．
勝手にqueueはそこそこ早いものだと思ってたんですが，そうでもないみたいだったので調べてみました．

ということで簡単なテストコードを書いてみました．

# encoding:utf-8
import queue
from collections import deque
import time

que = queue.Queue()
dque = deque()

do_time = []
do_time.append(time.time()) # 計測

for i in range(10**6): # que
    que.put(i)

do_time.append(time.time())

while que.empty() == False:
    que.get()

do_time.append(time.time())

for i in range(10**6): # deque
    dque.append(i)

do_time.append(time.time())

while dque:
    dque.popleft()

do_time.append(time.time())


for i in range(len(do_time)-1):
    if i == 0 or i == 1:
        print("queue:",end = "")
    else:
        print("deque:",end = "")
    print(do_time[i+1] - do_time[i])

これの実行結果が以下のようになります．

queue:2.5287086963653564
queue:3.284255027770996
deque:0.13587212562561035
deque:0.10213994979858398

ということでqueueよりもdequeの方が圧倒的にはやいみたいですね．公式ドキュメント読んでみるとdequeはスタックとキューを一般化したものであり，最初と最後どちらの方向からもおよそO(1)でアクセス可能なようです．しかしこうなるとqueueの方がどうして残っているのかわからないです．もし知っている方がいれば教えて欲しいです．

さて今回はとてもみじかいですが，queueの実行時間についてでした．できればqueueにはdequeをつかった方が良さそうです．

ほなまたな〜