ICFP の話をしゃべってきた。

当日使ったスライドは http://mayah.jp/resources/2010/OCaml-UserMeeting-2010.pdf においてあります。

以下いろいろ感想など。

名古屋

マウンテンに行って以来。名古屋弁は思ったほどは聞こえてこなかった。もっとみんな名古屋弁を話しているものだと...。

F# のはなし

F# は昔使って以来触っていなかったのだけど、そのときから .NET の世界のものを使おうとするとなんか残念で、ぬるぽとか平気で出るし、あんまりうれしさがわかってない。MS が出したということには意味があると思う。

今回の発表聞いてもあんまり変わってない感じ。

OCaml 3.12 の第一級モジュール

これは昔からずっと待ち望んでいた機能で、これでいろんなものが簡単に書けるようになりそうだなーと。

Garrigue 先生の話は要復習。

デザインレシピ

教育的なお話で、top down にプログラミングをすすめるといいですよー、と。insertion sort の話をされていて、ins_sort を作るとき、まずコメントをかいて型を書いて、テストを書いて、それから本体を書き始めると良いですよ、と。わりと自分も同じように教えていると思うが、参考になった。

spot your white caml

ocamlspotter を作った話で、こういうのを俺自身が作っていけるようにしないといけませんねと思った。

ICFP

これは自分の発表で、今年の ICFP で書いたソースがひどいことになっているという話をした。詳細は pdf を見てください。

golf

なんかコード見ると素直なコードが縮んだ感じでしたね...。let (^) = List.map はちょっと基礎ゴルフ力的に思いつくのは厳しそうだった。golf もやらないといけないような気がする。

C78 の制作もいよいよ佳境に入ってきた。ブースは二日目土曜日(14日)東ア53a。お誕生日席らしい。

しかし、残念ながら実家の都合で現場には参加できない。ただ、としさんとかが売り子してくれるので全部彼におまかせです。

頒布物は例によって ICPC 2009-2010 本が１つ。あと関数型系の本がもう１冊。後者は pi8027 さんが書いてくれた Haskell の記事と、ICFP-PC のまとめになる予定。サークルカットとかは YUHA の方を見てください。

ただいま表紙のレイアウト中...。

Cassandra 勉強会 #9 というのでしゃべっていたのだが、全く書いていなかった。

資料はこちら。

正直 Cassandra はまだ不安定で実運用を行うのは結構つらい感じがするのだけど、構成はほかの DB よりもかなり好きなのでもうちょっとおいかけていたい。

いや、別の意味で死んでるかもしれないけど...。

８問解いて７位 だった。最近のコンテストの中ではかなりうまくいった方だったが、うまくいって７位というのもなかなか精進が必要だと思うのである。というかトップ層は８問を２時間で処理しているというのがなんとも...。私は２時間では６問しか処理できてないし、２問分はあってないような問題だからなあ...。

去年は６問で２２位だったので今年８問７位というのは悪くない数字ではある。

問題一覧はこちら。

問題の感想などを簡単にまとめて書いてみる。

A 期末試験！

やるだけ。けいおん！　が元ネタだったらしいが実は気がついてなかった。２分で処理してたらしい。

B 宝くじチェッカー

これもやるだけ。これは４分。

C コンパイル

まさかのぷよぷよ。盤面が与えられるのでそれが何連鎖を行うかを求める。やるだけだが、ちょっとずつ分けて書くと楽。そんぐらい。

D 無矛盾な単位系

ぱっと見どうしようか分からなかったが、グラフ作って Floyd みたいなものを適用。決まってないところは決める、決まっているところは矛盾がないかチェックする、という風にした。証明はしてないが DFS やってるのと本質的に同じなのでよいはず。

E トーマス・ライトの憂鬱

ロックマンのパスワードが元ネタ。縦横での○の数が与えられるので、一意に復元できるかどうかチェックせよという問題だが、色々試していると一意に復元できるのは稀であるので、greedy に決められるだけ決めて最後まで決まったらよかろうと思ってやったら通った。

F UTF-8

DP であることはすぐに分かった。それ以降がめんどくさい問題だったが、check("10yxxxxxx", str, xs, ys) みたいな関数を作って、'x', 'y' に対応する文字を vector<char> xs, ys に挿入し、str と "10yxxxxxx" が矛盾してたら false を返す、というようにするとわりと、面倒くさい部分が易しく書けた。

G 天体観測

元ネタが星空のメモリアというものらしい。知らん。解いている最中は勝手に宙のまにまにが元ネタであるということにしておいた。

３次元座標を X, Y, Z 軸で回転するオペレータをウェブで調べて写して、後はそれを組み合わせて座標変換するだけだった。やや苦戦した。

H 迷い猫、走った

元ネタは迷い猫オーバーランか。名前しか知らないので特に何も味わうこともなく問題へ。

最大値を最小化する、という２分探索でやってくださいという典型問題だったので２分探索することに。まず、全部にエサをぶちまけてみると、確率的には一番分散するはず。これで n 以上猫が集まっている場合、そこにエサを置くと n 匹以上猫がいることが確定するので、エサをおかないようにする。それで状態を update して、n 匹以上猫がいるところがなくなくまでエサをとりあげつづける。５回も WA した。コードがバグりまくっていたが、なんとか直して通った。

I 盗まれた宝石

これ以降は通してない。履歴をうまいこと覚えて BFS なのはすぐ分かる。かなりうまいこと覚えないと MLE する。

J 多項式の解の個数

うーん、わかんね。解説聞いても ustream では式が追えなかったので解説スライド待ち。

K ワープホール

これ意外と戦えたんじゃないかなあ。二人通してたしと今では思う。

L ３つのシルエット

きつい３次元幾何という感じで、モンテカルロでもなげてやろうかと思ったけど思うだけでやめた。モンテカルロは想定誤解答だったらしい。まあ、そりゃそうか。

営業をしたいわけではないのだが、自分の能力を発揮する場を作り出すという意味において、最近営業的能力があることは重要な気がしてきている。

基本的にはお客様が何をして欲しいのかという真のニーズ・隠れたニーズを引き出しそれを提案するというさんざん聞いてきた事が書かれてある、これが難しいことは良く理解している。

読んでは見たが、特に読まなくても良かったというような本。

ハルヒシリーズを全部読もうと決めてこれで全部読み終わった。いわゆるライトノベルを読んだのは何年ぶりか分からない。中学校の頃にスレイヤーズを出ているだけ全部読んだ記憶がある。他のはちょっとつまみぐいしたぐらい。高校に入っても惰性で少し読んでたが、大学に入ってからはご無沙汰だったのでおよそ１０年ぶり、というところだろうか。中学生の頃はライトノベルとはいえ「読む」という行為そのものが馬鹿に出来なくて、読み始めてから数ヶ月で国語の成績がやけに上がった。さっぱり書けなかった漢字が何で覚えられなかったのか分からないぐらいに書けるようになったのを覚えている。国語の成績があがらない人は問題集をやるよりとりあえず本を読んでみると良い。ただマーク試験の成績はさっぱりだったが (偏差値でいうと記述 70 とマーク 55 みたいな感じだった)、あれはあれでやり方があるというのはそういう試験を受ける必要がなくなってから気づいたことだった。

ハルヒシリーズ読んでて感じたのだが、なんかコイツ Steve Jobs みたいじゃね？　人の意見聞かないところとかとりあえず一番出来る人をだしなさいなところとか。現実歪曲空間とか。こういうのが痛快ということなんだろうか？　明日からマネしていこう。

あと、坊っちゃん。松山を非常にバカにした話である。これで町おこしをしようと思った人たちもなんだかなあと思った。松山出身ではないのだが、多分松山でなければもっと楽しめた。話は大衆的でおもしろいことはおもしろい。

この５冊は全部 iPad の i文庫HD で (いわゆる自炊をして) 読んだのだが、通読する分には十分読める。ただし、あるページを探そうなどと思うと紙の本でパラパラ探す方が簡単だ。この点だけはいただけない。後数年もすれば iPad の様なデバイスでもパラパラめくるのよりも高速に本の内容を俯瞰出来るになるだろう。なってほしい。

18日金曜日から21日月曜日まで、ICFP Programming Contest 2010 に参加。

今回は初めは俺言語で出るために一人で出ていたのだが、途中でチーム Oh!tomaton に
合流した。チーム Oh!tomaton は、tsukuno, kinaba, mayah の３人。順位は２７位のようだ。二人のブログは、d.y.d. となんとなくな日々のコメントにある。

あと、俺言語で出るという目標を掲げていたが、一応一人の時は使っていた。機能は絶対的に足りないので OCaml と ruby も併用していたが...。３人になってからは OCaml, ruby, C++, Java, D あたりが使われていた。tsukuno は PHP も使っていたらしい。

はじめ

とりあえず問題を 15 分ぐらい書けて読む。

今回のタスクは、お金を稼ぐこと！　らしい。どうやってお金を稼ぐかというと「車」に対して「燃料」を供給することで利益をえることができるということのようだ。ふむ。

「車」とは、複数の chamber を持ち、各 chamber は upper と lower の２本の pipe からなり、pipe は複数の section の列からなる。各 section は燃料タンクに繋がれている。燃料タンクは最大で６つである。「車」は ternary stream (３進数ストリーム) でエンコードされているので、どのような「車」かは自分で decode しなければならない。また、「車」がどのように encode されているかは推測しなければならないし、ternary stream の仕様も自分で推測しなければならない。他にも色々細かい規則がある。推測多いな...。

「燃料」は、「車」によって次のように使われる。

out(k) = c(n, 1)in(1) + c(n, 2)in(2) + ... + c(n, k) in(k)

まだなんのことか分からない。

「燃料」が「車」に合うとは、全ての chamber で、upper pipe と lower pipe に同じ空気を送り込んだ場合に、upper の方が lower より大きくなる(一部の pipe に関しては等しくてもかまわない)ことを言う。まだ何のことか分からない。

「燃料」は「工場」によって作られる。「工場」はゲートを組み合わせたもので、ternary stream を入力にするとなんらかの ternary stream を出力する。ゲートは２入力２出力で、工場は１つの外部出力と外部入力を持つ。工場のフォーマットも推測しなければならない。また推測...。

１日目

とりあえず、まずなんとかできそうなのがゲートを推測することぐらいなので、工場を適当に造って推測する。工場のフォーマットはちょっと考えればすぐ分かるようになっている。工場の外部入力がそもそも分からないので推測がしにくい。

試していると

X:
:
X

という工場が通ることが分かった。これは入力をそのまま出力に出すものなので、これで入力が判明する。

次に、

  i
  | |
 +---+
 |   |
 +---+
  | |
  a b

この外部出力を a, b とつなぐととりあえず値が出るので、

  i
  | |
 +---+
 |   |
 +---+
  | |
 +---+
 |   |
 +---+
  | |
  X

とすることで、入力が分かっている状態で左の出力と右の出力が外部出力につなげるので、という感じでゲートの推測をしていく。

次に、しばらくたって燃料は prefix をもたなければならないというのをとばし読みしていたことに気がつく。しかしこの辺で推測大会でやる気なくなってきた。

というか、ここまでだとまともなプログラミングがない。一応俺言語でゲートの推測とかしていた。

１日目夜 oh!tomaton に合流

一人でやるのがつらかったので oh!tomaton に合流。ternary encoding の仕様を探る。kinaba タソが整数の encoding の初めの方を見つけたので、試しているとだんだん分かってくる。list は絶対 empty list で最後終わると信じて読もうとしていたのだが、そんなことはなくリストの数が先に来る encoding だった。

２日目

この辺で ternary encoding を encode/decode するプログラムを作った。

それでようやっと問題の本質が分かってくる。問題を例を挙げて説明すると

1. pipe は 燃料 [0] から [5] の列である。
2. 燃料とは、正方行列である。何次元かは分からない。
3. 空気とはベクトル v である。
4. 空気を pipe に通すと、燃料の行列を乗算したものになる。
5. upper と lower に任意のベクトル v をかけたとき、全要素が upper の方が大きく(もしくは等しく)なるように、燃料 [0] から [5] を推測して定める。

となる。あとは、燃料は提出するときに ternary encoding で encode しなければならない。この形式も推測しなければならない。また、実際に提出するのは、それを出力するような工場である。

所望の ternary encoding を作る工場を生成するプログラムは kinaba たそにまかせた。あと ruby で CUI から submit するものとか、車のリストを取ってくるモノとかも２日目が始まるまでに作られた。

燃料の行列を求める方法がさっぱり分からないので、焼き鈍し法で探索でもするかということに。焼きなまし法 ライブラリでググって出てきた nodchip さんのテンプレートを使って書いた。とりあえず１次元から始めて７次元ぐらいまで試すものを書いた。

まず、行列をランダム生成。(左辺) > (右辺) を満たさない場合は (左辺) - (右辺) の絶対値をエネルギーにする。適当に行列の値を動かしてみて、エネルギーが下がる方向にすすむようにする。10 秒ほど試して、一番良いモノを採用する。

という感じでやっていたら、なんか知らんけどいくつかが解けるようになる。これで解けないのは tsukuno が人手で解くという感じのことをやっていた。

この辺で、車の仕様を受け取ると、デコード、焼きなまし、回路生成、サブミットを自動化するものを書いた。回路生成は kinaba と tsukuno になげっぱなし。

あとは必死にやきなまし法の改良を重ねていた。

２日目も終わる頃、車はそろそろ作らないとヤバイだろうという話になったので、kinaba タソにまかせる。アイデアだけとりあえず適当にだした。３次元で行列を５つランダム生成して、適当に大量に生成した不等式で満たされるモノを列挙し、残り１つの行列を１０次元にして、今までのを満たさない不等式の中から、不等式を満たすようになるように項を決めてみるとかいうもの。今までの不等式は行列の区分けをしてしまえば、左上３次元だけ要素を持つような１０次元正方行列になるので満たせる。また新しいものは満たすように作ったので満たせる。しかし、大きいのを送るとエラーになるらしい。実際は５次元ぐらいでランダム生成して送っていたらしい。

３日目

何をやったらいいのか分からない。とりあえず、solver で解けないものを眺めていると [4][5] を大量にかけまくっているものとかがあったので、[4] や [5] をとりあえず I だと思って焼きなましてみるとか、そういう個別対応をやっていた。全体的に人手が足りない。

あとはやきなましソルバーをずっと回していた。

残り何時間かで突然 tsukuno が回路ゴルフを始める。kinaba ソルバーは任意の n 個を出すのに 24 + 3n かかっていたが、1.66n + α ぐらいで出せるようになる。このソルバーで全部再サブミット。自動ソルバーもそっちに。

残り２時間ぐらい、もうなにをやっていいのか分からずあきらめムード。

で、タイムアップ。

感想

最初の推測大会いらないと思う。プログラミングせずに投げてしまった人も多かったのではないかという印象。最近スタートラインが全体的に遠い。

行列が解けるようになってきてからは結構おもしろいと思えるようになってきた。

来年以降はもっと最初の敷居を低くすべきだと思う。その点、昔の ICFP Programming Contest で出た、とりあえず VM の仕様が与えられるので実装せよとかいうのは良いのではないかという印象。

最近わけあって Cassandra を追いかけている。というのも、作ろうと思っていたモノが結構実装されていて、足りないと思っている部分も 0.8 までには実装されそうだからだ。自分で作るよりは十分によいモノがあるのであればそれを使った方がよいし、ちょっと足りないぐらいなら自分で commit してしまえば良い。

Cassandra は NoSQL (Not only SQL) 型のデータベースの一種で、書き込みが高速であることで知られている。twitter や digg などがサービスのインフラとして導入しており、それだけの大規模でもきちんと使えばスケールする。

Cassandra の良い点は single point of failure (単一障害点) がないこと、すなわち、どこか１つのサーバーが落ちてもシステム全体が応答しなくなるというようなことがないことだ。これはサービスレベルを高く維持するには必要なことであり、これを持ってない DB で同じ事をやろうとすると非常に高く付くか実装できない。余談だが、Cassandra と比較されることが多い HBase は 単一障害点を抱えている。

Cassandra は他の NoSQL DB 同様、CAP 定理の C を犠牲にしている。CAP 定理とは、Consistency, Availability, Partition tolerance の３つを同時に達成することは出来ないという定理だ。RDB はこのうち C を重視し P を犠牲にしてきたが、NoSQL は C を犠牲に A, P を重視するようになっている。これはそうしないと大量のリクエストを捌くことが出来ないからである。

Cassandra では、速度を犠牲にすることによって、実は C をいくらか稼ぐこともできるようになっている。Cassandra では、あるデータのレプリカを複数のノードに取る。このノード数を N とする。一般的には N = 3 で運用することが多い。このとき、次の条件が満たされれば古いデータが読まれないことが保証される。すなわち、read するときは R 個のノードから読み出して最も新しいものを返し、write する場合は W 個のノードに書き込まれたことを保証してから返るとするとき、R + W > N が成立する。

ただし、これでも RDB 程の Consistency は確保できない。基本的にロックなどは可能な限り取らない用になっているので、外部参照張ってその一貫性を取るとか、そういうのは苦手だ。どうしても必要であれば、おとなしく RDB を使うか、あるいはそれに頼らないように application を書き換えた方が良い。

さて、話を戻す。今自分が Cassandra で欲しいのは検索機能だ。どうしても key 以外で検索しなければならないことがある。バッドノウハウ的な対応策 (たとえば、検索したい値を key にして id を引けるような column family を作っておき、id をひいてから実データを取る。ただしこの場合やりようによっては inconsistency が発生する) はいくつかあるのだが、そうするよりも DB 側でサポートしてくれても良いだろう。index は 0.8 でサポートされる予定らしいので、そのあたりが発表されるまでには完全に内部構造を理解しておき、自由に操れるようになっておく必要がある。

最近 Cassandra のソースをけっこうきっちり読んでいるので、その辺もちょっとずつ書いていきたい。

長い間ブログが開いてしまったが、実は実家に不幸があるなどして忙しい状態が続いてしまったのが原因だった (TOEIC も受け損ねた)。もう通常営業になっているので、これからは普通に更新できるだろう。