日々の流転

λ. ICFP Programming Contest 2007 (4)

なんか、諦めがつかなかったので、午後半休を取得してもう少し足掻く。 見込みもないのにこんな事の為に休むなんて、自分でもどうかしてると思うが。

昨日も書いたけど、DNA→RNA のruby版は文字列の連結(とGC)がボトルネックなのが明らかで、それをどうしようかと悩んでいた。

Rubyの文字列の連結は O(n) であり、そりゃこれだけ長大なデータの連結が大量に発生すれば重くなる。 昨日はこの問題を解決するために「文字列を単一のStringで表現する代わりに、チャンクの配列で表現して……」というのをアドホックにやろうとして、バグってやる気をなくしてたのだった。 文字列の表現を変えると Regexp なんかもそのまま適用できなくなるし、面倒くさいことこの上ない。 どうでも良いが、高速に連結可能な文字列実装すら標準ライブラリに存在しないのに、「テキスト処理関係の能力などに優れ」(「Rubyとは」)というのは何だか微妙な気がしないでもない。

流石にアドホックにやっててもなぁと思い、ちゃんとしたデータ構造を使おうと思ったのだけど、Rubyでデータ構造を書くのは面倒くさいので、とりあえずHaskellで。

最初は Purely Functional Data Structures に載っている O(1) で連結可能なデータ構造 Catenable List を実装しようとした。 で、Catenable List の実装にはキューを使うのだが、Data.Queue を使おうとしたら、「Warning: Module `Data.Queue' is deprecated: Use Data.Sequence instead: it's faster and has more operations」とか言われてしまった。 「そういや Sequence なんてのもあったな」と思って調べてみると、こいつの連結コストは O(log(min(n,m))) 。Catenable List の O(1) よりは重そうだけど、「既にある」というのは手軽なのでまずはこっちを試してみることに。

丁度、nobsun の ByteString 版のコードがあって、ByteString と Sequence はインターフェースがほぼ同じなので適当に書き換える。findSubstring だけは Sequence 側に近いコードが無かったので適当にでっち上げた(BM法すらちゃんと知らない*1ので本当に適当。なお、このコードには性能上の問題があった)。 最初少しバグっていたけど、すぐに直った。 こいつに endo.dna を食わせると1分くらいでRNAの生成が完了した。 使用メモリが心配だったのだけど、たったの150MBくらいだった。 おお、Haskellすげー。 こんなことなら私も最初からHaskellで書いていればよかった。 nobsunは正しかったよ。

で、生成されたRNAをまた描画プログラムにかけてもらった*2ら、なんか変なモアレっぽい画像が。 source.pngの画像か、もしくは何か描画ルーチンを探すのに役立ちそうなものが出てくるかと思ったのに……　ここでまた詰まってやる気を無くす。

でもまあ、これが本当に正しい描画結果かどうか分からないしな。それを確かめるためにも自分の環境で描画プログラムが動かないと不便なので、描画プログラムのソースコードをだらだらと追いかける。 そんなことをしているうちに時間切れ。

ちょうど時間切れ後に、単に入力のRNAの与え方が違っていただけということに気付く。アホ過ぎだ、こんなことに一日悩んでいたのかよ。 さらに、それより少し前に描画プログラムの修正版が出来ていたようで、修正版に食わせたら今度こそ source.png の画像が出てきた。 さらに、他の方が描画途中に最初のヒントが現れている事に気づく。 ……本当に、丁度入り口付近に辿りついたところで終了という感じ。

しかしまあ、全然歯は立たなかったけど、とても楽しかった。 AyaCFPのみなさん、そして誘ってくれたnobsun、本当にありがとう!

Random-access list?

<URL:http://shuns.sakura.ne.jp/?%BD%B5%B5%AD> の 2007-7-23 「ICFP contest(not ICFP)」に、「dna2rnaの実装についてですが、関数型なら個人的に最もエレガントな解法、というか自分ならこれで書くかなと思ったのは Random-access listかFinger-treesで」と書いてあるが、この Random-access list は catenable list か何かの間違いではないだろうか。Random-access list は連結も部分文字列取り出しも特に速くないはずなので。