日々の流転

λ. 艦砲射撃!

FLASHのゲーム。ちとはまってしまった。

λ. "A New Method for Functional Arrays", Melissa O'Neill, F. Warren Burton

Syntax Error (2004-08-20) より。配列の外にバージョン管理の情報をつけるのではなく、配列の要素に構造を持たせて、要素レベルでバージョンの管理をする fat element という方法を提案している。「へぇ、こんな方法があるんだ」と感心。計算量はsingle-threadedならO(1)。single-threadedでなくてもアクセスが一様なら、amortizedな計算量でO(1)。それ以外はamortizedな計算量でO(log n)か。結構いいね。

• 神戸隆行さんによる紹介