rope ライブラリ

ICFPC で話題になった rope/cord ですが、特定の言語環境でしか使えないのはもったいない話です。そこで Ruby の拡張ライブラリとして実装しようとしました。

rope とは

以下の特徴を持った文字列の実装です。

  • 文字列と文字列の結合が速い (O(log n)) らしい
  • 部分文字列の切り出しが速い (O(log n)) らしい
  • 部分の書き換えはできない
  • 指定位置からの文字の取り出しは遅い (O(log n))
  • でも一文字ずつ順にたどるのは実用上は O(n) らしい

詳しい話はいなばさんの解説なり元論文なりを見てください *1

実装方針

  • 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

追記

重要なことを言い忘れていましたが、ruby 1.9 (trunk) の環境で開発・テストしています。1.8 だとコンパイルすらできないかもしれません (試してない) 。そういえば、M17N に絡む話でもあるんだなぁ。どうなる予定なんだっけ。

*1:ちなみに僕は元論文をまともに読んでいません (笑)

*2:Rope#+ 、Rope#* 、length (size) 、index 、rindex 、to_s (to_str) 、inspect 、[] (slice) 、<=> 、empty?

*3:Core 2 T7200 @ 2.00 GHz 、Windows XPcoLinux 上の Debian で測定。