Mongrel2のコードを眺めていてRagelという有限オートマトンを一般的なプログラミング言語にコンパイルするツールのことが気になった。Ragelのユーザーガイドの冒頭に、rationale的なことが書いてある。それとか、Wikipediaで読み漁ったところを勉強メモとし…

Mongrel2のsrc/http11/http11_parser.cを見てたら以下のようなコードがあった。 #line 454 "src/http11/http11_parser.c" switch( (*p) ) { case 33: goto st16; case 58: goto tr25; case 124: goto st16; case 126: goto st16; } if ( (*p) < 45 ) { if ( …

クリーンなCで書かれたWebサーバ「Mongrel2」を読んでみた。コードの内外ともにドキュメントはしっかりしているし、関連ブログエントリもあって、非常に勉強になる。何より、毒舌のZed Shawの書く文章は面白くて飽きないのがいい。例えば、src/adt以下にはユ…

知人に6x6の魔方陣を見せられて、そういえば魔方陣ってやったことないなと思ってRubyで解いてみた。モヤモヤと悩みつつ、良い練習になった。RubyにはEnumerable#permutationという強力なのがある。多重ループを使わなくても、「(0..3).to_a.permutation」と…

ハフマン符号化に使うハフマンツリーをRubyで作ってみた。2本のキューを用意して、2つのノードをくっつけたり出し入れするのが簡単というのでそういう方針で。本当は1本はプライオリティ・キューでないとエンキュー時にソートするために効率が悪い。 # Huffm…

Lispは遅くて実用にならないと揶揄されるで、それに論駁するために竹内郁雄先生が2時間ほどで考えだしたという「たらい回し関数」を、手元で実行してみた。計算量はtarai(2n,n,0)の場合にO(n^n)ということらしい。これだけ短いコードで、これほどの計算量の…

ここにある迷路の最短経路を調べる問題をやってみた。これはまた要するに動的計画法でいいんでしょ、とハンマーの使い方を覚えたもんだからすべてが釘に見える感じで、同じ方法論でやってみようとしてみたり。ダイクストラ法がうんたらという話も聞こえてき…

オイラー・プロジェクトの18問目、67問目。ピラミッド状に並んだ数字を上から下までたどるとき、足した結果が最大になる経路を見つけろというもの。単純に上から大きい方を選びつつ降りていくだけでは正解は得られない。かといって、可能な経路をすべて調べ…

プロジェクト・オイラーの15問目。以下の2x2のグリッドを左上から右下になぞるとき、6つのルートがある。20x20のグリッドではルートは何通りか。最初にRubyで書いてみた。確認のために経路を配列に残しつつ。 WIDTH, HEIGHT = 2,2 $count = 0 def step_forwa…

理系関連のトピックに関して、Wikipediaには初学者向けに優れた記述が多いように感じているけど、その中でも特にコンピュータサイエンスに関しては英語、日本語ともにコンパクトで読みやすい解説が多いように思う。Wikipediaで木構造について色々と読み漁っ…

MyHeapのsiftdownでコードの重複と分岐の分かりづらさが気になったので書き換えてみた。 def siftdown(n) if n * 2 > @n then return elsif n * 2 == @n then if @q[n] > @q[n * 2] then @q[n], @q[n * 2] = @q[n * 2], @q[n] end elsif n * 2 + 1 <= @n the…