0
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

PHP の SplPriorityQueue を使って、推理作家一覧を作りたい

Last updated at Posted at 2024-08-14

きっかけ

先日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>

基本的な方針

  1. 優先度を昇順に書きかえる(※)
  2. キューを作る
  3. 作家データをinsert()する
  4. 各行のデータもinsert()する
  5. 出力する

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

※ 単純に出力すると、「あ」より「か」の方が、優先度が高いため、降順になってしまいます。
「猫でもわかる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の比較用関数を書く必要がなく、ただ既存のメソッドを書きかえるだけで済むので、コードを書く上での見通しは良かったなと思いました。

0
0
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
0
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?