「オフラインリアルタイムどう書く E02」というイベントに参加しました。与えられた問題を解くプログラムを 1 時間の制限時間で実装するというものです。今回の問題と、各参加者の実装へのリンク集は、それぞれ以下にあります。
http://nabetani.sakura.ne.jp/hena/orde02pire/ (問題)
http://qiita.com/Nabetani/items/8d7691e9bb7655c3b990 (実装へのリンク集)
私が実装したコードは以下にあります。src/solve.php がプログラム本体です。なお、これはイベントの終了後に他の参加者のコードも参考にしながら改善、リファクタリングして書き直したものです。当日に実装したコードは src/solve-20160305-v1.php です*1。
https://github.com/y-uti/doukaku-e02/tree/1.0
今回の問題の解き方については、参加者の angel さんが解説記事を書かれています。私の上記の実装も、この記事で説明されている方針で解いています*2。
オフラインリアルタイムどう書くE02参加しました - ange1のブログ
GitHub からコードを取得して次のように実行すると、正しい答えが得られていることを確認できます。実行時間は Intel(R) Core(TM) i5-3337U CPU @ 1.80GHz の環境で PHP 7.0.4 による結果です。ただし、仮想マシン上で実行しているので、どの程度参考になる数値かはわかりません。
$ time php src/solve.php <data/original/problem.txt | diff - data/original/expected.txt real 0m0.116s user 0m0.080s sys 0m0.032s
問題のサイズによる実行時間の変化
このアルゴリズムのオーダーは、angel さんが Qiita のコメントに書かれているように、黒マスの数を B として O(B^3 * logB) になりそうです。そこで、問題のサイズに応じて実行時間が変化する様子をグラフに描いて確認してみます。
最初に、このアルゴリズムでは盤面の大きさが実行時間に影響しないことを確認しておきます。次のグラフは、長方形に含まれる黒マスの数を 10, 盤面に存在する黒マスの数を 100 に固定して、盤面の大きさ (幅と高さ) を変えたときの実行時間をプロットしたものです。横軸が盤面の幅と高さ、縦軸がランダムに生成した 10 問を解くのに要した時間の合計 (秒) です。
上のグラフで、盤面が小さなときに少し速く計算できているのは、盤面が小さいときには一本の「串」に複数の黒マスが刺さった状態になり、串の本数が少なくなるためと考えられます。逆に、盤面がどれだけ大きくなっても串の数は最大で B 本なので、実行時間が大きくなり続けることはありません。
次に、黒マスの数を増やしていったときに実行時間が大きくなっていく様子を確認します。グラフは、長方形に含まれる黒マスの数を 10, 盤面の幅と高さをそれぞれ 1,000 に固定して、盤面に存在する黒マスの数を変えたときの実行時間をプロットしたものです。実行時間は先ほどと同様に、各設定でランダムに生成した 10 問を解くのに要した時間の合計です。
最後に、長方形に含まれる黒マスの数 N を変えたときの実行時間の変化を確認します。グラフは、盤面に存在する黒マスの数を 100, 盤面の幅と高さをそれぞれ 1,000 に固定して、N を変えたときの実行時間をプロットしたものです。N が大きくなるにつれて実行時間が小さくなる様子がわかります。
このアルゴリズムでは、選んだ串に刺さっている黒マスの数が N 未満であれば、処理をスキップできます。N が大きくなるほどスキップできる場合が増えていくので、このように実行時間が短くなっていきます。
プログラムの実行方法
GitHub リポジトリの src ディレクトリにある solve_large_problems.sh を実行すると、今回の記事の実験を再現できます。このスクリプトは、data/large ディレクトリの各問題を solve_large.php で順番に解いていきます。
盤面の大きさが 62 を超えると、黒マスの位置を数字とアルファベットで表現できません。そこで、X/Y という形式で表現するように変更しました。solve_large.php はこの形式のデータを読み込むように対応したもので、問題を解く処理そのものの実装は solve.php と変わりません。
create_large_problems.sh を実行すると、実験で用いた各サイズの問題をランダムに生成します。これは、パラメータを変えながら create_problem.php を繰り返し実行するものです。create_problem.php の実行には PHP 7.0 が必要です*3*4。また、安直な実装のため、実行には大きなメモリが必要です*5。
