WebエンジニアのLoL日記

LoLをプレイしたりLJLの試合を見たりするのが好きなエンジニア。LoLのイベントやパッチノートなど気になった点を記事にしたり、LJLについの記事をかいたりしています。某社でWeb系のエンジニアとして働いているので、技術系の記事もたまに書きます。コンタクトを取りたい場合はtwitterまで。

PHPのPriorityQueueの実装についてとSplPriorityQueueの使い方

JavaC++だとPriorityQueueが標準ライブラリで用意されているイメージがありますが、PHPはあまりそういったイメージがありません。しかし、PHPでもちゃんとPriorityQueueが標準で用意されています。

SplPriorityQueue の使い方

PHPのPriorityQueueの実装がSplPriorityQueueです。その基本的な使い方は以下の通りです。

<?php

$queue = new SplPriorityQueue();

// insert メソッドで要素を挿入
// $queue->insert(<挿入するオブジェクト>, <そのオブジェクトのPriority>); 
$queue->insert('Hoge', 1);
$queue->insert('Fuga', 3);
$queue->insert('Piyo', 2);

// isEmpty() でqueueが空かどうかを判断
while(!$queue->isEmpty()) {
    // extractは先頭の要素を取り出しつつその要素をqueueから削除
    var_dump($queue->extract());
}

これの実行結果は以下のようになります。

string(4) "Fuga"
string(4) "Piyo"
string(4) "Hoge"

Queueの中から、Priorityが高い順に取り出されていることがわかります。

主なメソッドは以下の通りです。

  • insert() : Queueに要素そ挿入
  • isEmpty() : Queueが空ならtrue
  • extract() : Queueの先頭の要素を取り出しつつその要素をQueueから削除
  • top() : Queueの先頭の要素を取り出す。Queueからの削除は行わない
  • count() : Queueの中身の数を取得

発展 - 優先度が低い順に取り出したりする時は...?

SplPriorityQueueのデフォルトの実装では、優先度が高い順に要素を取り出すようになっていますが、優先度が低い順に取り出したかったり、優先度を複雑に設定したかったりする場合があると思います。

優先度が低い順に取り出したい

SplPriorityQueue を継承したクラスを作り、compare メソッドをオーバーロードすることで可能となります。

<?php

class MyPriorityQueue extends SplPriorityQueue {
    /** Queueの中身を昇順でソートするように変更 */
    public function compare($priority1, $priority2) {
        if($priority1 === $priority2) return 0;
        $priority1 < $priority2 ? -1 : 1;
    }
}

$queue = new MyPriorityQueue();

$queue->insert('Hoge', 1);
$queue->insert('Fuga', 3);
$queue->insert('Piyo', 2);

while(!$queue->isEmpty()) {
    var_dump($queue->extract());
}

こうすることで結果は以下のようになり、昇順で取り出されるようになります。

string(4) "Hoge"
string(4) "Piyo"
string(4) "Fuga"

パーフェクトPHP (PERFECT SERIES 3)

パーフェクトPHP (PERFECT SERIES 3)