2008年04月15日

RNG -> GNC -> PFI

先日、ICPC世界大会がカナダのバンフで開催され、弊社メンバーのkzkたそとoxyたそが参加していた。チャットなどでその様子をいろいろ伝えられ、昔のことをいろいろ思い出したので、長文を書いてみることにする。書くことは、他でもない、自分自身のICPCの参加記録である。

今では、情報科学科から多数のチームが参加するようになり、最近だと批判も多いようであるが、自分が初めて参加したときは、まだ参加チームが少なく、運よく大学1年のときに、函館大会にいくことができた。自分としては、ICPCから得られたものは多いし、プログラマーの人生として、一度は本気でプログラミングで感動したり、悔しかったりすることは必ずプラスになると考えているので、批判は的外れだと思うことがおおいけれども、書くと長くなるので、それは別の機会に意見を書くことにする。ひとつ言えることは、コンピュータサイエンスをつきつめようと思うと、プログラミング能力がなかったら話にならないし、人生の2・3年間をICPCに全精力を傾けることは、正しい方向だと思う。結果、ICPCで得たプログラミング能力は、一生ものであるように思える。

大学一年生の時は、RNGというチームで、GUSさんとROPPYと参加した。とりあえずノリで国内予選に応募してみた。特にあんまり練習とかはしないで、ECCとかいう大学のコンピュータシステムで、2・3回ほど練習して国内予選に参加した。国内予選の問題は、そのころ5年分ぐらい過去問が公開されていたので、それを解いてみて、サンプルインプットが通ったらOKという感じで練習していた。

国内予選は、とりあえずノリで参加したということもあって、あんまり緊張しなかった。そのころは、自分がとけそうな問題を自分で解くというスタイルでといていたのだが、しばらくプログラミングをしていなかったこともあって、GUSさんに頼りっきりであった。途中、ECCのシステムが切断して、そのまま終わりまで復旧することがなかったので、3問といた時点で、あとさぶみっとすることができずに終わってしまったのだが、運よく、国内予選を通過することができた。とりあえずタダで函館に旅行にいけるということで、非常にうれしかった。

函館大会は、1日目は練習セッションがあったのであるが、VisualAgeC++とかいう、VisualStudioに似ているものの、なんか使いにくい開発環境で開発せざるを得ず、また、PC^2というジャッジシステムがそもそも何たるものかよくわからず、練習セッションから結構苦労した。そのころは、環境がWindowsNTであった。夜は、懇親会というものがあって、いろいろおいしいものが出た。英語で、チーム紹介をしなければならなかったのだが、僕は英語がものすごい苦手なので、GUSさんにメインで話してもらって、僕はへんてこりんなことを言っておわった。。そのあとは、函館山にのぼったのであるが、ものすごいきれいであった。北海道は初めてであったので、あまりの景色のよさにずっと感動していて、11月だったのでものすごい寒かったけれども、またいきたいとおもうぐらい、楽しかった。帰りに、バスガイドさんが、朝市で売られているイカスミアイスがおいしいよというので、ウホオー食べたす、とおもいながら、早めに就寝。

大会当日の朝は、朝5時ぐらいにおきて、一人宿をぬけだして、イカスミアイスをたべにいった。気温は氷点下10度。勢いでたべにいったので、Tシャツ一枚で出発したら、悶絶ものの寒さ。さむすぎてしにそう。でも、イカスミアイスをたべたらおいしかった。おいしかったのはいいものの、Tシャツ1枚でアイスをたべたら、氷点下10度という騒ぎではなく、風邪をひきそうになった。ごめんなさい。イカスミアイスをたべたあと、やどにもどる途中、カニをかいませんか?といわれたので買った。後日それをたべたが、ぱさぱさしていた。観光客向けのカニだったのかもしれない。残念である。

というわけで、7時ごろに宿にもどって、朝ごはんをみんなでたべて、大会に参加した。大会の問題はよく覚えていないけれども、3人でがんばってといて、3問とけた。10位タイぐらいだった気がする。あまりにも昔のことであるから、当日のことはよくおぼえていないけれども、大会おわったあとは、太鼓の演奏をきいて、カニをたべた。カニは食べ放題だったのであるが、いろいろ他のチームと話していたら、カニは1本しかのこっていなかった。ご飯はいろいろおいしかった。当日に飛行機で東京に帰った。次の日が基礎実験であったので、帰らざるをえなかった。残念。そのときは、中国のチームが一位で、なんであんな問題を全問とくことができるのか、となぞであった。壁を感じたけれども、また参加したいと思った。

大学2年のときは、ROPPYがぬけて、ちゅんさんがチームにはいって、GNCというチームになった。このころから、東大内予選が激化して、大学2年のときと3年のときは、通過することができなかった。ショボボボン。通過できなくて悔しいので、チーム練習をよくするようになった。

大学4年のときには、ほんとうに通過したかったので、練習をいっぱいするようになった。といっても、他のチームにくらべたらあまりしていなかったかもしれない。このときに新しく導入した手法として、ペアプログラミングがある。ペアプログラミングを、予選で初めて実戦してみた。かなり効果が高かった。無事国内予選を通過することができた。非常にうれしかった。1位にはなれなかったものの、2位になった。海外派遣ゲットだとおもった。マニラはとられそうだったので、台北に応募したら、台北にいけることになった。ヤターー!

このころに、OBOG会が結成されて、その練習合宿に参加できることになった。このときに、はじめて、COMBATのメンバーとであった。運命である。ぬっしーは、床にころがって物理のむずかしそうな教科書をよみ、たなかさんは、SICPを宣伝していた。ただならぬ雰囲気。たなかさんと、夜に、FPGAについて熱く語った記憶があります。京大でもCPU実験があるとか。C言語コンパイラを書いたことあるよという話もしていて、話が盛り上がった。ぜひまた会いたいとおもったら、愛媛でまた会えました。練習合宿では、1日ぐらい、1位をとれたきもするし、そうでなかったきもする。

台北までは、効果のあったペアプログラミング手法をもとに、練習を何回か重ねた。

台北は、GNC初のアジア地区大会である。台北には、大会の2日前ぐらいに現地入りした気がする。ボランティアの人に空港でひろってもらい、その夜は、いろいろ案内してもらった。とりあえず腐った豆腐がいっぱいうっていて、GUSさんとちゅんさんは、これはくさいといっていたが、僕は風邪をひいていたので、よくにおいがわからなかった。セブンイレブンは独特のにおいがした。市場みたいなところがあって、そこに、ファミコンソフトや、ぱちもののディズニーの人形などが置いてあって、大変あやしかったので、お土産にかってみた。ミッキーマウスなのに、顔が茶色かった。こういう雰囲気は嫌いではない。生もののジュースはのんじゃだめよといわれていたが、そんな些細なことはきにしなかったので飲んでみたら、案の定体調はこわれなかった。

大会前日は練習セッションである。とりあえず、席がものすごく狭かった。練習のあとは、ボランティアの人となかよくなった。今でもよくメッセンジャーをしている。お互い片言の英語で会話をしている。台北は、ご飯はとてもおいしかったように思える。

大会当日は、さすがにもう問題はよくおぼえていないけれども、一問目に、ポーカーの問題をといたきがする。ぼくが、がりごり実装系をといてみたいということでときはじめたのであるが、結構複雑で、なんとか通った。結局、5問ぐらいといておわってしまった。あんまりいい成績ではなかった。途中、ペアプログラミングしてると声がおおきくなるので、横のチームからおこられた。ごめんなさい。そして、となりのチームは、その年の世界大会で優勝したSJTUのチームであった。ふうせんがいっぱいあがっていた。これは勝てない。おわったあとは放心状態で、悔しかったものの、あんまり、そこまで悔しくはなかった気がする。

夜は、バスにのって、よくわからないアミューズメントパークみたいなところにいった。バスで2時間ぐらいのっていたような気がする。ながいながい。懇親会は、終始中国語でなされていたので、ボランティアの人が訳してくれなかったら意味がわからなかった。とりあえずよくわからなかったけれども、イベントが開催されて、ノリで前いきなよといわれて、前にいったら、腕立て伏せ勝負になって、腕がものすごい筋肉痛になった。いたいいたい。そのあとは、ゲームセンターで、ボランティアの人達もまじえて、いろいろゲームであそんだ。一回、おおあたりして、メダルみたいなものがいっぱいゲットできた。へんなマグカップをゲットしたけれどもボランティアの人にあげた。で、そのまま宿にかえって就寝。

次の日は、観光である。なんとか博物館にいったものの、だいたい工事中で、僕は書をみていた。あとはあまりよくわからなかった。その博物館の前にはぼったくりタクシーがいっぱいいるとのことなので、帰りはバスでかえった。夜は、シーザーパークとかいう高級ホテルにとまった。ひろいひろい。肉がはいったラーメンっぽいのが、とてもおいしかった。夜、地震がおきて、ドアががたがたいっていてこわかった。台湾ではあまり地震がおこらないらしく、たてものが弱いらしいので、きをつけたらよろしと電話がかかってきたけれども、たおれなくてよかった。

次の日は飛行機で東京に帰った。おみやげをいっぱい買ったら荷物が重くなった。カラスミもかってみた。

愛媛大会は、風邪をひいていた。風邪をなおすにはどうしたらよいか、と、当時QOOのコーチであったシゲトミさんにきいたら、子ども用のシロップを一気飲みするといいよと言われて、なにをいっているんだこのひとは、と思いつつ、普通の風邪ぐすりを服用した。台北とちがって、机がひろくて、そこは快適であった。大会では、5問といた記憶がある。10位だった記憶がある。もうちょっと上だったかもしれない。でもいづれにせよ世界大会県外なので、残念であった。

愛媛大会の当日のことはよく覚えていないけれども、SJTUとこのころから仲良くなった。台北のチームのコーチは、台北のときの主催大学の責任者だったので、むこうもおぼえていてくれた。愛媛城のロープウェイはおぼえている。ずっと、問題の解法について、コンバットのたなかさんと議論していた。コンバットは、このときに、世界大会出場をきめていた。うらやましい。I問題が、グラフの菜食問題っぽい問題で、全探査でとけたよ、という話をしていた気がする。

夜は、へんてこりんな宿にとまった。中島さんだったか鈴木さんだったかが見回りにくるらしくて、見回りにきたら怒られるということでいつでも寝る準備をしていたのだが、結局みまわりには来なかった。

次の日は、やきものに絵をかいて後日おくってもらうというイベントがあった。たなかさんは、ラムダなどを書いていた。僕もいろいろ書いていた。うちのチームの分は、ぼくの家におくってもらうことにしたのだが、いまだまだ全員分ぼくの家においてある。ごめんなさい。そのあとは、すぐに飛行機で東京に帰った。

大学院に入った。

国内予選は、ペアプログラミングをさらに洗練させ、1位で通過することができた。これは非常にうれしい。うちのチームは、一致団結したときのチームワークの良さは抜群である。

国内予選を通過してからは、何回も練習会を開いた。GNC練習会というイベントをひらき、毎回京都チームとも闘っていた。これはかなり効果的だった。

マニラ大会に参加できることになった。

マニラ大会は、今でも鮮明におぼえている。

まず、飛行機が、ゆれるゆれる。フィリピン航空は運転があらくて、いつ落ちるかわからないと思った。マニラについたら、その日は、とくに観光をせず、夕食をたべておわりであった。夕食は、てりやきなるものをたのんでみたら、醤油のかわりに黒砂糖がかかっていて、悶絶ものであった。僕は甘いものが苦手です。ピザは普通においしかった。宿はとても豪華で、インターネットも快適であった。アドホックネットワークをくんで、インターネットにみんなでつないでいた。去年、シロップをいっきのみするといいよという貴重なアドバイスをくださったシゲトミさんは、うちのチームのコーチになった。ホテルは豪華で、まくらが4つぐらいひとつのベッドにあって、なににつかうんだとおもいながら、一人まくらなげなどをしていた。ポカーン。

次の日は、練習セッションである。彼らは、マシンの再起動のときに、元電源をきって、つけなおすということをするらしい。アグレッシブである。問題の表記がまちがっていて、さぶみっとすらできなかった。悲しい。

次の日は、本番であった。とりあえず、開始時間は1時間以上のびていた。開始したら、問題をよんでみると、なんだか問題の仕様があいまいな問題がおおい。URLのドメインを認識してうんぬんという問題があったのだが、トップレベルドメインの仕様とかがかいてなくて、完全に想像でつくるしかなかった。焦る焦る。最初の2時間ぐらいは、相当に成績がわるかった。もう泣きそうであった。でも、そこから、ばんかいして、8問すべてとききることができた。終了40分前ぐらいである。これは、優勝したんじゃないかと思った。純粋にうれしかった。ハイパワーなガスさんがさらにハイパワーになり、ちゅんさんのグラフ能力が炸裂していた。

そのあとは方針状態で、表彰式をむかえた。そのまえに、香港のチームFATEも全問をといたということで、どきどきであった。

表彰式では、うしろから順番によばれていくのである。2位の発表になったときに、うちのチームがよばれた。え、なんで???衝撃であった。1位のチームは、香港チームであった。1位を確信していたのに、2位だったので、正直なにがなんだかわからなかった。最初のスタートダッシュが遅かったみたいだ。あまりに悔しくて、としがいもなく、おお泣きしてしまった。こんなに悔しかったのは、初めて。もう涙がとまらなくて、正直頭が動揺しすぎていた。ただ、冷静になったあとに、マニラのチームから、コングラチュレーションと言ってもらえて、2位だったものの、うれしかった。香港チームとも、お話をして、いまでは良い友達である。この年に、いっしょに世界大会にいったのである。

帰りの日は、空港のトイレで、1000円とられた。危険。

その後の東京大会では、東大内1番をとればいいとしょうじき思っていた。両側探索の問題が解けなかったものの、東大内では一番っぽいから、安心していた。ここで、IHIがもう一問といていたら、世界大会出場は危なかったかもしれない。コンバットは、あいかわらず本番につよくて、1位をとっていった。

そのあとは、大学の中を見学であるが、よく覚えていない。宿は、寒かったのを覚えている。QOOと同じ部屋でした。

とりあえず表彰式がおわって、懇親会。ここでも運命的な出会いがあった。

懇親会では、YAHOOの人がリクルーティングにきていて、わかいうちはGOOGLEにいったほうがいいよといっていたので、何をいっているんだこのひとたちは、と思いながら、飲みまくっていた。そしたら、ぬっしーが、京大の後輩のチームを紹介スルオといっていて、そこにいってみたら、ECHIZENがそこにいた。そこで、HASKELLの会のパンフレットをもらい、熱烈な歓迎をうけたが、OXYたんからはただならぬオーラが放たれていて、WAOWAOこれは来年に期待がもてます、とおもいながら、そのまま飲みすぎてしまった。COMBATと出会ったときもそうだったけれども、自分のバックグラウンドというか、自分の境遇と似ている人と会うと、なんかそういう雰囲気をかんじるのかもしれない。ちょっとはなしただけで、おうおうOXYたんはそうとう昔からコンピュータを使いこなしているなというオーラをひしひしと感じた。なので、そのころにはもうPFIの創業を決意していたのだが、後日熱烈にプッシュして、今はPFIで一緒に働いている。あのときに、よっぱらったぼくとECHIZENを出会わせてくれたぬっしーには大感謝である。ポッキーはいまでも覚えている。なんでもないです。

というわけで(どういうわけだろう)、世界大会にいけることになった。

世界大会前の合宿では、チーム崩壊の危機で、大変ピンチであった。うちのチームは、チームワークがすべてであるので、とてもあぶなかった。でも、なんとか本番までには修復したように思える。

テキサス。

初日は、時差ぼけで、せっかくリバーウォークで船にのっているのであるが、全員爆睡していた。ガイドさんごめんなさい。テキサスは、豆みたいな食事がとてもまずく、肉はそれなりにたべられて、ケーキは甘すぎて、テキーラはおいしい。たまたまはいったイタリア料理はおいしかった。

現地入りしてからも、練習をかさねた。いままで解けなかった難問セットを10台あつめて、コンテストをおこなった。日本のチームと連絡しながら、コンテストをひらいた。そのときに、どうしても解放がわからなかった問題があったが、OXYたんが解放をメールでおくってくれた。そして、同じ問題が、本番で出た。奇跡。

現地では、いろいろ不安が襲ってくるもので、チームノートブックが、白紙じゃないからやばいんじゃないか、とかで、その場で紙をかったりして、不安を払拭することに必死だった。最後のチャンスであるから、当然緊張するものであろう。エクスカーションもエクスカーションどころではなく、ただただ緊張せざるを得なかった。JAVAチャレンジなどもあったが、ぬっしーが、このじゃばチャレンジは必勝法があってツマランとおっしゃって、その場でゲームをつくっていたのが懐かしい。UPEミーティングというつまらないミーティングもあって、その場でアドホックネットワークを組んで、AJAXでチャットシステムを構築して、時間をつぶしていた。

大会当日。コンバットのメンバーとともに、会場にむかっていたが、心臓があまりにも緊張し、もうなにがなんだかわからなかった。でもとりあえず優勝カップはさわっておいた。1UPキノコのパンツ一丁のひとがいるなど、ファニーであったが、僕の心はファニーではなかった。はちきれそうでさった。

大会開始。問題がむずすぐる。。。なんだこれは。解けない。解けない。解けない。さぶみっとしてもYESが帰ってこない。周りの風船もあんまり上がらない。結果、3問で終わった。長い間のICPC人生が終わった。虚無感に襲われ、悔しさにあふれて、終わったあとに、悔しさのあまりに涙がでてきた。起業準備や未踏が重なっていたこともあり、100%を世界大会にささげられたとは言えなかったことが、その時になって初めて後悔した。チームメンバーには、申し訳ない気持ちでいっぱいであったが、ここまで、4年間一緒にこのチームで参加できて、よかった。このチームでなければ、こんなに感きわまることもなかっただろう。この3人で、ここまで本気でプログラムを組むことは最後なのかもしれないと思うと、ますます涙がこみあげてきていた。ああ、ついにおわってしまったんだなあ。

その後は、放心状態であったものの、コンバットとゆあさせんせいと両チームのコーチとともにリバーウォークで食事をたべていた。コンバットも、やはりぎりぎりで3問とおしていたので、悔しさがいっぱいであったようである。GNC練習会でも、合宿でも、いつも一緒に競い合ってきた仲であるから、もう、ここまで本気で競いあうことがないのだと思うと、寂しく思えた。

懇親会では、いろいろなチームに、たなかさんときんじょうさんと、かたっぱしから情報交換をした。楽しかった。ついでにせぐうぇぃにものれた。MITのチームメンバーは、アルマジロをずっと見つめていた。アルマジロには、プログラミングに通じるなにかがあるのかもしれない。彼は、30分ぐらいアルマジロをずーと見つめていた。SJTUのメンバーとも仲良くなれた。日本語であいさつをしてくれて、うれしかった。こちらも中国語であいさつをした。なんだかんだで、台北大会のときから、SJTUのチームともずっと一緒だった。ICPCは、国とかの違いはあんまり関係なくて、純粋にプログラマーどうし仲良くなれる場所であると強く感じた。FATEともよく話した。宿にもどったあとは、ぬっしーとGNCとFATEといっしょに、ゲームでいろいろあそんでいた。たなかさんは、写真をみつめて、感慨ぶかかった。

そのあとはしばらく放心状態。

1か月後には、会社が本格的に始動して、Sedueという製品を作った。ICPCで得られた能力の一つに、バグを入れない・バグを確実に見つけるコーディング能力・デバッグ能力がある。これは、今でも非常に役立っている。極度の緊張状態で確実にバグをとらなければならないICPCでは、常に頭の中に起こりうるバグをすべて想定してコーディングをしないとならない。そういう経験は、たとえばマルチスレッドにおけるデッドロックや、コーナーケースで起こりうるバグをすばやくとることに非常に貢献した。

あとがき。

ICPCで得られたことは非常に多いけれども、一番自分にとって大きくプラスになったのは、非常に優秀な人との出会いである。ICPCがなければ、PFIのメンバーの多くとも出会うことはなかったであろう。今では、メンバー10人中6人が世界大会に出場した経験のあるメンバーである。とくに、コンバットのメンバーとは、本気で戦いあって、一緒に世界大会に出場したこともあり、本当によかったとおもう。ECHIZENのOXYたんと出会うことができたおかげで、優秀という言葉では表せられないほどポテンシャルの高いメンバー2人とPFIで一緒に活動することができた。

先日、この2人が世界大会に出場していた。僕は、OXYたんが初めてICPCに出場したときからずっと一緒であるが、いろいろ助言をしたように思える。その助言は余計なものだったかもしれないけれども、ひとつ、ICPCに参加することの楽しさや、ICPCに全精力を傾けることが非常に価値が高いことであることは、伝えられたのではないかと思う。彼のチームは最初の年はあまり芳しくない成績ではあったものの、その後1年間では、ものすごい成績の向上をみせ、東京で行われた世界大会では、メダルには一歩及ばなかったものの、優秀な成績をのこした。とてもうれしかった。応援するのは非常にたのしかった。それと同時に、とてもうらやましかった。世界大会の舞台は非常に輝かしいもので、何百人も、これほどすぐれたプログラマーが集まる機会はそうそうない。その中に身を置く経験は、どんなにお金をかけても経験できるものではない。

GNCの2人のチームメンバーと4年間過ごせたことも、忘れられない想い出である。2人には非常に感謝している。ちゅんさんのバランス感覚というのは素晴らしいものがあって、PFIでも非常に製品開発に貢献している。GUSさんとは、5年間一緒であったが、ずばぬけたコーディングセンスは、どんなソフトウェアでも書いてしまうのではないかとさえ思わせてくれる。GUSさんは、今は就職して違う道を歩んでいるが、僕はこの3人のチームワークは最強で、あらゆることも乗り越えられると考えているので、近い将来一緒に仕事をして、新しいソフトウェアを生み出していきたい。

僕がPFIを作ったモデルとなったのも、GNCなのである。ICPCのどっかのサイトに、1かける3は4という言葉が書いてあったけれども、GNCでは、1かける3は4以上で、相当に大きいものであった。それぞれ違う能力を持ったエンジニアが、お互いの能力を補完することによって、3人ばらばらでは達成できないことも達成できるようになる。

よくできたチームであれば、コミュニケーションはコストにならないのである。コミュニケーションをとることそのものが大きく生産性を加速させて、できないことも可能にするのである。普通のチーム開発で論じられるような、2人あつまっても生産性が2倍にはならない、というような次元ではない。PFIを作るときに一番重要視したのは、これを、会社でも実現することだ。一切の妥協はしないで、小さなチームでもいいから、最大限に能力の活かせるチームを創り上げる、ということだった。コミュニケーションが価値を生まなくなってしまっては意味がない。

なんだかいろいろ書いてしまったけれども、先日、世界大会に参加しているのを見て、文章を書きたくなってしまった。世界大会を楽しんでいる後輩をみていると、自分も嬉しくなってくる。いろいろ、悔しさや後悔もあるとおもうけれども、その経験があるから、コーディングという行為そのものから、技術的なノウハウだけではなく、無限の可能性を学びとることができるのではないかと思う。嬉しければ嬉しいほど、悔しければ悔しいほど、自分が本気だったということだし、そうじゃなかったら、嘘だということになる。本気でプログラミングをできる、世界で数少ない機会の一つが、ICPCだと思う。

2007年09月22日

分類型画像検索エンジン『viim』

1週間ぐらい空いてしまいました。お酒のみすぎて、今はふらふらですwww

ちょっと、今日は、前々から出したかったサービスがついにリリースできたので、紹介します。『viim』というサービスです。

これは、分類型画像検索エンジンという、検索キーワードを入れると、それにマッチする画像をトピック別に表示する、一風かわった画像検索エンジンです。この画像検索エンジンでは、「検索結果クラスタリング」という技術を用いています。クラスタリングというのは、たくさんの文章を、意味的な集まりに分類してあげる技術のことです。もともとはうちの会社でクラスタリングの研究開発を進めている過程で、メンバーのOxyさんが新しいコンセプトでクラスタリング手法を生み出したのがきっかけです。

普通、クラスタリングというと、まず意味的な集まりに分類し、分類してから各クラスタにタグをつけるのが一般的です。しかしながら、今回のエンジンでは、まず、ありうるタグを全部抽出してから、文章をそのタグに基づいて分類してクラスタを沢山つくります。そのあとで、クラスタの大きさや交わりが適切になるようにクラスタを選んでいきます。

この手法で目指したのは、ユーザーの、クラスタリング検索への納得感をどうしても高めたかったというのがあります。検索結果を見るときに、ユーザーが検索結果を判断するには、まず結果のサマリーを見ます。今回のエンジンでは、サマリーから目立つ単語をまず抽出して、その単語をもとにクラスタを作ってあげることで、ユーザーにぱっと見てわかりやすいタグを提示することができます。そして、そのタグのクラスタを選んだときに、そのタグを含んでいるすべての結果が含まれているので、検索結果になにが含まれているのかをすぐ把握することができます。

まだまだ精度は今後向上していく必要がありますが、まず一つの形としてこのクラスタリングエンジンを世の中に出すことができて、非常に嬉しいです。画像検索結果にクラスタリング技術を応用してみるというのは、たまたま思いついたアイデアですが、実際サービスを作ってみると、いままでの画像検索では実現できなかった、大量の画像を効率的に眺めていくというのは斬新なのではないかと思います。

検索エンジンの一つの形として、クラスタリング検索はだんだんと普及してきましたが、Web検索以外にもクラスタリング技術は価値があるのだ、ということを示せれたらよいなあ、と思っています。

ちょっと裏話的なことになりますが、viimのリリースまでには、クラスタリングエンジンの完成からずいぶん時間がかかってしまいました。エンジン自体は5月ごろには完成していたのですが、「どのようにクラスタリングを応用するか」という点でまずいろいろ悩みました。サイト検索結果を分類するものは既に様々なサービスが存在するし、サイト検索をするときは、比較的検索エンジンを長い間つかっていると、目的のサイトを見つけることはそれほど難しくないので、なかなか自分たちでクラスタリングのよさを実感しにくいというのもあるのかもしれません。そこで、いろいろなコンテンツのクラスタリングを試している中で、画像検索に適用してみると、意外に面白い。

画像検索クラスタリングを社内リリースしたときは、けっこうみんなはまっていて、これは是非サービスにしたいと思っていたのですが、今度は、ユーザーインターフェイスをどうするか、という問題がありました。画像は、いろいろ眺めていると楽しいのですが、HTMLベースだと、ページ遷移があって、どうしても臨場感がでない。そこで、どうやってうまくみせるかいろいろみんなで悩んでいたのですが、8月末に開発合宿をやって、そこでぬっしーがUIをFlashで実現してくれました。開発合宿は3日間(実質48時間)しかなかったのですが、その中で、いままでのHTMLベースのUIから、かなり劇的にUIが進化して、合宿中もみんな休憩中に(休憩中じゃなくても)けっこうviimを使って遊んでいました。

そんなこんなで、ようやくサービスとしてリリースできたので、感慨もひとしおです。長い間出したかったけど実現していなかっただけに、サービスとして出せたときは、Oxyさんとぬっしーでチャットでカウントダウンとかしてました(笑)。

ちょっと長くなってしまいましたが、今日はここまで。

2007年09月15日

プログラマーに必要なこと

ひさびさの日記更新です。
いつのまにか1年ぐらい経過してます・・・
要望が多かったので、日記を書くのを再開してみることにしましたが、いかんせん飽きやすいので、更新頻度は謎です。

最近、マシン語の話がいろいろなところで取り上げられていて、思うところがいろいろあるので、釣られて書いて見ることにしました。あああ。

端的に言うと、すべてのプログラマーは、マシン語のみならず、アーキテクチャ・OS・データベースなどなど、すべての分野を、専門家レベルとは行かなくても、空でその分野について1日中は語れるぐらい詳しくなるべきだと思います。

理由は、2つです。

1つは、動作原理を知っていれば、コンピュータをいじることが楽しくなるからです。

というか、なぜ勉強しないのか、勉強しない理由はないと感じます。面白いのだから。IA32のインストラクションセットにも、他のマイクロプロセッサのインストラクションセットを読んでいても、単にアセンブラを書くために必要なだけではなく、コンピュータを理解するためのヒントが沢山含まれています。今のプロセッサのインストラクションセットは、コンピュータで様々なアプリケーションを高速に動かすためのいろいろな工夫が詰まっています。read-modify-writeの命令を知らなかったら、マルチスレッドプログラムがなんで安全に動くのかわかりません。アトミックなメモリ操作をする命令があって、その上でセマフォアやミューテックスを実現する仕組みがあって、その上にロックマネージャを実装し、並列処理を安全に動作させることができるわけです。排他的処理をどうやって実現するのか知っていれば、マルチスレッドプログラミングが分からない・難しいなんてことはなくなるでしょう。ISAを読むだけで、いろいろなことがわかって、その上にどのようなものを構成できるか考えることができるのに、その考えるプロセスを楽しまない理由はないと思います。

もう一つ、実用的なソフトウェアを作るには、きちんとした設計が必要だからです。設計がガタガタでも動いているアプリケーションはいろいろありますが、スケーラビリティーや安定性など、ソフトウェアが多く使われるようになると必然的に生じる問題には対処できません。資金と人を投入してパワーで解決するしかなくなります。きちんとした設計ができるようになるためには、先人の知恵を借りるのが一番です。もはや、分野が広くなりすぎて、自分ですべて1から作って、必要な設計技法を自分の力だけで身につけていくことは不可能です。

たとえば、システム開発に携わっているのにデータベースを知らない、という人が多すぎるように思えます。RDBMSはミッションクリティカルなアプリケーションの基盤になるソフトウェアであるからして、システムを堅牢に保ちつつパフォーマンスを向上させるための技術が沢山詰まっています。データベースを開発するわけではなくても、たとえば安定したシステムを作るためには、常にトランザクション処理を意識しなければなりません。今まで何十年もかかって築かれてきたトランザクション処理の理論を、自分で1から考えるのは、無謀といわざるをえません。ある程度まではうごくでしょうが、より完成度を高めようと思うと、壁にぶち当たります。すでに答えがあるのに、それを参照しない手はありません。

ちょっと話はそれますけど、既存の手法をきちんとサーベイすることの重要性が、あまりプログラマの間で認識されていないようにも思えます。もちろん、手をうごかすことは、とてもとても重要です。しかしながら、それと平行して、きちんとサーベイもすべきです。だいたい自分が考えた技術は、すでに実現されています。何が実現されているのかは正しく把握し、あたらしいものを生み出すために手を動かすべきです。もちろん、最初は手を動かして、そもそもイニシャルバージョンを動かすようにすることは重要ですが、そこで止まるのではなく、たとえばアドホックに対処したところをきれいに実現できないか、既存の技術で実現できないか、を見直さなければ、システムはつぎはぎの塊になってしまうのではないかと思います。

つぎはぎのシステムは、性能を出すためにマシンを増やしまくらないといけないので、環境にもよくない。電力は無視できない資源であるし、もし同じ電力なら、より多くのタスクをコンピュータにやらせたほうがよいにきまっています。

だから、私は、うちの会社で、メンバーにきちんとサーベイしてもらうことを徹底しています。たしかに時間はかかるのですけれども、その後にまっているより大きな時間消費に比べれば、小さいものです。

まあそんなわけで、私は、プログラミングするなら、コンピュータやシステムの動作原理をきちんと勉強しておくことは必須だと考えています。自分が携わる分野でプロフェッショナルな知識をもつことは必須ですが、そのほかの分野の知識も一通り知っておくべきだとおもいます。しらないと、引き出しにないので、必要になったら調べるということも不可能になってしまいます。



散文的になってしまいました。すいません。

次に、じゃあ、どうやって幅広い知識をきちんと身につけていくかってことを書きたいと思います。うちの会社で実践していることと重なりますが、参考になる部分もあると思います。

結論からいうと、違うバックグラウンドをもった人が集まって、一つの大きめのソフトウェアプロジェクトを完成させるべく、協調して開発を行うのが一番だと思っています。

中学・高校のときは、部活動でプログラミングをやっていたのですが、そのときの私の興味はオペレーティングシステムとコンパイラ、あとマイクロプロセッサでした。そのころは、8086とZ80,MIPSの資料やドラゴンブック、コンパイラ構成法とか、あとLions' Commentary on UNIXとかタネンバウムのMINIX本とか、そういうのばっかり読んでました。でも、部活動で、文化祭の展示をつくり上げていくうちに、他の人からAIの知識やCG、アルゴリズムの知識を教えてもらっていろいろ学びました。

会社では、Sedueというシステムの開発を通じて、自然言語処理、クエリプロセッシング、ネットワーク、トランザクション、分散システムといった分野をお互いが提供しあって、お互いで吸収しあっていきました。ペアプロや、ずっとスカイプつなぎっぱなしでの開発だったので、相手のやっていることを理解するために、自然と相手の知識は吸収できるわけです。

プログラミングを始めたバックグラウンドはみんな違うので、興味も違います。ただ、システムを作りあげるためには、システムに必要な要素をすべての人が知っておく必要があります。それを、一人だけで身につけるのは、なかなかめげてしまう。めげてしまうのなら、みんなでやれば、心も落ち着く。だから、うちの会社では、自分の得意分野を最大限に活かして、それを実用化する過程で、得意分野を活かすために必要だけど得意分野ではない部分を身につけていく。すくなくとも、開発メンバー全員が、自分のコードを実用化するために必要な、他の人の力を借りるべき部分を知っています。

今は、プログラミングを一緒につくるための環境は、以前よりもずっと創りやすくなっているのではないでしょうか。インターネットを通じて人を見つけることができます。昔は、でかい本屋さんにいって、片っ端から全部立ち読みするしかなかったですから。だから、同じバックグラウンドを持った人だけで固まるのではなくて、違うバックグラウンドを持った人とソフトウェアを作り上げていくことが重要なんではないかと思います。


ちょっと、久しぶりに日記を書いたので、なかなかこれが難しい。これからは、定期的に日記をかいてみていろいろ情報を発信していこうと思いますよ。かいてないと、書く速度が従来比100分の1ぐらいになります。



2006年11月07日

ICPC@Yokohama

11月4〜5と、ICPC横浜大会がありました。今年は、ヘルパーとしての参加。まあヘルパーなんですが、コーチミーティングなどにも出てきました。

とりあえず、今年の問題は個人的には難化したと思っています。まあ自分が苦手な探索問題が多く出たというのもそうなのですが、なかなか計算量の予測がつかない問題がおおく、TLEのどはまりモードにはいりがちな問題セットなのではないかと思っています。

試合後に、いろいろなチームとお話をしてみました。思ったのは、2位の越前も3位のきつねーも、もちろん1位のSJTUも、本番中には、あまりキーボードがながく停止する、という様子がみられなかったことです。かなり、うまく端末を活用できていたんではないでしょうか。SJTUにいたっては、コーダーのチェンジもものすごい高速で、切り替えがものすごい速いのを感じました。

いろいろ思うところはあるのですが、とりあえず、国内1位の越前はすばらしかった。試合中の様子を眺めていると、Gにどはまることなく、両側探索にチェンジできたことは、これは非常にすばらしいことなのではないかと。ICPCでは、本番で勝つことがすべてなので、本番ですばらしい成績を残したことはこれはすばらしいことです。直前練習会や予選で悔しい思いをしていたと思うだけに、世界大会へのいちばん重要な局面でよい成績を残せたことはすばらしい限り。ぜひ、世界大会を大いに楽しんできてもらいたいと思っています。

今回の上位チームの話を聞いていて感じたのは、やはりチームとしての戦略がうまくいっているところが上位に来たと思わざるをえません。役割分担は、チームそれぞれですが、チームとして戦えないと勝利することは難しいのではないか。ワンマンプレーやばらばらな戦略では、もう勝つことは難しいのではないかと思います。きつねーの本番での戦略を聞いていると、アルゴリズムの思考と、コーダーの分離が非常にうまくできていることを感じました。SJTUにいたっては、ここはスタイルが非常に確立されていて、さすがだなあと言わざるをえない。

今年は選手以外として参加したのですが、ちょっとまた選手として出たくて仕方ないと思った2日間でした。



2006年07月02日

チーム力強化のために(1)

今日から、何回かに分けて、GNCでの経験を踏まえた「チーム力強化のための練習」について
書いてみることにします。GNCのときに経験した、チーム力、とくにペアプログラミングの重要性に関しては、ちゃんと文章として残しておくべきだと思った次第であります。

今回は、各論に入る前に、ICPCにおいてなぜチーム力が重要なのか、ということと、チーム力強化におけるポイントを整理することにします。

・なぜチーム力が重要なのか?

ICPCにおいて重要なことは、単にプログラムを完成させるだけではなく、「時間内に」「問題を通すこと」の難しさが、プログラムを完成させることよりも難しい、ということです。「時間」の概念は特にICPCでは重要で、「のべ時間」であることはその中でも特に重要になります。つまるところ、時間に対する戦略が非常に重要になってくるわけです。端末の使用効率はいうまでもありませんが、チームの得意・不得意分野を考慮した問題のスケジューリングなど、考えなければならないことは山積みです。また、「問題を通すこと」、これもプログラムを書くことと同じく重要です。ICPCでは、ジャッジの想定した入力データを、ジャッジの想定した時間で解くことがそれすなわち問題を解くということです。入力データを想定するのも、TimeLimitを設定するのも、「コンテスタント」ではなく「ジャッジ」です。

つまり、
 ・問題を読み、解法を考えること
 ・解法をコーディングすること
と共に、
 ・チームのスケジューリングを適切に考えること
 ・ジャッジの意図を把握すること
等、多くの要素が絡んできます。勝つためには、当然のごとく、これらの要素をすべて考えなければなりません。1人で、このすべての要素をきちんと捕らえることができるのか?私は、それは不可能だと考えています。少なくとも、私は、1人でこれらをすべて捉えることができる人をみたことはありません。

それは、まったくもって問題にはなりません。なぜなら、ICPCは、3人で競技できる大会であり、また、3人で競技しなければならない大会だからです。「3人」というのは、非常に絶妙な数字で、3人だからこそ、ICPCはこれだけ長い間続いて、なおかつ、いまだ参加者が増え続けているのではないかとさえ感じます。

では、3人で戦うということはどういうことなのか、それは、「チーム」で戦う、ということです。前に述べた要素を、3人で分担し、3人ですべてを捉えきる。それが、ICPCです。完璧な人間というのは存在しないので(少なくとも私はそう思っています)、1人では絶対に何か足りない部分はあります。その部分をお互い補完し合う、ということと、それを補完しあえるだけの信頼関係、それが、「チーム力」です。

・チーム力強化におけるポイント

では、実際にチーム力強化を行っていくためには、どのようなことを行っていけばいいのか?私は、チーム力強化のためには、次の点が重要であると考えています。

 1.各メンバーのチーム内での立場の確立(お互いの特徴を理解しあう)
 2.仕事を安心して任せることのできる信頼関係の樹立
 3.共有された知識の量・質

です。

1番目の項目についてですが、まず、チーム力は、お互いの役割分担から生まれます。各メンバーがどのような得意分野を持ち、また、どこが苦手なのか、それを把握することにより、「チームで問題を解く」ということが始まります。2番目も、とても重要です。勝負の分かれ目となるのは、「いざというとき」にどう立ち向かうかです。焦りが生まれた状況下で、お互いの領分が見えにくくなる、そのときにもチーム力を発揮するためには、3人の信頼関係は必要不可欠なものになります。3番目は、チーム力を円滑に発揮していくために必要なことです。デザインパターンではないですが、チームで共有できるイディオムを多く持っておくことが重要な要素になってきます。また、それを強化する過程で、信頼関係に対しても大きく貢献することができます。


次回は、実際にチーム力がICPCの大会本番において貢献したケースをいくつか紹介します。

ICPC国内予選

金曜日に、ICPC国内予選がありました。
今年は、選手としてではなく、コーチ(XLiLTaN)として参加。
各チームの動向をハラハラしながら観戦していました。

結果の云々に関しては、他の日記でいろいろ取り上げられているので、
特に書くことはないのですが、
とりあえず言いたいことは、国内予選を通過したチームは、
ものすごく貴重なチケットを手にしたわけで、これを存分に生かすべく、国内大会まで
頑張ってほしいということ、
また、今回残念ながら通過できなかったチームは、来年に向けて今から練習を
つんでいって欲しい、ということです。

私が、ICPCにおいて最も重要だと考えていることは、ICPCはチーム力の勝負である、
ということです。個々人のポテンシャルも重要ですが、最も重要なのは、
間違いなくチーム力です。世界大会の上位チームも、3人で戦う戦略を持っています。

国内予選は、世界大会までの3つの大会の中で、チーム力の重要性を認識するよい機会であると私は思っています。3時間という短い時間の中で、簡単な問題から、それなりに難度の高い問題までを解かなければならない。ミスは致命的です。その際に、そのミッションを確実に成し遂げるためのチーム力を発揮できたチームが、上位にたつことができます。私が所属していたチームであるGNCは、4年生のときの国内予選で、ペアプログラミングの重要性を見出し、M1のときは世界大会に出場できたわけです。
とかく、コーディング力が重要視されがちなプログラミングコンテストですが、
ICPCは、そのイベント性、短時間でのべ時間が早かったチームの勝利、など、
単にコーディング力=実力とならないコンテストであると思います。
国内予選の結果に関しては、どのチームもいろいろ思うところがおおいと思います。
Makegumiは、ついに勝ち組になりましたが、直前のチーム練習の多さ、また、チーム戦略を常に模索していた姿を見ていると、この結果は納得のいくものであります。本当におめでとう。
相当混戦となった国内予選ですが、結果に満足がいかなかったチームにまず考えて欲しいのは、
国内予選で、チームとして戦うことができたか?なにが足りなかったのか?
です。それと共に、チームとして足りない部分をどう克服するか?のプランです。
もし、それに気付けたならば、国内予選での成績は、結果として大きなものを与えてくれると思います。
それは、国内予選を通過できたチームも、通過できなかったチームも同じです。
もし、通過できなくても、来年チャンスがあるのならば、1年間死ぬ気で頑張ってほしいと思います。
1年間、モチベーションを保つことは難しいかもしれません。プログラミングコンテストは、単なるコンテスト以上のものではないから、それに1年間も費やすのは無駄じゃないか、と思われるかもしれません。
しかしながら、国内予選・地区大会通過の果てになる、日本・世界の優秀なハッカーと時・場所を同じくできるということは、この上ない魅力のはずです。また、ICPCの練習によって得られるプログラミング能力は、一生の財産になります。世界大会に出ることが、プログラマーやエンジニアにとって、非常に価値のあることであるということは、保証します。



2006年06月27日

Sedue全文検索システム

今、PFIでは、Sedueという全文検索システムを開発しています。
これは、メンバーである岡野原君(http://homepage3.nifty.com/DO/)
が作成した圧縮サフィックスアレイをベースにした全文検索システムです。

圧縮サフィックスアレイを用いると、元の文章とインデックスの両方を、
元の文章量以下で格納することができます。そして、検索速度も、今一般的に
利用されているn-gram方式と同じ精度を、より高速に検索することができます。

あえて今全文検索エンジンを開発するには、いま沢山ある全文検索エンジンに対して優位性を持たねばなりません。Sedueは、この省メモリなインデックスに着目して、ほぼon-memoryでインデックスを処理できる、という特徴を持っています。コンピュータの中で最も壊れやすい部分は、間違いなくHDDです。ようは、ぐるぐる動くところ。また、HDDはランダムアクセスに弱いという欠点もあります。なので、スループットを出そうと思うと、インデックスはメモリに載せざるをえません。でも、メモリは容量あたりの単価がHDDに比べて著しく高い。なので、省メモリであるという特徴は、そこに貢献できるだろうと考えたわけです。

圧縮サフィックスアレイは、最新の研究成果なので、良い意味でも悪い意味でもかれた技術である転置ファイル(n-gramなどの方式は転置ファイル方式の1種です)に比べて、ノウハウがありません。たとえば、文章に順位をつけるランキングに関しても、圧縮サフィックスアレイでは、未だ細かいノウハウがまったくない状態です。そのギャップを埋めるのがSedueです。圧縮サフィックスアレイ向けにランキングアルゴリズムを構成し、また、より安価にメモリを拡張できるように、複数マシンを容易に利用できるための分散環境での運用、といったことがSedueの特徴になります。

また、Sedueはより多くの人にon-memoryの全文検索を有効活用して欲しいという考えから、
 ・メンテナンスを極力簡単にする
 ・全文検索に付随した機能の充実
といったことも重要視しています。
 メンテナンスの問題は、ほんとに重要で、インデックスを作るのにいちいちコマンドラインを打ったり、マシンを増やしたりしたからといって設定しなおすのは面倒です。Sedueは、システム周りの設計を、分散環境でも容易に扱えるように設計して、たとえばマシンを追加したりマシンが壊れたりしたら、それを自動検知してインデックスを張りなおすような仕組みを用意しています。「検索の速度・精度」と共に、「システムがいつでも動いている」という高可用性は、商用のシステム故にだと考えています。落ちたらファイルが調べられない、だと、思わぬチャンスを逃すこともあるので、人が側にいなくても管理ができる仕組みはこういったシステムでは必須です。
 付随した機能は、たとえば全文検索エンジンを使うためには、文章を集める仕組みが必要ですが、そういった機能もいろいろ選択肢を用意しています。たとえば、LAN内のデータをかき集めたり、Sedueにつながったクライアントマシンから簡単に文章が登録できたり。普通のファイルシステム並みにインデックスの登録を使いやすくなれば、ぽんぽん自分のファイルを詰め込んで、自分専用の検索ストレージとして使うことができます。

今は、製品リリースに向けて日々開発中です。
個人向けバージョンは無償で公開予定なので、もし興味がある方は、ぜひぜひ試して見て頂けたら、と思います。

日記

日記を再開してみました。

3月3日に、
Preferred Infrastructure(http://preferred.jp/)
という会社を設立しました。
アカデミックにスゴイ研究を実用化に向けてシステム化や、
メンバーのアイデアを集結して面白いソフトウェアを開発したり、
そんな会社になります。

会社のメンバーは、ICPCで知り合ったメンバーと、東大の情報科学科のメンバーで、
みんなすごい人達でいつも圧倒されまくり。デスマーチすら楽しくなってしまうのが
このメンバーのすごいところです。

会社では、パッケージ販売をメインにしていくので、(受託はやらない)
いまはとても貧困状態orz学生が立ち上げたからこそできる業ですね。
金銭的なバックアップはまったくないので、そこは一番大変である反面、
自分たちの理念を完全に実現できる、というのは一番重要なことだと考えています。
甘い!といわれればそうなのかもしれないが、その苦境を乗り越えられるほどの
メンバーであれば、未来は明るいのではないか、と。ソフトウェアは、
1台のラップトップがあれば、なんでも作れるし。

自分の中では、社会にでてある程度余裕ができてから、という選択肢も
無いことは無かったですが、ICPCっていう、日本・世界の同世代の
トップレベルプログラマーが集う大会に出ることができて、
また、今の学科で自分の思う最も優秀な人達と起業できるチャンスってのは、
もしかしたらもうこないかもしれない。
そう考えると、社会にでて安定するまで待っていられなかったです。
恐らく大きな壁にぶち当たることは何度もあるだろうけど、
それを克服できるぐらいでないと、大きいことはできないと思うので。

そんなこんなで、製品リリースに向けて、コーディングの毎日です。

Recent Comments
Profile
nvaca
アクセスカウンター