Google Code Jam 2009 の思い出 (3)
Google Code Jam 2011 も Round1 で撃沈したのでそのことでも書こうと思っているですが、もう少し検証したいこともあるので、先に一昨年＆昨年の GCJ の話を吐き出しておきます。
ということで、一年前に書いた
の続きで、パフォーマンス関連の話題になります。
概観
この年私は全て Perl で解いていたんですが、GCJ 2009 Round1A の A 問題
が肝で。この問題、Small は解けたんですが Large については計算が 8 分の制限時間内にぜんぜん終わる気配がありませんでした。
ほかの人はどうだったんだろう？ということで統計ページを除いてみると・・・LL の通過率が異常に低い。
通過率を抜き出すとこんな感じ。（※2009 年に抜き出したものなので統計が変わってるかもしれません。）
| Language | Small | Large | Small通過者のLarge通過率 |
|---|---|---|---|
| C | 43 | 11 | 25.6% |
| C# | 119 | 22 | 18.5% |
| C++ | 1042 | 350 | 33.6% |
| Haskell | 13 | 0 | 0.0% |
| Java | 394 | 79 | 20.1% |
| Pascal | 21 | 10 | 47.6% |
| Perl | 37 | 1 | 2.7% |
| PHP | 21 | 1 | 4.8% |
| Python | 205 | 3 | 1.5% |
| Ruby | 43 | 0 | 0.0% |
| Scala | 6 | 0 | 0.0% |
| Scheme | 5 | 1 | 20.0% |
| Erlang | 1 | 0 | 0.0% |
| F# | 2 | 0 | 0.0% |
| Factor | 1 | 0 | 0.0% |
| Groovy | 2 | 0 | 0.0% |
| Javascript | 4 | 0 | 0.0% |
| Lisp | 3 | 0 | 0.0% |
| Objective-C | 2 | 0 | 0.0% |
| OCaml | 2 | 2 | 100.0% |
| Standard ML | 1 | 0 | 0.0% |
| Visual Basic | 4 | 0 | 0.0% |
| Total | 1971 | 481 | 24.4% |
Python は Small を解いた 205 人中 3 人しか Large 通過してないし、Ruby については Small を通過した 43 人が Large の通過に失敗しているという、ちょっと壮絶な感じです。
Perl で解いた人はどうやってる？
を見ると Perl で Large を解いたのは 2 人ということになっているんですが、ErickW は C++ で計算して Perl を補助的に使っているみたいなので除外して。ちゃんと Perl で解いているのは cugbcat 一人だけと。
- Code Jam 2009 Statistics ・ Participant Details: cugbcat
- ※リンク先の解法を気軽に見たい方は この bookmarklet をご利用ください
この解法と自分の解法を見比べてみたんですが、基本的な解き方には大差なくて、アルゴリズムがいくらか洗練されている感じ？これで 8 分以内に終わるのかな？
と、ためしに自分の環境で実行してみると・・・8 分以内に全然終わらなかった。この人の PC どれだけ高性能なんだろう・・・。でも自分のスクリプトよりは数倍早いみたい。
C だとどんなもの？
C の人のコードを適当に引っ張ってみると、Large は 42 秒くらいで計算が終わっているようで。やっぱり Perl と C じゃ実行速度が比較になりませんね。
処理を改善してみる
まず cugbcat の処理を参考に少し手直ししてみたんですけど、速度はあまり変化なく。どこでこの数倍の差が出てしまってるんだろう？
DProf でプロファイリング→あんまり意味なかった
チューニングするならちゃんとプロファイルとらないとだめだろうということで、
ここを参考にやってみました。
>perl -d:DProf multi_base_happiness.pl < large.in >dprofpp Total Elapsed Time = 27.94769 Seconds User+System Time = 27.09869 Seconds Exclusive Times %Time ExclSec CumulS #Calls sec/call Csec/c Name 157. 42.56 42.566 641651 0.0000 0.0000 main::calc 0.06 0.015 0.015 5 0.0030 0.0030 Data::Dump::BEGIN 0.00 - -0.000 1 - - Exporter::import 0.00 - -0.000 1 - - warnings::BEGIN 0.00 - -0.000 1 - - warnings::import 0.00 - -0.000 1 - - subs::import 0.00 - -0.000 2 - - strict::bits 0.00 - -0.000 2 - - vars::import 0.00 - -0.000 1 - - overload::BEGIN 0.00 - -0.000 3 - - strict::import 0.00 - -0.000 4 - - warnings::register::mkMask 0.00 - -0.000 3 - - vars::BEGIN 0.00 - -0.000 2 - - warnings::register::import 0.00 - 0.015 4 - 0.0037 main::BEGIN
・・うん。メインの計算処理で時間を食ってると。そりゃそうだ。
もっと関数を小さくしないとプロファイリング意味ないなぁ。でもそうすると関数呼び出しのコストが・・・うーん。
浮動小数点の計算をなくしてみる
cugbcat のスクリプトをちまちま移植したりして念入りに比較すると、私のスクリプトで
$m /= $base;
と書いていたところが、cugbcat のほうは
$m = int($m / $base);
となっていました。・・・あー、私の処理は一度割り算が発生して以降は浮動小数で計算されていたから遅かったと。とりあえずこの一行を変えるだけで cugbcat と同じくらいの速度は出るようになりました。でもまだまだ 8 分で終わるところまでは辿りつけないので、もう少しがんばってみます。
Perl のソースコードに手を入れたり→無駄足
なんでこの人の Perl こんなに速いの？なんか手を入れてるんじゃないの？とか思って自分も手を入れてみることにしました。具体的には浮動小数での計算に入ってしまう可能性のある処理を整数での計算に書き換えたり。・・・とかいろいろやってて気づいたんですが、
use integer;
していればその辺はうまいこと整数だけで計算してくれるみたいで、完全に無駄足でした。use integer してれば上に書いたような int のキャストも要りませんし、整数計算しかしないときは何も考えずにつけておくとよさげです。
Inline::C を使ってみる
いざとなったらインラインで別の言語を使えるのも Perl のいいところ、ということで Inline::C に手を出してみました。
ActivePerl ではうまく動かなかったので mingw のほうで。あとパスにスペースあるとうまく動作しないようなので、スペースを含まないパスで実行する必要がありました。
どうも割り算まわりの処理がまだ重そうなので、
use Inline 'C' => q<int divi(int a, int b) { return a / b; }>みたいに C で書いてみたり。でも Perl と C のインターフェイスの部分がまだ重そう。
use Inline 'C' => q<void divi(SV* a, SV* b) { SvIV_set(a, SvIVX(a) / SvIVX(b)); }>;みたいにすればインターフェイスがシンプルになるかなと思ったらそうでもなく。剰余も利用する形にすればいいのかな？と
use Inline 'C' => q<
#include <stdlib.h>
void divi(SV* a, SV* b, SV* c) {
div_t temp;
temp = div(SvIV(a), SvIV(b));
SvIV_set(a, temp.quot);
SvIV_set(c, temp.rem);
}
>;みたいにやってみると・・・処理遅くなった。もうメイン処理部分 C で書いちゃおう、と
use Inline 'C' => q<
#include <stdlib.h>
int get_next(int num, int base) {
int next = 0;
while (num) {
div_t temp = div(num, base);
next += temp.rem * temp.rem;
num = temp.quot;
}
return next;
}
>;ここまでやると、ようやく計算が 8 分前後で終わるようになりました。でもここまでやるんなら最初から C で書いたほうがいいような・・・。
その後わかったこと
模範解答
ということで一昨年は悩んだ末に「やっぱり LL だけじゃきついかも」と LL への情熱が冷めてしまっていたんですけど、今年見るとちゃんと解説が載ってました。
この解説によると、
- 全組み合わせは 500 通りくらいなもんだから、あらかじめ全部計算しておいて、Small とか Large の時間内にはその結果を使う処理を動かすだけでいいんだよ。
- あと 1,000,000 以上の計算はキャッシュしなくてもいいよね。一回の計算ですぐ収束するから 1,000 くらいまで持っておけば十分でしょ
とのことで。C とかだと力技で解けちゃってたみたいですけど、LL では力技では解きにくいってだけで、解く手段が用意されてないわけではなかったみたいです。さすが良く作られてる・・・。
Python 勢は？
Python ではふつうに解いてる人が 3 人いたわけですが、こちらも覗いてみました。
まずこちら。
なんだか洗練されたコードです。当時「なんで yield 使ってるんだろう？」って疑問を持っていたんですが、
の最後のほうに Python の yield の特徴とか載っていて納得。スタックオーバーフロー起こしにくくなると。
あと面白いのはこの解答。
import psyco してる・・・（参考: Psyco - Wikipedia）。こういう裏技っぽいのが使えるのはいいなぁ。
