miauのブログ

はてなダイアリー「miauの避難所」をはてなブログに移行しました

paizaオンラインハッカソンVol.2 と PHP コード最適化の話

会社の人からこのネタを振られて。「業務で PHP を使ってる身だし、PHP で最速を目指してみるかー」とやってみたので、そのお話。

さっそくやってみた

30 分くらいでてきとうに解いたところ・・・。

Test case 3 失敗 (出力結果が間違っています)

えー?時間切れならともかく、答えが合わないってことは無いと思うんだけどなぁ。

後に判明したんだけど、

PHP,Ruby,Python,Perlは全テストケースで以下の条件を満たします。

1 ≦ H ≦ 130 ※ 画面縦の区画数
1 ≦ W ≦ 130 ※ 画面横の区画数
1 ≦ N ≦ HW ※ ウィジェットの個数
1 ≦ S_i ≦ 300 (1 ≦ i ≦ N) ※ ウィジェット縦大きさ
1 ≦ T_i ≦ 300 (1 ≦ i ≦ N) ※ ウィジェット横大きさ

「この『1 ≦ S_i ≦ 300 (1 ≦ i ≦ N)』は『1 ≦ S_i ≦ 130 (1 ≦ i ≦ N)』の誤記だよなー」、と勝手に問題を読み換えてたせいでした。チューニングする→答えが合わない、みたいなことを繰り返してるうちに応募受付期間が終ってしまったので、「※130 ではなく 300 です」みたいに明示しておいてくれると嬉しかったなー、とか思いました。

考えたアルゴリズム

今回の問題に興味がある方だけどうぞ。PHP のコード最適化にしか興味がない方は、「最適化」のところまで読み飛ばして大丈夫です。

ステップ1
00000
00100
00010
10001
10000

こういうホーム画面があるとして。まずは各座標から、右に連続する 0 の個数を数えます。

54321
21021
32101
03210
04321
ステップ2

この各列の末尾に番兵っぽく 0 を入れた上で、縦方向に

523000 412340 301230 220120 111010

と読んでいきます。

523 という並びは、この列から右向きにこの幅のウィジットが置ける、つまり

00000
00
000

といった領域に配置が可能だという意味でした。ここから各列に置ける最大のウィジットの個数を

$preCount = [
    1 => [3 => 1], // 1 列目には高さ 3 のウィジットが 1 つ置ける
    2 => [3 => 1], // 2 列目には高さ 3 のウィジットが 1 つ置ける
    3 => [1 => 2], // 3 列目には高さ 1 のウィジットが 2 つ置ける
    5 => [1 => 1], // 5 列目には高さ 1 のウィジットが 1 つ置ける
    4 => [1 => 1], // 4 列目には高さ 1 のウィジットが 1 つ置ける
]

といった形で求めます。これは、各列ごとに 0 が始まった時点での y 座標を覚えておいて、0 が終わった時点での y 座標との差分を求めることで埋めていきます。

ステップ3

上記のデータ上で「2 列目には高さ 3 のウィジットが 1 つ置ける」となっていても、実際は

  • 高さ 3 のウィジットが 1 つ
  • 高さ 2 のウィジットが 2 つ
  • 高さ 1 のウィジットが 3 つ

置けるので、これを展開して、

$count = [
    1 => [3 => 1, 2 => 2, 1 => 1],
    2 => [3 => 1, 2 => 2, 1 => 1],
    3 => [1 => 2],
    4 => [1 => 1],
    5 => [1 => 1],
]

この形に変えます。

ある列から見て n 列目にウィジットを置けるというのは、結局幅 n のウィジットを置けるのと同じことなので、$count[$width][$height] は $width x $height のウィジットをいくつ置けるかというデータになります。あとはウィジット毎にこの配列からルックアップするだけ、と。

これを実装したコードがこれ(最初に投稿したコードではなく、変数名とかをわかりやすく書き換えたもの。)で、

この状態では

Test case 7 は 0.12 秒と。(以下 Test case 7 の時間を基準で考えます。)

もっと効率のいいアルゴリズムもあるかもしれませんが、思いつかないのでこれベースで最適化について説明します。

最適化

競技プログラミングでも、業務アプリでも、計算のオーダーを減らすことが大切です。O(N^2) で済む処理を O(N^3) で書いたりしていたら、最適化してもほとんど効果はないです。

十分計算のオーダーが減って、それでもさらに処理を速くしたい場合は、最適化に手を出すことになります。

最適化については以下の URL に色々と載ってました。

遅くならないコードを書く(未定義のローカル変数を参照して warning が出ないように書くとか)のが大切ですが、PHP コードを最適化をする上で重要なのは、前者の URL に載っていた

39. もとから用意されてる 関数たち を活用しよう。

これだと思ってます。

C のように自前で処理を書いても十分な速度を出せる言語では、最適なデータ構造とアルゴリズムを自前で実装すればいいのですが、PHP でがんばって複雑な処理を書いても実行が遅くなります。PHP の処理を減らして、C で書かれている標準関数をいかにうまく使ってやるかがポイントになります。

わかりやすい例では、さきほどのコードにあった

for ($x = 0; $x < $w; $x++) {
    $map[$h][$x] = 0;
}

この処理は、

$map[$h] = array_fill(0, $w, 0);

と書けます。こうしたほうが処理が速いですし、可読性も高くなることが多いです。

さて、さきほどの処理でボトルネックになっているのは、実はここ。

fscanf(STDIN, '%d', $n);
for ($i = 0; $i < $n; $i++) {
    fscanf(STDIN, '%d%d', $wh, $ww);
    echo isset($count[$ww][$wh]) ? $count[$ww][$wh] : 0, "\n";
}

最後に各ウィジットのサイズを読み込んで結果を出力するループですが、PHP 側で最大 16900 回

  • ループの駆動
  • 標準入力からの読み込み
  • 配列のルックアップ
  • 標準出力への書き出し

の処理を行っているので、まあ遅いわけです。

こんな感じに書き換えるとどうでしょうか。

fgets(STDIN);
$data = stream_get_contents(STDIN);
echo preg_replace_callback(
    '/([0-9]+) ([0-9]+)/S',
    function($m) use ($count) {
        return isset($count[$m[2]][$m[1]]) ? $count[$m[2]][$m[1]] : 0;
    },
    $data
);

ループの駆動は preg_replace_callback() の内部で行われるようになり、PHP 側で行っている

  • 標準入力からの読み込み
  • 標準出力への書き出し

も一度ずつしか行われなくなりました。PHP 側で 16900 回行われるのは、配列のルックアップ(とクロージャの呼び出しに伴なうオーバーへッド)だけです。
(ちなみに正規表現では S 修飾子 を使ってます。詳しくはこちらを参照。
 正規表現処理エンジン PCRE の パータン分析スイッチの有効性について [nao-pon/blog/2013-06-27] - UsersWiki - XOOPSマニア

変更後のコード全体は

これで、結果は・・・

0.12 秒から 0.05 秒になりました。
(2014/05/22 追記)
・・・と偉そうに書いておいてなんですけど、

 fscanf(STDIN, '%d', $n);
+$out = '';
 for ($i = 0; $i < $n; $i++) {
     fscanf(STDIN, '%d%d', $wh, $ww);
-    echo isset($count[$ww][$wh]) ? $count[$ww][$wh] : 0, "\n";
+    $out .= isset($count[$ww][$wh]) ? $count[$ww][$wh] : '0';
+    $out .= "\n";
 }
+echo $out;

のように出力を一度にするだけでも十分速いですね。ローカルでの計測だと preg_replace_callback() のほうが 0.002 秒くらい速い程度でしたが、環境によってはこちらのほうが早いのかも?
(2014/05/22 追記ここまで)

ダメ押しでもう一つ最適化してみましょう。ステップ1 で 0 の連続を、

for ($y = 0; $y < $h; $y++) {
    $width = 0;
    for ($x = $w - 1; $x >= 0; $x--) {
        if ($rawMap[$y][$x] == '0') {
            $map[$y][$x] = ++$width;
        } else {
            $map[$y][$x] = $width = 0;
        }
    }
}

のようにして数えてますが、これも標準関数に任せられないでしょうか。残念ながら PHP は今回の用途に使えるような配列関数が充実していないのですが、文字列であれば preg_replace_callback() に任せられます。幸い幅も高さも 130 までで、1 byte に収まりますので、

$map = [
    ['5', '4', '3', '2', '1'],
    ['2', '1', '0', '2', '1'],
    ['3', '2', '1', '0', '1'],
    ['0', '3', '2', '1', '0'],
    ['0', '4', '3', '2', '1'],
];

ではなく、

$map = "\x05\x04\x03\x02\x01"
     . "\x02\x01\x00\x02\x01"
     . "\x03\x02\x01\x00\x01"
     . "\x00\x03\x02\x01\x00"
     . "\x00\x04\x03\x02\x01";

この形に持ってしまいましょう。すると、上記部分の処理はこうできます。(左右どちらから数えても同じなので、54321 ではなく 12345 のようにしています。その他細かい変更もあるので詳しくは diff を見てください。)

$chars = "\x01\x02\x03\x04\x05\x06\x07\x08\x09\x0a\x0b\x0c\x0d\x0e\x0f\x10\x11\x12\x13\x14\x15\x16\x17\x18\x19\x1a\x1b\x1c\x1d\x1e\x1f !\"#\$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\\]^_`abcdefghijklmnopqrstuvwxyz{|}~\x7f\x80\x81\x82";
$rawMap = preg_replace_callback(
    '/0+/',
    function($m) use ($chars, $w) {
        return substr($chars, 0, strlen($m[0]));
    },
    $rawMap
);

コードの最終形は

これで、結果はこう。

・・・あれ?タイムは変わらず 0.05 秒のままですね・・・。
ローカルでは 0.002 秒くらい速くなってましたし、以前これと同じ処理を書いたときは 0.04 秒になったので、調子がよければ 0.04 秒に乗るんじゃないかと思います。

とまあこんな感じで、PHP での最適化は標準関数を組み合わせるパズルみたいになってくるので、個人的にわりと楽しいです。

最後に

最適化のやり方をいくつか書きましたが、業務では可読性優先で書いています。上記のような最適化をするのは、呼び出し回数が多く、他の人の目に触れることが少ないフレームワークやライブラリの内部だけです。それもボトルネックがあったであることが判明してからで、上記の例だと 1 つめの最適化はやっても、2 つめは実コードとしては残さないでしょう。

実際にやった例を載せておきます。

Doctrine2 で Oracle にクエリを投げる際に使われるパラメータ置換処理(「?」を「:param1」等に書き換える処理)が遅かったので、まさに今回書いた preg_replace_callback() での最適化を行ったのでした。この処理はコールバックが呼ばれる回数が少ないので preg_replace_callback() による最適化は特に有効で、確かこの処理単独で 20 倍くらい速くなった気がします。

「速くしたいなら拡張モジュールを作れば?」って意見もあるかと守いますが、保守性の問題で手を出していません。元々 PHP しか知らない人でも保守できるように PHP で開発しているわけで、C を書けないと保守できないようだと意味がないので。

とはいえ、自分で拡張モジュールを作って「やっぱり C で書くと速いよなー」とかなんとか遊んだりはしてました。これをやっておくと最適化するときにある程度処理コストの予想ができるようになるので、知識として知っておいて損はないですね。まあ予想が裏切られることも多いので、最終的には計測が重要ってことになるのですが。