#:g1: ropeの紹介

Posted 2014-06-08 15:00:00 GMT

(LISP Library 365参加エントリ)

 LISP Library 365 の160日目です。

ropeとはなにか

 ropeは、Evan Hanson氏作のropeのライブラリです。

パッケージ情報

パッケージ名rope
Chicken eggs:rope - The Chicken Scheme wiki

インストール方法

$ sudo chicken-install rope

すれば、

(use rope)

(require-extension rope)

試してみる

 ropeはimmutableな文字列です。大量の文字列処理に向いているとのことですが、詳細はropeの解説ページを参照して下さい。

 このライブラリでは、string系の関数は大体揃っているので、stringなんとかを書き直すだけでropeを利用したものへ書き直せそうです。

(let ((s "foo bar baz"))
  (rope->string (call-with-input-string s read-rope)))
"foo bar baz"

StringとRopeで速度比較

 処理が速いとのことなので、どんな感じなのかstringとropeを比べてみました。
青空文庫の「こころ/夏目漱石」を文字列にして、最後に「こんにちは」を付け足してみます。
連結は、文字列だとO(n)、ropeだとO(1)の処理みたいです。

(use rope)
(use utils) ;read-all

(define *kokoro-rope* (with-input-from-file "/tmp/utf8kokoro.txt" read-rope))

(rope-length *kokoro-rope*) ;=> 557917

(define *kokoro-string* (read-all "/tmp/utf8kokoro.txt"))

(string-length *kokoro-string*) ;=> 557917

まずはrope

(time 
 (let ((r (string->rope "こんにちは")))
   (let loop ((cnt 1000000) (acc '() ))
     (if (zero? cnt)
         acc
         (loop (- cnt 1)
               (cons (rope-append *kokoro-rope* r)
                     acc))))
   #f))
;>> 1.1s CPU time, 0.284s GC time (major), 122439 mutations, 4/7749 GCs (major/minor)
;=> #f

通常の文字列

(time 
 (let ((s "こんにちは"))
   (let loop ((cnt 1000) (acc '() ))
     (if (zero? cnt)
         acc
         (loop (- cnt 1)
               (cons (string-append *kokoro-string* s)
                     acc))))
   #f))
;>> 0.692s CPU time, 0.256s GC time (major), 1075 mutations, 9/492 GCs (major/minor)
;=> #f

文字列の場合、2000回位繰り返すと戻ってこなくなるので回数が違ったものになってしまいましたが、この例の場合では630倍位rope方が高速みたいです。

まとめ

 今回は、ropeを紹介してみました。
ChickenとRopeとエンコーディングの関係がちょっと分かっていません。
ropeの実装は、Racketにもあるようなので比べてみたい所です。

comments powered by Disqus