SplPriorityQueueで優先度付きキューを実装する

Bynori

SplPriorityQueueは、値と優先度をペアで登録すると優先度の高い順に取り出せるキューを提供するSPLのクラスです。内部はmaxヒープで、自前でソートや優先度管理を書く手間を省けます。

タスクの実行順を制御したり、イベントリスナーを優先度順に並べたりする場面で、配列をusortでソートし続けるのは正直しんどいです。挿入のたびに全体を並べ直すのは無駄が多いですし、コードも煩雑になりがちです。そういうときにSplPriorityQueueを使うと、挿入と取り出しだけで優先度順が保たれるので楽になります。

SplPriorityQueueはどう使う?

使い方はシンプルで、insert()で値と優先度を渡し、extract()で優先度の高いものから順に取り出します。優先度は数値でも文字列でも比較可能なものならなんでも構いません。

$queue = new SplPriorityQueue();
$queue->insert('メール送信', 1);
$queue->insert('決済処理', 10);
$queue->insert('ログ出力', 3);

while (!$queue->isEmpty()) {
    echo $queue->extract(), PHP_EOL;
}
// 決済処理
// ログ出力
// メール送信

insert()の第2引数が優先度で、数値が大きいほど先に出てきます。並び替えの実装を自分で書かなくていいので、優先度付きのタスクキューやジョブスケジューラの土台としてそのまま使えます。

foreachでも回せるが中身は消える

SplPriorityQueueはIteratorを実装しているので、foreachでそのまま回せます。ただしここに大きな落とし穴があります。foreachでの反復は内部的にextract()相当の処理で進むため、一度回すとキューの中身がなくなります。

$queue = new SplPriorityQueue();
$queue->insert('A', 1);
$queue->insert('B', 2);

foreach ($queue as $item) {
    echo $item, PHP_EOL;
}

var_dump($queue->isEmpty()); // bool(true)

「一覧をちょっと確認してから本処理で使う」みたいな書き方をすると、2回目のforeachで何も出てこず、なぜだとハマります。中身を保持したまま参照したいなら、事前にcloneしておくのが安全です。

値だけでなく優先度も一緒に取り出したいとき

デフォルトではextract()やforeachの値には登録した値だけが返り、優先度は見えなくなります。優先度も一緒に欲しい場合はsetExtractFlags()で取り出しモードを切り替えます。

$queue = new SplPriorityQueue();
$queue->setExtractFlags(SplPriorityQueue::EXTR_BOTH);
$queue->insert('決済処理', 10);
$queue->insert('ログ出力', 3);

foreach ($queue as $item) {
    echo $item['data'], ' : ', $item['priority'], PHP_EOL;
}
// 決済処理 : 10
// ログ出力 : 3

EXTR_DATAが値のみ(デフォルト)、EXTR_PRIORITYが優先度のみ、EXTR_BOTHが[‘data’ => …, ‘priority’ => …]の配列です。ログに優先度も残したいときなどはEXTR_BOTHにしておくと後で困りません。

同じ優先度のものはどの順で出る?

もうひとつ実務で刺さりやすいのが、同じ優先度の要素同士の順序です。公式マニュアルには「同じ優先度を持つ要素の順序は未定義」とはっきり書かれています。挿入順で出てくることを期待したコードを書くと、PHPのバージョンや内部実装の変化で結果が変わりうるということです。

挿入順を保証したい場合は、優先度に「メインの優先度」と「挿入連番」を組み合わせた配列やタプルを使い、compare()メソッドをオーバーライドして比較ロジックを自分で定義するのが確実です。SplPriorityQueueはcompare()を上書きできるように設計されているので、標準の比較で困ったらここに手を入れます。

class StablePriorityQueue extends SplPriorityQueue
{
    public function compare($priority1, $priority2): int
    {
        // priorityは [優先度, 挿入連番] のペアを想定
        // 優先度が同じなら連番が小さい(先に入れた)方を優先
        if ($priority1[0] === $priority2[0]) {
            return $priority2[1] <=> $priority1[1];
        }
        return $priority1[0] <=> $priority2[0];
    }
}

まとめ

SplPriorityQueueは、優先度順の取り出しをヒープ構造に任せられる便利なクラスですが、foreachで回すと中身が消える破壊的イテレーションであることと、同一優先度の順序は保証されないことの2点は覚えておく必要があります。挿入順を保証したいケースでは、compare()を自分で書いて優先度に連番を織り込むのが実務では一番安全なやり方だと思います。

よくある質問

Q. SplPriorityQueueとSplQueueの違いは?
A. SplQueueは先入れ先出し(FIFO)の単純なキューで、SplPriorityQueueは優先度をキーにして常に優先度が高いものから取り出せるキューです。用途が異なるので、単純な順番待ちならSplQueue、優先度で処理順を変えたいならSplPriorityQueueを選びます。

Q. 優先度に同じ値を使っても壊れませんか?
A. 壊れませんが、取り出し順序が保証されないだけです。挿入順を維持したいなら、優先度に挿入連番を含めてcompare()で明示的に順序を決める必要があります。

Q. cloneしてから回せば元のキューは消えませんか?
A. はい、SplPriorityQueueはclone可能で、cloneしたインスタンスに対してforeachを回せば元のキューの中身は保持されます。一覧確認と本処理の両方で使いたいときに有効です。

類似投稿

コメントを残す

メールアドレスが公開されることはありません。 ※ が付いている欄は必須項目です