チームラボ天下一武道会 - 純粋関数型雑記帳

チームラボ天下一武道会～コードGolf & F1レース！～ : ATND
に参加してきました。普段Java使っていないのでどうなるかと思いましたが、なんとか優勝することができました。

問題は、ユーザデータと商品の購入データが与えられるので、全商品間のコサイン類似度を求めよというものでした。入力は

<ユーザID>,<商品ID>

のCSVで与えられ、出力は商品ID×商品IDの二次元配列をCSVで出します。購入データは1万件、ユーザ数は1000以下、商品数は500以下という制限です。

順位は、実行時間によるスコアとバイトコードのサイズによるスコアの和によって付けられます。それぞれ50点満点で、実行時間は

10秒 (50点)
60秒 (0点)

バイトコードのサイズは、

1Kbyte (50点)
6Kbyte (0点)

を基準として、線形補完されて決まります。50点満点ですが、基準値を超えた場合は60点まで加点されるとのことでした。

最初問題聴いたときは、効率のいい疎行列計算しろってことなのかなとか思ったのですが、入力データはそんなに疎ではないらしいし（と思ったけど、500*1000=5万と勘違いしてたようでした）、そもそも密行列で持ってばかな方法でも 500^5*1000 = 2500万ぐらいの計算量で済むので、10秒どころか1秒もあれば余裕ではないのかと思いました。Rで計算すると60秒ほどかかるそうなのですが、それの6倍速が上限というのは緩かった気がします（しかしこれ以上短くすると、JVMの起動時間が無視できなくてあれかもしれない…）。そういうわけで、時間は多分緩いけど、バイトコードサイズ1KBは相当厳しそうに見えたので、純ゴルフ勝負になりそうな予感でした。

まずは適当に組んでみますと、実行速度は手元で2.5秒ほどで、やっぱりそんなにかからない。バイトコードサイズは2.8KBほどで、これをどこまで縮められるかという感じ（そもそも空のクラスでも300バイトぐらいあるんですよ）。まあしかし、普段Javaでコード書かないものですから、Javaの重箱仕様やら、ましてやJVMのことなんかよくわからない。どうやれば小さくなるかなんて皆目見当もつきませんでしたが、とりあえず小さくなりそうなことをひとつずつやっていきました。

ローカル変数名の長さはバイトコードサイズとは無関係
使っているクラス数を減らすとガクッとサイズが減る（TreeMapはMapじゃなくてTreeMapで受けるべし、とか）
使っているメソッド数を減らすとサイズが減る（メソッドごとに文字列で参照情報が入るのだろうか？）
改行を消すと縮む場合がある（多分デバッグのための行番号の情報）
メソッドの引数名の長さはバイトコードサイズに影響
try catch より throwsのほうが短い
変数宣言はまとめたほうが短い
forの宣言部などに入れられるものは入れたほうが短い
複雑な式を関数の引数に入れるとなぜかでかくなる
importはバラでやったほうが若干短い

そういうわけで、こつこつ短くしていきました。最初はどんな入力がきても大丈夫なように作っていたのですが、入力が決まっているので、配列長決めうちにしてArrayListから配列に変えたり、ユーザIDと商品IDはぬけがある時のためにTreeMapを用いて内部IDに変換していたのをやめて、ちょっと計算は無駄になるけどぬけてるとこも計算しちゃうとか、出力は対象行列になるから上半分だけ計算していたのを、どうせ計算にはそんなに時間掛からないからすべて計算することにしたり（データを保存しておくための配列が要らなくなる）、入力を読みながら隣接行列構築するなど、許容される範囲で速度を遅くしつつ、コードを簡略化していくという作業を続けた結果、速度3秒（評価環境では5秒ぐらい？）、バイトコードサイズ1390バイトぐらいにまで縮みました。コードのサイズでいうと、最初は80行ぐらいあったのが、最終的には25行ぐらいになりました。

import java.io.FileReader;
import java.io.BufferedReader;
import java.io.PrintWriter;
class cosine{
    public static void main(String[] a) throws Exception{
	BufferedReader br = new BufferedReader(new FileReader(a[0])); br.readLine();
	PrintWriter pw = new PrintWriter("output.csv");
	double[][] tbl = new double[512][1024];

	for (String line;(line=br.readLine())!=null;) tbl[new Integer(line.split(",")[1])][new Integer(line.split(",")[0])]++;

	for (int i=0; i<512; i++){
	    double ni=0; for (int k=0; k<1024; k++) ni += tbl[i][k]*tbl[i][k];
	    if (ni>0){
		int t=0;
		for (int j=0; j<512; j++){
		    double nj=0, nc=0;
		    for (int k=0; k<1024; k++){ nj += tbl[j][k]*tbl[j][k]; nc += tbl[i][k]*tbl[j][k]; }
		    if (nj>0){ if (t!=0) pw.printf(","); t=1; pw.printf("%.2f", nc/Math.sqrt(ni*nj)); }
		}
		pw.printf("\n");
	    }
	}
	pw.close();
    }
}

提出したコードからすぐ気付いた良くない個所が直してあるので、若干短くなっています。時間いっぱいまで頑張っていたので、まだまだ縮むとは思います。1KBを切りたかったのですが、これはちょっと難しいかもしれません。最初からこれぐらい割り切ったコードを書いていればよかったのかもしれませんが、Javaの速度感覚が無かったのが駄目でした。

バイトコードサイズでのゴルフはやったことがなかったのですが、なかなか楽しかったです。コードサイズは書いたままがスコアですけど、バイトコードサイズはコンパイラの気分次第で、コンパイルするまで縮むか分からないので、コンパイルが毎回どきどきです。

残り10分ぐらいの時に検証用データの最終版がもらえたのですが、なかなか手元で出力が合わなくて、うわあこれはだめぽ、みたいな状態でサブミットしたので、懇親会中は気が気ではなかったです。でも他の人たちもみんな合わないみたいなので少し安堵しつつも、やっぱり大丈夫なのかなという感じでやっぱり落ち着きませんでした。コンテスト中にあってるかどうか調べる手段は欲しいと思いました。出力がおかしくならないようにしながらコードをいじる作業が続くので、どこかでバグを入れてしまうと、どこからバグっているのか分からなくなって厳しいです。それと、スコアボードもやっぱり欲しいと思いました。周りがどれぐらい頑張っているのか分からないので、一人もくもくになってしまって、ちょっと辛かったです。あと、スコアボードがないと接戦になりにくい気がする。

そんなこんなですが、一位になれて嬉しかったです。またの機会があればぜひ参加させていただきたいと思います。チームラボの皆さまどうもありがとうございました。参加した皆さま、お疲れ様でした。