pythonにはデフォルトでキューを実装するのに便利な機能が実装されている。競プロなんかでも結構頻出で、自前で実装するよりも全然早いのでよく使ってる。
簡単に使い方のメモ的に書いていく。FIFO、LIFO、プライオリティキューなんかは特に頻出。
似たような使い勝手のcollections --- コンテナデータ型 — Python 3.8.4rc1 ドキュメント なんかもあるけどこっちはマルチスレッドでの動作向けにスレッドセーフな実装となっている。
FIFO Queue
一番馴染みのあるFIFOキュー
メインスレッドからスレッドを生成してメインスレッドからキューにデータを与えてワーカースレッドで処理をするサンプル
import threading, queue q = queue.Queue() def worker(): while True: item = q.get() print(f'Working on {item}') print(f'Finished {item}') q.task_done() threading.Thread(target=worker, daemon=True).start() for item in range(5): q.put(item) print('All task requests sent\n', end='') q.join() print('All work completed')
実行結果は当然与えたデータをFIFOで処理するため以下のような結果となる
Working on 0 Finished 0 Working on 1 Finished 1 Working on 2 Finished 2 Working on 3 Finished 3 Working on 4 Finished 4 All task requests sent All work completed
LifoQueue
こっちは前述したFIFOではなくLIFOでデータを処理していく。スタック的な動作をする。
先ほどのプログラムのQueueのコンストラクタをLifoQueueへと変えるだけで実装することが可能。
import threading, queue
q = queue.LifoQueue()
def worker():
while True:
item = q.get()
print(f'Working on {item}')
print(f'Finished {item}')
q.task_done()
for item in range(5):
q.put(item)
threading.Thread(target=worker, daemon=True).start()
print('All task requests sent\n', end='')
q.join()
print('All work completed')
実行結果は先ほどはデータを1から順に入れているが今度は最後に入れた値からワーカースレッドで処理されていくのがわかる。
Working on 4 Finished 4 Working on 3 Finished 3 Working on 2 Finished 2 Working on 1 Finished 1 Working on 0 Finished 0 All task requests sent All work completed
優先度付きキュー
データの要素の値に基づいて取り出す順番を決めることができるキュー。似たような機能にheapqがある。競プロだと基本heapqしか使わない。マルチスレッドでの実装ならこっちを使う。
import threading, queue q = queue.PriorityQueue() def worker(): while True: item = q.get() print(f'Working on {item}') print(f'Finished {item}') q.task_done() q.put(4) q.put(3) q.put(6) threading.Thread(target=worker, daemon=True).start() print('All task requests sent\n', end='') q.join() print('All work completed')
実行結果は以下の通り与えたデータの最初値からワーカースレッドが処理している様子がみられる。
Working on 3 Finished 3 Working on 4 Finished 4 Working on 6 Finished 6 All task requests sent All work completed
heapqとPriorityQueueはベンチマークについても結構話題になっていて最大でも2倍程度の速度差が出るらしくマルチスレッド環境でない場合は基本heapqで良さそう。
自前で実装していライブラリとして持っておいてるのも参考になる。
