日々の流転

λ. “Ropes: an Alternative to Strings” by Hans-J. Boehm, Russ Atkinson and Michael Plass

を読んだ。

d.y.d. - ICFP Programming Contest 2007 経由で w.l.o.g - ロープ より。稲葉さんのこの記事は以前にも読んでいたはずなのに、ICFP Programming Contest 2007 の期間中は思い出すことも出来なかった。残念。

稲葉さんの記事に付け加えることはほとんどないのだけど、ロープがバランスしていることをフィボナッチ数を使って定義しているのが少し面白かった。深さ n のロープがバランスしているのは文字列として長さが fib(n+2) 以上のとき。 ちなみに、フィボナッチ数が使われる他のデータ構造にはフィボナッチヒープがある。

しかしね、Rebalanceのところを読んでいて「The resulting rope will not be balanced in the above sense」とか書いてあったのには笑った。 ちょっ、おまっwww　まあ、その後には「but its depth will exceed the desired value by at most 2.」と続いてるんだけどね。

【7/30追記】 Haskellで基本的な部分だけ書いてみた。Rope.hs

λ. Shiroさんによる文字列実装の比較まとめ

だいありー (2005-07-20) から派生して、Shiroさんが [yarv-dev:541] Re: [im]mutable string で文字列実装を比較してまとめていたのを思い出した *1。 このスレッドの[yarv-dev:542] でもRopeの論文が言及されていた。