Hatena::ブログ(Diary)

純粋関数型雑記帳 このページをアンテナに追加 RSSフィード Twitter

このページはHaskellを愛でるページです。
日刊形式でHaskellなどについての記事をだらだらと掲載しとります。
2004 | 07 | 08 | 09 | 10 | 11 | 12 |
2005 | 01 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2006 | 01 | 02 | 03 | 04 | 06 | 07 | 08 | 09 | 11 |
2007 | 03 | 04 | 05 | 07 | 08 | 09 | 12 |
2008 | 02 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2009 | 03 | 05 | 06 | 09 | 10 | 11 | 12 |
2010 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 12 |
2011 | 01 | 02 | 05 |
本体サイト

2010年03月30日(火) チームラボ天下一武道会

[]チームラボ天下一武道会 チームラボ天下一武道会を含むブックマーク チームラボ天下一武道会のブックマークコメント

チームラボ天下一武道会 ?コードGolf & F1レース!? : ATND

に参加してきました。普段Java使っていないのでどうなるかと思いましたが、なんとか優勝することができました。

f:id:tanakh:20100329103241j:image:w320

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

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

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

トラックバック - http://d.hatena.ne.jp/tanakh/20100330

2010年03月29日(月) JOI 春合宿の講義資料

[]JOI 春合宿講義資料 JOI 春合宿の講義資料を含むブックマーク JOI 春合宿の講義資料のブックマークコメント

id:iwiwi さんからご紹介に与りまして、JOI春合宿にて講義をさせて頂きました。テーマはなんでも良いとのことでしたので、関数プログラミング入門ということで話させて頂きました。スライドを以下に公開しております。

聴いて頂いた皆さま、拙い講義ではありましたが、どうもありがとうございました。二時間も頂けるとのことだったので、あれもこれも話したいとなって、まとまりのない発表になってしまった感が否めませんが、少しでも関数プログラミングの魅力が伝われば幸いです。関数プログラミング入門ということで、関数プログラミングを全く知らない人をターゲットに作りましたが、少々無理があったかもしれません。私はネルー値が1を切らないとなかなか準備に取り掛かれなくて、当日は準備不足で資料のミスも目立ったし、資料の退屈さを紛らわすために適当に突っ込んだネタ画像も唐突過ぎていけない(その辺は大分修正しました。余計ひどくなっているかもしれませんが)。

とまあ、反省はこのぐらいにしまして、内容は関数プログラミングの基礎から並行プログラミングの話まで、なるべく関数プログラミングがおいしく見えるところをかいつまんで説明してあります。嘘も方便も多かろうと思いますが、識者の方は大目に見てやって下さい。こういうのは宗教論争だと言われたりもしますので(私は学術論争だと思っているのですが)、まさに布教でして、ならばこれは宗教の勧誘と変わらないわけでして、私の言うことを全面的には信用しないようにと念を押してはおきました。

で、内容の話ですね。いやあ、退屈な資料ですね。キャッチーな資料の作り方を誰か教えてください。まず、パワーポイントデフォルトテーマ、これがいけない。白地にゴチック体、淡々と並べられるitemize。作り方が分からないので、アニメーションも一切なし、PDFに変換しても完全版が楽しめるという親切設計。うえうえ、3分で眠れる自信がありますよ!最近流行りといったらあれです、高橋メソッド。巨大な文字のインパクト。次々めくられるスライドによる圧倒的なスピード感。聴衆も話者の巧みなキーボード操作から目が離せない!?って、そうじゃないよ。古いよ。なんでなの、これ。高橋メソッドにしたらページ数1000超えるよ!誰かほんとにクールスライドの作り方教えてください。

それで、内容の話ですね。うーん、内容はスライド観てください。

nushionushio 2010/03/30 23:25 僕はデフォルトテーマが一番伝わりやすくてよい、と思ってます。アニメとかあるのもよくない。未完成のスライドを出す事になるから伝わりにくくなる。PDFに変換しても完全版が楽しめるのこそ理想。・・・まあキャッチーなスライド、ってことは伝わりやすいスライドとは違うものを求めてるのかな。

↑真面目になってしまいましたが、1つ、聞いたことのある話は、人間10分もすると飽きると。だから10分ごと位にはネタや笑いや実験や動画や萌えやAAやコピペを挟むといいそうですよ!しかもちゃっかり話の筋とからんでるのがベスト。「コードの90%が無くなる」「な、何を(ry」なんかとてもよかったです!!

tanakhtanakh 2010/03/31 01:27 なるほどなあ。伝わりやすいというのはあんまり考えてなかったです。ただなんとなく、他の人のスライドを見てみると、タイトルでおお、とかなったり、レイアウトとかアニメーションが工夫されていたりして、随所に飽きさせない工夫が施されているように見えるのですね。でもよく考えると、伝わりやすいって方が重要かもしれないですね。資料が分かりやすいかどうか、内容が面白いかどうかってのは、デザインやアニメじゃないですからね。私は営業をしているわけではなかったのです…。

飽きさせないというのはやっぱり重要ですけど、AAやネタを挟むとよいというのは参考になりました。この辺はもう退屈な資料を紛らわせなきゃなあってので、本当はこういうのはなくてもいいようにしたいなあと思いながら作ってたんですけど、効果的な手法なんですね。これからは自信を持ってネタを挿入していこうと思います。

トラックバック - http://d.hatena.ne.jp/tanakh/20100329

2010年03月26日(金) wafのユニットテストモジュールの改良

[]wafのユニットテストモジュールの改良 wafのユニットテストモジュールの改良を含むブックマーク wafのユニットテストモジュールの改良のブックマークコメント

前回wafの紹介記事を書きましたが、あれからいくつかバージョンアップがあって、それに伴ってユニットテストモジュール仕様が結構変わりました。変わったといいますか、かなり改悪されたように思います。

ちょっとこのまま使っていくには厳しい状況です。それに加えて、ユニットテストコンパイル・実行しないというオプションがかねてから欲しいと思っていたので(ユニットテストライブラリがない環境でもインストールはできて欲しいものです)、これを機に自作することにしました。拡張しやすいこともwafのメリットなので、作業はとてもスムーズに進みました。

http://github.com/tanakh/waf-unittest

というわけで、作ったものをgithub公開しました

waf組み込みユニットテストモジュールとの違いは、

などです。詳しくはgithubのREADMEをご覧ください。

トラックバック - http://d.hatena.ne.jp/tanakh/20100326
Connection: close