2001-07-23
λ. 「記号処理プログラミング」の試験は失敗。時間配分間違えた。でも、それほどひどい点数って事は無いと思うから、まあ良しとしよう。そして、残るは難関の「経済理論演習」。ミクロは大体オッケーで、マクロも基本的な所はなんとか押さえた。でも、これだけじゃ、問題解けないんだよー(泣)
λ. uses
$"があっても、initializationやfinalization等に適切な順序を定義できなければ意味が無いと思う。まあ、順序に依存しない場合はもっと善きに計らって欲しいものだけど。
λ. 昼
学食で、冷やしタヌキうどん、かばちゃの煮物、あとあれはフランクポテトでいいんだっけ?。
λ. 経済理論演習のテスト
失敗しました。ええ、失敗しましたよ。時間無さ過ぎ。小澤先生は「時間があっても、解けない問題は解けない。」とか言ってましたが、時間がもうちょっとあったら相当違ったね。
λ. まあ、それはそうとして、テストが終ってから「台形の面積ってどうやって求めるんだっけ?」とか聴こえてきたのは、気のせいでしょうか? 落ちぶれたりとはいえ、こんな連中と同じ大学にいる我が身がホント情けない。
λ. 瓶暗
手焼きっていいな〜
2002-07-23
λ. システムプログラミング テスト
#include "/dev/tty"
に笑ってしまった。1988年に行われた第5回IOCCCで"Best abuse of the rules"を受賞した作品らしい。
でも、下らないミスをしてしまって悔しいのだ。
λ. プログラミング言語論 テスト
予想通り、並列処理に関する問題が解けなかった。
λ. 情報数学Ⅱ テスト
確率分布や検定の話が出なかったので助かった。
λ. システムプログラミング最終課題
気がついたら時間がなくなっていて、大した事は出来なかった。
とりあえず cd, pwd, 環境変数の展開, glob, alias だけ。あと、readlineとhistoryとpipe辺りはやりたかったのだけど……
そういえば、「char**」から「const char* const* char」ってキャストが必要なんでしたっけ? Warningを潰してる時間がなかったのでそのまま提出してしまったけどね。
![\xymatrix{
& & & A \\
C \ar@{-->}[rr]_{\langle f_1, f_2\rangle} \ar@/^1pc/[urrr]^{f_1} \ar@/_1pc/[drrr]_{f_2} & & A\times B \ar[ur]_{\pi_1} \ar[dr]^{\pi_2} & \\
& & & B
}](tex/b5af5ec6d0a4982e073745f72f05eb79.png "\xymatrix{
& & & A \\
C \ar@{-->}[rr]_{\langle f_1, f_2\rangle} \ar@/^1pc/[urrr]^{f_1} \ar@/_1pc/[drrr]_{f_2} & & A\times B \ar[ur]_{\pi_1} \ar[dr]^{\pi_2} & \\
& & & B
}")
2006-07-23
λ. 第十九回圏論勉強会
うげ、俺も腹痛い……。 会場には行ったが、人数が少なかったので、自習していた。
λ. 『陰陽ノ京〈巻の3〉』 渡瀬 草一郎
を読んだ。
Quotation
p.275-276より。
あるいは——もっと他の糸が、何処か自分たちの与り知らぬ所で、絡み合っていたのかもしれない。しかし、その糸がまるで見えぬために、この問いに対する答えを人は持つことが出来ない。(中略) それら全ての糸が、保胤にはもちろん、誰にも見えてはいない。人にとっての自然とは、そうしたものである。まるでわからないものといっても過言ではない。
2007-07-23
λ. 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 は連結も部分文字列取り出しも特に速くないはずなので。
