Pythonのキューは3種類ある

Pythonのキュー

Pythonにはキューを実現する方法が3種類あります。備忘のために整理します。

• list
• collections.deque
• queue.Queue

list

listで実現する場合は、append()とpop(0)を利用します。

def test_queue_list():
    q = []
    q.append(1)
    q.append(2)
    q.append(3)
    v = q.pop(0)
    assert v == 1

ただし、Pythonのlistは内部的にはCの配列で実装されているため、この方法はおそいです（ちょっと正確な表現ではないかも）。append()は $O(1)$ で実現できますが、pop(0)は $O(N)$ 。ドキュメンテーションの案内はこんな感じ。

リストをキュー (queue) として使うことも可能です。
（中略）
追加（append）や取り出し（pop）をリストの末尾に対して行うと速いのですが、挿入（insert）や取り出し（pop）をリストの先頭に対して行うと遅くなってしまいます（他の要素をひとつずつずらす必要があるからです）。

collections.deque

dequeはdouble-ended queueの略で、デックと読みます。append()とpopleft()でキューを実現します。両端が終端のため、キューとしてもスタックとしても使えて便利、高速。ただし、スレッドセーフではありません。

from collections import deque

def test_queue_deque():
    q = deque()
    q.append(1)
    q.append(2)
    q.append(3)
    v = q.popleft()
    assert v == 1

queue.Queue

同期キュークラス。スレッドセーフな実装です。put()とget()を利用します。スレッドセーフを実現するためにややオーバーヘッドがあるため、dequeよりは遅い。

import queue

def test_queue_Queue():
    q = queue.Queue()
    q.put(1)
    q.put(2)
    q.put(3)
    v = q.get()
    assert v == 1

おわりに

listが汎用的で便利ですが、ちゃんとメリット・デメリットを把握して使い分けたいですね。にしても、インターフェイスは、enqueue()、dequeue()だと分かりやすいんだけどなぁ。