y_uti のブログ

統計、機械学習、自然言語処理などに興味を持つエンジニアの技術ブログです

オフラインリアルタイムどう書く E02 のプログラム実行時間

オフラインリアルタイムどう書く 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

*1:これも、制限時間の 1 時間では完成させられず、15 分ほどの延長時間を使って完成させたものです。

*2:さらに高速な解き方があるのかもしれませんが、今回の参加者の中では、これよりも高速な解き方を実装した方はいませんでした。

*3:?? 演算子** 演算子PHP 7.0 の機能です。これを書き直せば PHP 5 でも実行できます。

*4:[2016-03-09 追記] ** 演算子PHP 5.6 から導入されています。内容を修正しました。

*5:PHP 7.0.4 で memory_limit = 1024M に設定して、盤面のサイズ 4,000 程度が限界でした。