スーパーコン反省会。（10/08/31）

今年はJOIとか他いろいろに参加しようとがんばりたいんだけど、2次元にもがんばらないとなぁとか



..10/08/31(火) 18:57:42
スーパーコン終わった。
ブログに書く人もいるようだけど、アルゴリズムも考えていない自分が書くことなんてないでしょ、と思ってたけどまぁ。
初日に問題が説明されたときから思考停止してた。
最初から解こうとしてなかった。
だけどやっぱりがんばってても解くの大変だったと思う。無理かも。

このコンテストの概要を誰ともなく説明してみると、「スーパーコンピュータを使って問題を解かせる」かな？
なんか文章がおかしい気がするのはほっておこう。
今年は東工大のスパコンTSUBAMEの弟分のTSUBASA？を阪大から使ってた。
問題はレンガ敷き詰め問題で、レンガを敷き詰めたら何通りになるか求めろって問題。
予選問題はかろうじて解けた。でも自分一人だったら通らなかったのかもな。
行列の乗算は早くできるとかなんかそんなかんじので、解き方が分かっただけじゃ早さが足りなくて予選落ちる。
行列使ったら早くできるって、そんな一般人知ってることじゃねーよ……とは思うけどまぁあの集団普通じゃない。

数学できないとプログラム書けないんだ！
いや、アルゴリズマーにはなれないんだ！

来年からのためにちょっとはアルゴリズム勉強しようと思った。
だって本戦出たけど実は探索木を実装したことないとかうわぁそんなこと言えるわけ（ｒｙ
ちょくだいさんが書いてるアルゴリズマーになろうってかんじの記事、最初の方は読んだけど意味わかめ。
まぁいいや、スーパーコンの反省。

10000問はといたつもりだった。10個の入力ファイル喰わせた。1つ遅かったから最後の方で止めた。
結果10000問より20問少ないぐらいの点数だった。
これで上位の方だったらなにそれひどいｗ　と思ってたんだけど、まじで上位だったからびびった。
工夫も何も、先輩が少々解けるぐらいに高速化したサンプルしか使ってない。
まぁ他のところも、動的計画法（DP）を使って解けるようなアルゴリズム作れたところはほとんどなかった。
作れたところはわたしたちより上位に入ってた。。

運良く5位だったところで、勝因はなんですか？とか聞かれて、「人力です」とか答えるの？
要は着目点とか手際のよさとかだったんじゃないかな。
でも自分たちが手際よかったって訳じゃない。
むしろ、もっと自動化で準備してればよかったと思う。
ただ5位以下はほんとしょぼい。全問題の10分の1も解けなかったんだよ？

反省点：
解析を人力じゃなくて少しでもプログラムにやらせてればよかった。
だけど、練習用の入力が小さい順に並んでたから失念してた。
出題が簡単な順にされるとは限らなかった……。
それに問題数が、全部で10000問だと思ってたんだけど100000問あった。ファイル数が10倍とか人力でつっこんでたら、普通に考えて1ファイルに数分時間を使うと足りなくなる。
すらすら問題が解けていても、全部キューに投入する時間がない。
……本番で何問出題されるとかどっかに書いてあったっけ……。
書いてあったとしたら、自分が残念だった。
アルゴリズム考える気が最初からなかったからMPIとか並列化をちゃんと成功させようと思ってたけど、最小限以外のことはできてなかったし。

とりあえず統計ファイル読み込んで、フィールド数が小さいのから解いていくくらいでも書いておけばよかった。
1回のキュー投入でいくつもの問題ファイルを読み込む仕様にしておくべきだった。
まぁ問題の難しさを自動で解析させてたところで、それが失敗して下の方に入ってたチームもあったんだけど。


まぁ反省は適当でいいや。
他のあまりバッチ処理を練習してなかったチームに比べて勝ったと思うのは、キューの投入。
バッチを投入してから実行されるまでの間に少し待ち時間がある。そのおかげで100個も投入する時間がなくなっていた訳なんだけどまぁこれはおいておいて。
実行が終了してるはずの時間でも、qstatするとまだ実行中になってる。
出力はできてる。
だから実行後にも待ち時間があるわけだ。

いちいちqstatして終わってるか確認するのがめんどくさかったので、標準出力のファイルを見て実行が終わってるようだったら、qdeleteしてもう新しいのをつっこんでた。
それで少し時間を有効に使えたけどそれ以外で無駄なことしてたけどな……。
たとえば、本番中にシェルスクリプト書いてたりとかｗ
その書き方を間違えてちょっと修正したりとか時間の無駄。
まぁね、準備不足。

人力で統計ファイルを見て簡単な問題を探すって馬鹿だよね。
45分間あっというまだった。


さて、こんだけ書いたけど、あまりこの記事目当てで探しに来る人いないと思ってかいてるから見つかったら怖い。
スパコンとか書いても検索には引っかからないと思ってかいてるから引っかかったら怖い。