Python のプライオリティ キュー コンパレータ

Pythonのプライオリティキューは、優先度に従って項目を取り出します。適切な順序は優先度の表し方によって異なります。Pythonのヒープ操作は既定で最小の項目を先に返しますが、カスタムキーや比較可能なラッパーを使えば、別の順序も表現できます。このガイドでは、queue.PriorityQueue、heapq、ソート済みリスト、heapdictを比較し、優先度を変更できる場合についても説明します。

Pythonのプライオリティキューと順序付け

プライオリティキューは、優先度付きの項目を格納し、順序付けの規則に従って次の項目を取り出すデータ構造です。大きな数値が自動的に「より重要」だと判断するわけではありません。Pythonの標準的なヒープ操作では、最小の項目が先に取り出されます。大きな数値の優先度を先に処理するには、その値の負数を格納するか、比較動作を定義したラッパークラスを使います。

複数の項目の優先度が同じ場合は、同順位を判定するために連番を加えます。これにより順序が予測可能になり、順序比較に対応していない可能性のあるペイロードをPythonが比較するのを防げます。項目を挿入する前に表現方法を決めてください。通常のヒープに格納済みの優先度を変更しても、ヒープの不変条件が自動的に回復するわけではありません。

queue.PriorityQueueに比較関数の引数がない理由

queue.PriorityQueueは、項目の順序を使うスレッドセーフなキューです。コンストラクターに比較関数の引数はありませんが、項目自体を比較可能にできます。よく使われる方法は、キューにタプルを入れることです。タプルの最初の要素で優先度を決め、2番目の要素で同順位を判定します。たとえば、put((priority, sequence, task))の後にget()を呼ぶと、最小のタプルが先に返されます。数値が大きい優先度を先に返すには、優先度に負数を使います。

同じ優先度のタスクがある場合、連番が重要になります。連番がなければタプルの比較はタスクの要素まで進み、型の異なるタスク同士は比較できないことがあります。スレッドを使わないコードでは、heapqを使うと、キューの同期機能なしで同様の基本的なヒープ順序を利用できます。どちらも、独立した比較コールバックは受け取りません。

heapqで独自の順序を実装する

独自の順序を実現するには、その規則をPythonで比較できるフィールドに置き換えます。この例では、スコアの大きい項目を先にするために負のスコアを使い、同順位では挿入順を保つために増加する連番を使います。各要素は(negative score, sequence, task)なので、優先度が同じ項目同士の判定にタスクの値は使われません。

次の例を実行してください。コード内のタスク名と表示されるラベル（write、review、test）は英語のままです。

import heapq
from itertools import count

sequence = count()
queue = []

for score, task in [(7, "write"), (9, "review"), (9, "test")]:
    heapq.heappush(queue, (-score, next(sequence), task))

while queue:
    negative_score, _, task = heapq.heappop(queue)
    print(task, -negative_score)

review 9
test 9
write 7

この方法ではキーに基づく順序を表現できますが、汎用の比較コールバックを提供するものではありません。より複雑な規則が必要なら、比較メソッドで希望する順序を表す小さなクラスを作るか、各項目を比較可能なキーのタプルに正規化します。順序を決定的に保つため、同順位の扱いを明示してください。

小規模なプライオリティキューにリストを使う

キューが小さい場合や項目をまとめて追加する場合は、リストを使うと簡単です。(priority, task)のペアを格納してソートし、次の項目にあたる側から取り出します。優先度を昇順にし、最小値を先に取り出すには、降順にソートして末尾からpop()します。項目が順次届く場合は、挿入のたびに再ソートします。リスト全体のソートを繰り返すと、リストが大きくなるほど処理量が増えるため、追加や取り出しが頻繁なら通常はヒープのほうが適しています。

依存パッケージを使わないリストの例を示します。優先度は昇順なので、優先度1のタスクが最初に取り出されます。コード内のタスク名と表示されるラベル（report、email、meeting、review）は英語のままです。

items = [(4, "report"), (1, "email"), (3, "meeting"), (2, "review")]
items.sort(reverse=True)

while items:
    print(items.pop())

(1, 'email')
(2, 'review')
(3, 'meeting')
(4, 'report')

ペアの最初の要素で順序が決まります。優先度が同じなら、次にタスクの文字列が比較されます。挿入順を保つ必要がある場合や、ペイロードを比較できない場合は、連番を追加してください。リスト方式は動作を確認しやすい一方、内容が頻繁に変わる大きなキューでは、全体の再ソートを繰り返す方法は非効率です。

優先度を変更できる場合はheapdictを使う

キューに入っている間に優先度を変更する必要があるタスクには、heapdictを使います。サードパーティーパッケージはpip install heapdictでインストールします。heapdict.heapdictのインスタンスはキーと優先度を対応付けます。既存のキーに新しい値を代入すると、ヒープを維持しながらそのキーの優先度が更新されます。popitem()は、最小の優先度を持つキーとその優先度を取り出します。大きな数値を先にするには、数値の優先度を負数にします。

このパッケージを使うときは、tasks = heapdict.heapdict()のように作成し、tasks["write report"] = 3のように値を代入します。後からtasks["write report"] = 0を代入すると、そのタスクの優先度が更新されます。tasks.popitem()を呼ぶと、最小の優先度を持つタスクとその優先度が返されます。この例はサードパーティーパッケージのインストールを前提としており、単独で実行できるものではありません。

マッピングではキーごとに優先度を1つだけ保持するため、キューに入れるタスクにはそれぞれ異なるキーを使ってください。popitem()で取り出されたタスクは、キューから外れています。これはheapqの場合と異なり、そちらでは既存の項目の優先度を変える際、通常は古い項目を自分で管理するか、ヒープを作り直す必要があります。

方法を選ぶ

複数のスレッドで同期されたキューが必要で、項目がPython標準の比較順序に対応している場合は、queue.PriorityQueueを選びます。タプルキーや比較可能なラッパーで順序を制御できますが、比較関数の引数はありません。通常の単一スレッドのコードで、小さく高速なヒープを使いたい場合は、heapqを選びます。キーと同順位判定を使えば、独自の順序も表現できます。頻繁な更新よりも簡潔さを重視する小さなコレクションには、ソート済みリストが適しています。項目をキューに残したままキーごとに優先度を変更する必要がある場合は、heapdictを選びます。

どの方法でも、小さい値と大きい値のどちらを先に処理するかを決め、その規則を一貫して表現し、同順位の扱いも定めてください。項目の追加と取り出しが頻繁な大規模処理では、変更のたびにリスト全体をソートするより、一般にヒープのほうが効率的です。優先度を変更する場合は、マッピングに対応したヒープを使うか、heapqで実装するなら古い項目を明示的に管理してください。