Rope に関するあれこれ - yujioramaの日記

String は、1 つの文字シーケンスとして隣接した領域に保持する。
Rope は、文字シーケンスの連結ノードを保持する。

なので、追加やアクセスの計算量特性が少し違っている。
文字連結のコストが O(1) になり、文字の取得のコストが O(log_n) になる。

Rope の連続した文字シーケンスにアクセスするときは、Iterator を使うとすこし速い。

ただし、文字シーケンスが単独のノードからなる Rope の場合は、charAt が一番速い。

ストリームへの書き込みにおいて、os#write に Rope を渡すと toString を経由するが、これは遅い。

rope.write(os) とすることで、最適な出力が行われる。

挿入テストでは、String の処理時間は指数関数的に増加するのに対して、Rope のそれは O(1) です。

これまでの String を Rope で置き換えることが有効なのは、

ようなケースです。

内部ノードの数が少なければ、String に対する各種操作はだいたい最悪でも元のままです。