ICFPC で話題になった rope/cord ですが、特定の言語環境でしか使えないのはもったいない話です。そこで Ruby の拡張ライブラリとして実装しようとしました。
rope とは
以下の特徴を持った文字列の実装です。
- 文字列と文字列の結合が速い (O(log n)) らしい
- 部分文字列の切り出しが速い (O(log n)) らしい
- 部分の書き換えはできない
- 指定位置からの文字の取り出しは遅い (O(log n))
- でも一文字ずつ順にたどるのは実用上は O(n) らしい
実装方針
- Boehm GC 付属の Cord のコードを Boehm GC なしで動くようにする (リファレンスカウントを実装する) 。
- Ruby 側のインターフェイスは String 互換 (ただし破壊的操作と正規表現機能はなし)
ただ、C の文字列 (ASCIZ) に特化した機能や最適化が crosscutting concern になっていて手を入れにくすぎたのと、こまごましたスタイルがいろいろと気に入らなかった (笑) ので、コピペしつつも結局スクラッチから書いた感じです。だからきっと遅い&バグだらけ。あと、String 互換にする作業はとても面倒くさいので、テストするために必要だった極一部のインターフェイス *2 しか作っていません。
動作例
(とてつもなく不公平な) 速度比較。
$ time ./ruby -e 'x = "ab"; 24.times { x += x }; p x.size; p x[x.size / 2, 10]' 33554432 "ababababab" real 0m2.826s user 0m2.110s sys 0m0.680s $ time ./ruby -rrope -e 'x = Rope.new("ab"); 24.times { x += x }; p x.size; p x[x.size / 2, 10]' 33554432 "ababababab" real 0m0.037s user 0m0.020s sys 0m0.020s
約 78 倍の高速化です (笑)
以下は ICFPC の DNA インタプリタの一部です。ICFPC のドキュメントを割とそのまま写した感じに書きました。endo.dna を約 5 分半 *3 で処理します。プロトタイプくらいには使えそうです (でした) 。
def replace(env, tmpl) prefix = Rope.new("") tmpl.each do |type, a1, a2| prefix += case type when :base then a1 when :asnat then asnat((env[a1] || "").size) when :protect then protect(a1, env[a2] || "") end end prefix end
今後の予定
String 互換にしたりバグだししたりしないといけません。が、なんとなく動いた時点で興味が薄れたことと、正規表現が使えない文字列に存在意義があるのか疑わしい気分になったことから、投げ出しそうな気分です。とりあえず絶賛開発中バージョンを以下に投げ捨てておきます。コメントはないし破綻しかけているコードですが、奇特で暇な方が引き継いだり、踏み台にして作り直したりしてくれるとうれしいです。
http://dame.dyndns.org/misc/misc/rope-20070730.zip