こんにちは、高木です。

例によって、PHPでC言語の前処理を行う話題です。今回は、PHPを使ってソート済みの配列を作成してみることにします。

何らかのキーを使って値を引き当てる、あるいはキーが集合に含まれているかどうかを調べるといったことはよくあります。状況次第でどんな探索方法が最適かは変わってきますが、データが変化しないのであればソート済みの配列を二分探索するのが一般論としては一番効率がよいのではないかと思います。

ソート済みの配列を作るには、もちろん手作業でやってもいいのですが、面倒なので普通は実行時にソートを行った配列を準備するのではないでしょうか？ ところが、その1回のソートも無コストではありませんし、RAMが少ない環境では大きな負担になります。コンパイル時にソート済みの配列を用意して、ROMに配置できればそれに越したことはありません。

そういう作業はPHPで前処理することで簡単にできます。今回は例として、単純な数値または文字列の配列を扱うことにします。構造体など、もっと複雑なデータ型のソートは別の機会に譲ります。

それではPHPのコードを見ていきます。

今回作成したmake_sorted_array関数は、配列の初期化子のみを生成しています。つまり波括弧の中に初期値を羅列するだけになっています。配列の型や名前は自分で用意しなければなりません。

make_sorted_array関数が扱えるのは数値と文字列だけです。一応、$flagsで値の比較方法を指定できるようにはしていますが、通常はデフォルトで十分です。

foreach文の中で、値が文字列であれば二重引用符で囲むようにしています。本来であれば、文字列に逆斜線や二重引用符などが含まれていればエスケープする必要があるのですが、議論の本質ではないので今回は割愛しました。

ところで、PHPのソート関数にはたくさんの種類があります。PHPの配列は連想配列ですので、キーでソートするか値でソートするか、値でソートする場合はキーとの関係を維持するかどうか、昇順か逆順か、比較処理をユーザー定義できるかどうかで使うべき関数が変わってきます。詳細は公式ドキュメントを参照してください。

また、PHP 8.0とそれ以前ではソートの仕様が変わっています。以前は基本的に不安定ソートだったのが、PHP 8.0からは安定ソートになっています。ソート結果だけを見れば安定ソートで問題ないのですが、実行速度やメモリ使用量が気になるところです。想像ですが、メモリを潤沢に使ってマージソートや二分木ソートのような計算量が\(n  \log{n}\)になるアルゴリズムを使っているのだと思います。私なんかは、不安定ソートでいいから高速でメモリ使用量が少ない選択肢が欲しい方なのですが、PHPの典型的な用途では違うのかもしれませんね。