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()だと分かりやすいんだけどなぁ。
