paizaオンラインハッカソンVol1 お疲れさまでした

実際に取り組んでたのが12月の頭頃、結果発表が1月の中旬と、なんだかずいぶんと時間がたってしまったpaizaオンラインハッカソンVol1ですが、この手のにしてはいつになくそれなりにがんばったおかげで無事C言語で1位タイ(rarul)取ることができました。運営側も他の参加者もお疲れさまでした。せっかくなので私なりにどうがんばったのかまとめておきます。

この手のは基本的にアルゴリズム部分が主になるので、そこは他の人たちがすでにたくさん解説してくれるだろうということで省きます。というか、正直私自身が、真剣にアルゴリズム部分を考える前に、友人のほぼ完成されたアルゴリズムの回答を見てしまったので、あんまり考えられてないんですよねぇ。ズルといわれても仕方ない。なので、アルゴリズムじゃないところを中心に語ります。とりあえず作ったパッケージをアップしときます(5MBくらい)。思ったよりでかかったのでソースコードだけ(6KB)のも。

まず、提出するコードが正解をはじき出さないと話にならないので、そこに取り組みます。ランダムデータ生成スクリプト(パッケージの中ではmakep.pl)等を使ってテストデータを作り、また作りかけのプログラムなどを駆使して正解データも作ります。で、作ったコードをコンパイル・実行・入力・出力・出力までにかかった時間・出力結果が正しいかを事前に用意した正解データと比較する、までをスクリプト一発で実行できるよう自動化します。パッケージの中では、make.sh, test.shあたりが自動実行、input[1-8].txtが入力データ、output[1-8].txtが出力データ(期待の正解データ)です。ここまでやるのは正直めんどいかと思いますが、本気で取り組むなら真っ先にやっとくべき箇所でしょう。

次は時間計測です。一般論として、0.1秒を0.01秒にするのと1秒を0.8秒にするのとでは、前者の方が大変で後者の方が楽だけど、前者の方が高速化効果が薄くて後者の方が高いです。つまり、相対的に時間のかかっている箇所をがんばって早くしないと、トータルでは意味がないのです。ということは、どこに時間がかかっているのかをはじき出さないとどこをがんばればいいのかがわかりません。というわけで、プログラムを細かく時間計測して、どこの処理にどのくらい時間がかかっているのかを出すことが大事になります。私は clock_gettime() で区間ごとの時刻を取りその差分で時間を計りましたが、精度よく時間が取れれば他の方法でもいいでしょう。

そこそこまともなアルゴリズムでプログラムを動かしてみるとわかりますが、今回の運営側の Case 3 を0.2秒程度で完走できるレベルになると、残りの高速化ポイントはテストデータを読み込む箇所であることがわかります。これまた一般論として、世の中で稼働してるプログラムはたいてい入出力に時間がかかってます。なぜ時間がかかるかというと、そもそも読みたいデータがまだ届いてなかったり(HDDやらネットワークからからの転送待ち)、読んだデータが期待通りのデータかを確かめないと危険だったり(操作ミスしてたりファイル壊れてたり)、おかしいときはそれなりのエラー処理をしないといけなかったり(ファイルを初期化するとかエラーダイアログ出すとか)、などなどです。今回の問題では標準入力(STDIN)から読み取り標準出力(STDOUT)に正解を書くという設定でしたが、そもそもSTDINから次々に読めるのかどうか、標準出力に次々に書けるのか、とかは一般的には考えないといけない要素でしょう。まぁさすがに今回のような問題だと、リダイレクトで読み書きさせることで、そこまで考えなくてもよいようにしてるでしょうけど。で、どうやって読込を高速化するかですが、今回の場合だとこんな感じでしょう。

scanfを使わない。運営が用意したサンプルはscanf使ってますがscanfなんて一般的に使っちゃダメです。セキュリティ面でも速度面でも。何を使うか迷うくらいなら、テキストを読むならfgets、バイナリを読むならfread、とまずは覚えときましょう。今回私はfgetsのコストも惜しかったのでfreadで読んで自前でパースしましたが、一般的にはfgetsで十分に高速です。極限まで極めたい場合のみ、システムコールのreadやmmapを使うことになると思います。まぁそこまで来たら「HTTPやファイルシステムなんておせーから自前で作ろうぜ」とかなるんでしょうけど。

atoiを使わない。厳密には読み込みじゃないですが入力処理の一環ということで。fgets等を使うと必然的にascii文字を数値に変換する必要がありますが、そんな場合は普通はatoi使います。が、計ってみるとわかりますが、atoiは結構マジメにエラー処理をしてくれる関数なため、結構時間かかります。今回みたいに'0'から'9'までとわかっている場合は自前で処理した方が早いです。

と、この辺までがんばると、もはや誤差とも言いたくなるほどの微妙な処理時間と戦うことになります。私もそこまで本格的に取り組んだことはないので胸を張っては言えなくなってきますが、たとえば、CPUの種類(周波数やらパイプライン処理やら分岐予測やら)、CPUキャッシュサイズ(CPUのL1,L2,L3サイズとアクセス速度)、を意識することになります。gcc拡張として用意されている __builtin_expect や __builtin_prefetch があるのでまずはこれを利用することとして、あとはランダムアクセスするときの配列の大きさやらループアンローリングやらパイプラインの乱れやらを意識したプログラムを作ります。このレベルになると、C言語レベルではなくて、コンパイルした結果のアセンブラコードを見た上で判断すべきですね。今回は運営側は gcc-4.7.2とは書いていますが、コンパイルオプションは書いてないですしCPUの種類も書いてないですし、正直何をターゲットに最適化したらいいか難しいです。gcc -O3で x86_64 で Ivy Bridge世代のXeonあたり、が実際のとこなんじゃないかと思いますが。といいつつ、私はテストはAtom N270なマシンでやっていましたが・・・

最後に、言うまでもないですがこの手のはアルゴリズムが大事です。テストの自動化と時間計測とを準備したら、まずはアルゴリズムを徹底して固めるのが先決です。あと、小手先高速はあんまりやらない方がいいです。特に、入力の高速化と称して標準の関数を使わずに自前で用意するとか、エラー処理をガン無視できる今回のような例だからこそ可能なだけで、一般的には徹底的にエラーチェックをすべきです。一般的には速度が求められるはまれです、もしあったとしてもピンポイントな箇所のみです、漠然と「高速化しろ」と言われてもきちんと時間計測して時間のかかっている箇所を特定してその箇所だけ努力すればいいのです。速度最優先なのは、数値計算などのごく一部の分野のみです。

ところで、景品の新人女子プログラマの野田さんがまだ送られてこないのですが、いつになるんでしょうか...

このブログ記事について

このページは、らるるが2014年2月 2日 01:15に書いたブログ記事です。

ひとつ前のブログ記事は「「不本意な敗戦 エルピーダの戦い」読んだ」です。

次のブログ記事は「SMS付きSIMに変えてみた」です。

最近のコンテンツはインデックスページで見られます。過去に書かれたものはアーカイブのページで見られます。

月別 アーカイブ

ウェブページ

Powered by Movable Type 7.9.0