きっかけ

先日YouTubeで、PHPカンファレンス福岡での、きんじょうひできさんの「SPLから始める「データ構造」入門」という動画を見ました。

SplというPHPの標準ライブラリが紹介されていて、便利そうだったので、何か作ってみたいと思いました。

SplPriorityQueue とは

PHPマニュアルの説明はこちらです。

優先度付きキューについては、いろいろな説明があるようです。
ざっくり言うと、配列を並べ替えながら入出力するのが、ものすごく早いようです。

まず覚えるべきメソッドは、insert()と、extract()の2つです。

$q = new \SplPriorityQueue();
$q->insert('data_1', '1');
$q->insert('data_3', '3');
$q->insert('data_2', '2');
var_dump( $q->extract() );

insert()は、配列にデータと優先度を挿入します。
insert()の第1引数がデータで、第2引数が優先度です。
（なお、データそのものが優先度と同じ場合、SplHeap等を使うのが良さそうです。）
insert()するたびに、優先度が高い順に、データを並び変えてくれます。

extract()は、配列から優先度高いものを1つ取り出して、出力します。
取り出されたデータは、配列から消えます。

よって、extract()されたものをvar_dump()すると、優先度が一番高い
string(6) "data_3"
が、出力されます。

その後、もう一度extract()すると、（data_3は$qから消えているので）優先度が2番目に高いdata_2が出力されます。

作るもの

Wikipediaの推理作家一覧のような、各行（「あ行」や「か行」など）で区切られたリストを作ってみます。

もう少し具体的にいうと、以下のような配列が与えられた場合に、その下のようなHTMLを出力したいです。

$writers = array(
    ["name" => "鮎川 哲也", "kana" => "あゆかわ てつや", "url" => "/wiki/%E9%AE%8E%E5%B7%9D%E5%93%B2%E4%B9%9F",],
    ["name" => "折原 一", "kana" => "おりはら いち", "url" => "/wiki/%E6%8A%98%E5%8E%9F%E4%B8%80",],
    ["name" => "久生 十蘭", "kana" => "ひさお じゅうらん", "url" => "/wiki/%E4%B9%85%E7%94%9F%E5%8D%81%E8%98%AD",],
    ["name" => "宮部 みゆき", "kana" => "みやべ みゆき", "url" => "/wiki/%E5%AE%AE%E9%83%A8%E3%81%BF%E3%82%86%E3%81%8D",],
);

<h3>あ行</h3>
<ul>
<li><a href="https://ja.wikipedia.org/wiki/%E9%AE%8E%E5%B7%9D%E5%93%B2%E4%B9%9F">鮎川 哲也</a></li>
<li><a href="https://ja.wikipedia.org/wiki/%E6%8A%98%E5%8E%9F%E4%B8%80">折原 一</a></li>
</ul>
<h3>か行</h3>
<h3>さ行</h3>
<h3>た行</h3>
<h3>な行</h3>
<h3>は行</h3>
<ul>
<li><a href="https://ja.wikipedia.org/wiki/%E4%B9%85%E7%94%9F%E5%8D%81%E8%98%AD">久生 十蘭</a></li>
</ul>
<h3>ま行</h3>
<ul>
<li><a href="https://ja.wikipedia.org/wiki/%E5%AE%AE%E9%83%A8%E3%81%BF%E3%82%86%E3%81%8D">宮部 みゆき</a></li>
</ul>
<h3>や行</h3>
<h3>ら行</h3>
<h3>わ行</h3>

基本的な方針

優先度を昇順に書きかえる（※）
キューを作る
作家データをinsert()する
各行のデータもinsert()する
出力する

という方針で作成します。

※ 単純に出力すると、「あ」より「か」の方が、優先度が高いため、降順になってしまいます。
「猫でもわかるWeb開発・プログラミング」というサイトで、compare()を書きかえる方法が紹介されていました。
この方法で書きかえたもので、キューを作ります。

書いたコード

<?php
$writers = array(
    ["name" => "鮎川 哲也", "kana" => "あゆかわ てつや", "url" => "/wiki/%E9%AE%8E%E5%B7%9D%E5%93%B2%E4%B9%9F",],
    ["name" => "折原 一", "kana" => "おりはら いち", "url" => "/wiki/%E6%8A%98%E5%8E%9F%E4%B8%80",],
    ["name" => "久生 十蘭", "kana" => "ひさお じゅうらん", "url" => "/wiki/%E4%B9%85%E7%94%9F%E5%8D%81%E8%98%AD",],
    ["name" => "宮部 みゆき", "kana" => "みやべ みゆき", "url" => "/wiki/%E5%AE%AE%E9%83%A8%E3%81%BF%E3%82%86%E3%81%8D",],
);

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

function create_writer_list ( array $writers ):string {
    // キューを作る
    $queue = new ReversePQ();
    // 作家情報をinsert
    foreach ( $writers as $writer ) {
        $li_tag = '<li><a href="https://ja.wikipedia.org'.$writer["url"].'">'.$writer["name"].'</a></li>'.PHP_EOL;
        $data = array( "tag" => "li", "html" => $li_tag );
        $queue->insert($data, $writer["kana"].'a');
    }
    // 各行（あ行、か行...）をinsert
    $gyo_list = mb_str_split("あかさたなはまやらわ");
    foreach ( $gyo_list as $gyo ) {
        $h3_tag = '<h3>'.$gyo.'行</h3>'.PHP_EOL;
        $data = array( "tag" => "h3", "html" => $h3_tag );
        $queue->insert($data, $gyo);
    }
    // 出力する（ulタグを入れながら）
    $html = '';
    $prev_tag = '';
    function ultag ( string $prev_tag, string $now_tag ) : string {
        $prev = ($prev_tag === 'li') ? 2 : 0;
        $now = ($now_tag === 'li') ? 1 : 0;
        return array('', '<ul>'.PHP_EOL, '</ul>'.PHP_EOL)[($prev + $now) % 3];
    } 
    foreach ( $queue as $data ) {
        $html .= ultag($prev_tag, $data["tag"]);
        $html .= $data["html"];
        $prev_tag = $data["tag"];
    }
    $html .= ultag($prev_tag, '');
    return $html;
}
// 実行
echo create_writer_list ($writers) . PHP_EOL;

感想

今回のような使い方であれば、データすべてをarrayに入れてsort()する場合と比べて、計算量が向上するわけではない（おそらくどちらもO(N log N)になる）と思います。

しかし、arrayの比較用関数を書く必要がなく、ただ既存のメソッドを書きかえるだけで済むので、コードを書く上での見通しは良かったなと思いました。