チームラボ天下一武道会

チームラボ天下一武道会 〜コードGolf & F1レース！〜に行ってきました。
当日行ってみたら日比野さんがいてびっくりした。

ユーザーIDと商品IDの並んだ1万件のデータに対してコサイン類似度(商品ベクトルの内積)をいかに短いコードで高速に求めるかという問題でした。
処理時間とclassファイルサイズに上限と下限が設定されていて、それぞれ線形に0点〜50点を計算して合計点が高かい人が勝ちというルール。(上限超えると最大10点ずつのボーナス)。
Pentium4で10秒で満点の50点なんだけど特にチューンの必要も無く5秒以下になってたので基本ゴルフ勝負になってた。

結果3位だったんだけど、高得点だけど浮動小数点の丸めに影響されててランク外になってた人もいて不完全燃焼気味。

次回もあるらしいので行けたらいいな。

下のようなコードで2kちょいだったんだけど、優勝のtanakhさんのコードサイズが自分の半分くらい。クラスライブラリは使わないように実行時間は富豪的にいくべきだったらしい。だいぶ方向性を間違ってた。

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.File;
import java.io.FileReader;
import java.io.FileWriter;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Scanner;
import java.util.Vector;


public class cosine {
	/**
	 * @param args
	 */
	public static void main(String[] args) throws Exception {
		Vector<Integer[]> data = new Vector<Integer[]>();
//		TreeSet<Integer> itemSet = new TreeSet<Integer>();
//		TreeSet<Integer> userSet = new TreeSet<Integer>();
		ArrayList<Integer> items = new ArrayList<Integer>();
		ArrayList<Integer> users = new ArrayList<Integer>();

		BufferedReader r = new BufferedReader(new FileReader(args[0]));
		String line = r.readLine();
		
		while ((line = r.readLine()) != null) {
			String[] l = line.split(",");
			int uid = Integer.parseInt(l[0]);
			Integer uid = Integer.valueOf(l[0]);
			Integer itemid = Integer.valueOf(l[1]);
			if (Collections.binarySearch(users, uid) < 0) {
				users.add(uid);
				Collections.sort(users);
			}
			if (Collections.binarySearch(items, itemid) < 0) {
				items.add(itemid);
				Collections.sort(items);
			}
			data.add(new Integer[]{uid, itemid});
		}
		
		int itemNum = items.size();
		int userNum = users.size();

//		Vector<Integer> items = new Vector<Integer>(itemSet); 
//		Collections.sort(items);
//		Vector<Integer> users = new Vector<Integer>(userSet); 
//		Collections.sort(users);
		
		int[][] inputMat = new int[itemNum][userNum];

		for (int i = 0; i < data.size(); i++) {
			Integer[] d = data.get(i); 
			int user = Collections.binarySearch(users, d[0]);
			int item = Collections.binarySearch(items, d[1]);
			inputMat[item][user]++;
		}

		double[] len = new double[itemNum];
		double[][] res = new double[itemNum][itemNum];

		for (int i = 0; i < itemNum; i++) {
			int[] vec0 = inputMat[i];
			int sum = 0;
			for (int n = 0; n < userNum; n++) {
				sum += vec0[n] * vec0[n];
			}
			len[i] = Math.sqrt(sum);
			res[i][i] = 1.0;
			for (int j = 0; j < i; j++) {
				int[] vec1 = inputMat[j];
				int d = 0;
				for (int n = 0; n < userNum; n++) {
					d += vec0[n] * vec1[n];
				}
				res[j][i] = res[i][j] = d / (len[i] * len[j]);
			}
		}
		BufferedWriter out = new BufferedWriter(new FileWriter("output.csv"));
		for (int i = 0; i < itemNum; i++) {
			for (int j = 0; j < itemNum; j++) {
				if (j != 0)
					out.write(",");
				out.write(String.format("%1.2f", res[i][j]));
			}
			out.newLine();
		}
		out.close();
	}
}