きっかけ
先日YouTubeで、PHPカンファレンス福岡での、きんじょうひできさんの「SPLから始める「データ構造」入門」という動画を見ました。
SplというPHPの標準ライブラリが紹介されていて、便利そうだったので、何か作ってみたいと思いました。
SplPriorityQueue とは
優先度付きキューについては、いろいろな説明があるようです。
ざっくり言うと、配列を並べ替えながら入出力するのが、ものすごく早いようです。
まず覚えるべきメソッドは、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の比較用関数を書く必要がなく、ただ既存のメソッドを書きかえるだけで済むので、コードを書く上での見通しは良かったなと思いました。