Python の queue 関連のライブラリを確認する

Python の標準モジュールで用意されている queue 関連のライブラリについて確認します。

環境

• Python 3.9.13

queue 関連のライブラリ

以下があります。

種類	queue モジュール	その他モジュール
キュー	queue.Queue	collections.deque
スタック	queue.LifoQueue	collections.deque
優先度付きキュー	queue.PriorityQueue	heapq

queue.Queue/queue.LifoQueue vs collections.deque

queue.Queue および queue.LifoQuoue と collections.deque の違いは、ずばり stackoverflow で教えてくれました。

Queue.Queue and collections.deque serve different purposes. Queue.Queue is intended for allowing different threads to communicate using queued messages/data, whereas collections.deque is simply intended as a datastructure. That's why Queue.Queue has methods like put_nowait(), get_nowait(), and join(), whereas collections.deque doesn't.

Queue.Queue vs. collections.deque

そもそも公式ドキュメントのタイトルに A synchronized queue class とありますからね。queue.Queue のソースを見ると、コンストラクタのところで collections.deque を使ってキューを作っています。

queue --- 同期キュークラス

queue.PriorityQueue vs heapq

queue.PriorityQueue と heapq の違いも同じものです。

Queue.PriorityQueue is a thread-safe class, while the heapq module makes no thread-safety guarantees.

The heapq module offers no locking, and operates on standard list objects, which are not meant to be thread-safe.

What's the difference between heapq and PriorityQueue in python?

collections.deque の使い方

collections.deque の使い方を簡単に確認します。

collections.deque()

スタック

from collections import deque

stack = deque([4, 5, 6])
print(stack)
# deque([4, 5, 6])

stack.append(7)
print(stack)
# deque([4, 5, 6, 7])

print(stack.pop())
# 7
print(stack)
# deque([4, 5, 6])

キュー

queue = deque([4, 5, 6])
print(queue)
# deque([4, 5, 6])

queue.append(7)
print(queue)
# deque([4, 5, 6, 7])

print(queue.popleft())
# 4
print(queue)
# deque([5, 6, 7])

循環リスト

collections.deque.rotate() メソッドを使うことで、循環リストにもなります。

from collections import deque

circular_queue = deque([4, 5, 6])
print(circular_queue)
# deque([4, 5, 6])

circular_queue.rotate(1)
print(circular_queue)
# deque([6, 4, 5])

circular_queue.rotate(-1)
print(circular_queue)
# deque([4, 5, 6])

循環バッファ

maxlen 引数を指定すれば、循環バッファとして利用できると紹介されています。

efficient circular buffer?

from collections import deque

circular_buffer = deque([4, 5, 6], maxlen=3)
print(circular_buffer)
# deque([4, 5, 6], maxlen=3)

circular_buffer.append(7)
print(circular_buffer)
# deque([5, 6, 7], maxlen=3)

print(circular_buffer.popleft())
# 5
print(circular_buffer)
# deque([6, 7], maxlen=3)

heapq の使い方

heapq の使い方を確認します。

heapq --- ヒープキューアルゴリズム

heapq は、親ノードの値がすべての子ノードの値に対して「小なり」となるバイナリ・ヒープ・ツリーを作ってくれます。つまり、ルートのノードが最小となるツリーとなります。

import heapq
import random

target_list = [random.randint(1, 99) for _ in range(10)]
print(target_list)
# [75, 66, 21, 74, 85, 1, 94, 66, 44, 94]

# heapify() にリストを渡すと、インプレースでヒープしてくれます
heap_queue = heapq.heapify(target_list)
print(target_list)
# [1, 44, 21, 66, 85, 75, 94, 66, 74, 94]

# heappop() で最小ノードを返してくれます
print(heapq.heappop(target_list))
# 1
print(target_list)
# [21, 44, 75, 66, 85, 94, 94, 66, 74]

# heappush() でノードを追加しても、ヒープを維持してくれます
heapq.heappush(target_list, 50)
print(target_list)
# [21, 44, 75, 66, 50, 94, 94, 66, 74, 85]

ヒープソートの実装例

公式ドキュメントに、ヒープソートの実装例が記載されていました。

import heapq

def heapsort(target_list: list) -> list:
    h = []
    for value in target_list:
        heapq.heappush(h, value)
    return [heapq.heappop(h) for _ in range(len(h))]

print(heapsort([1, 3, 5, 7, 9, 2, 4, 6, 8, 0]))
# [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

基本的な例

ノードに複数の値を持ちたい場合

リストにタプルを入れて渡してあげることで、「優先度の値」と「優先度とペアとなる情報の値」を管理できます。

ヒープの要素はタプルに出来ます。これは、追跡される主レコードとは別に (タスクの優先度のような) 比較値を指定するときに便利です

import heapq

target_list = [
    (9, "nine"),
    (1, "one"),
    (8, "eight"),
    (6, "six"),
    (3, "three"),
    (0, "zero"),
    (5, "five"),
    (2, "two"),
    (4, "four"),
    (7, "seven"),
]

heapq.heapify(target_list)
print(target_list)
# [(0, 'zero'), (1, 'one'), (5, 'five'), (2, 'two'), (3, 'three'), (8, 'eight'), (9, 'nine'), (6, 'six'), (4, 'four'), (7, 'seven')]

print(heapq.heappop(target_list))
# (0, 'zero')

heapq.heappush(target_list, (10, "ten"))
print(target_list)
# [(1, 'one'), (2, 'two'), (5, 'five'), (4, 'four'), (3, 'three'), (8, 'eight'), (9, 'nine'), (6, 'six'), (7, 'seven'), (10, 'ten')]