ロープ: 理論と実践
http://www.ibm.com/developerworks/jp/java/library/j-ropes/
大量の文字列を処理するのに有効なデータ構造としてロープと呼ばれるものがある。ロープは文字列を二分木で扱っちゃいましょうというものだ。詳しくはリンク先を読んでください、いじょうです。といってしまったら話が終わってしまう。ロープでは文字列を削除するときに、削除しない文字列が抜き出されて新しいロープが作られる。ロープは部分文字列を得るところさえ実装できてしまえば文字列を削除するところがさっくりと実装できてしまうすてきデータ構造だ。そのロープをVBScriptで実装してみた。
リンク先ではRopes for Javaが紹介されている。Ropes for Javaではバランスが崩れたときノードを配列にいったん格納して配列を2つに分けていって二分木の平衡を保つやりかたがされている。スケープゴートツリーに近い実装になっている。わたしはAvltreeでの実装をこころみた。
文字列を追加するところはふつうのAvltreeの処理とほとんど変わらない。値を一番下に追加してバランスをとる。ふつうのAvltreeはノードが一つずつ追加されていく。ノードの高さが1ずつ増えていく。Ropeでは値を一つ追加して高さが2つ増えるときがある。それに対処する必要がある。
高さが2つ増えるのはこんなとき。
hogeという文字列がロープのリーフに格納されていてhoとgeとのあいだにaを入れたいとき。まずhogeをhoとgeに分割する。aとgeを結合して、それとhoを結合する。結合ノードが2つ作られて高さが2増える。高さが2つ増えましたよーという情報を結合処理の戻り値で返して、平衡化の処理を行ったときにその情報を参照して平衡化の処理を完了してよいのか判断すればよいだけなので、実装としてはとくにむずかしくない。
文字列の削除は部分文字列を取り出す処理で行うことができる。部分文字列をどうやって取り出そうか。最初はRopes for Javaのように配列にリーフノードを格納していって、そこからAvltreeを作ろうと考えた。考えたはいいのだけれども、はてと、どうやって配列からAvltreeを作ればいいのだろうか。それを考えているときには、いぜん実装したような傾きの情報をもとに平衡化を行うやり方でAvltreeを実装していた。しかし、配列からAvltreeを作るとなるとどうやって傾きの値をセットすればいいのかしら。あらやだ、高さの情報が必要だわ。高さの情報がなかったら傾きの値をセットすることができないわ。だったらもういっそのこと傾きの情報を捨てちゃって高さをもとに平衡化を行う実装にしちゃったらいいじゃないの。そんなこんなで高さベースのAvltreeを実装することにした、途中から。それで、Avltreeの実装を変えてみて思ったのだけれども、Avltreeは高さベースで実装されるべきデータ構造のような気がしてきた。
傾きベースのAvltreeは平衡化を行うときに全部で10個の場合わけが必要になる。いっぽう高さベースのAvltreeは平衡化を行うときの場合わけが6個ですんでしまう。処理速度もそんなには変わらない。
傾きベースの場合わけ。
高さベースの場合わけ。
傾きベースの処理速度。
高さベースの処理速度。
傾きベースのAvltreeの実装（ロープじゃないです）。
AvltreeBalance.vbs
高さベースのAvltreeの実装（ロープじゃないです）。
AvltreeHeight.vbs
Ropeでは高さの情報があると2つのAvltreeを結合することができる。2つのAvltreeの高さが同じであれば新しい結合ノードを1個作って左と右にそれぞれの木をつけるだけで結合が完了する。2つのAvltreeの高さが違っていれば低いほうの木を高さが同じになるまで下のほうにずらしていって、高さが同じになったらそこに結合ノードを1つ挿入してそのノードの下に木を付けてやる。木の高さが1つ増えるだけなので値を挿入したときと同じやり方で平衡化の処理を行うことができる。左右の高さの差が1以下であるというAvltreeの状態を保ったままノードを結合していくことができる。このやり方を使えば配列にノードを格納せずに部分文字列をえることができる。
さてさてそんなこんなで実装したのがこれ。
Rope.vbs
&でStringを結合するやりかたとRopeの処理速度を比較したのがこれ。
VBScriptのStringって超速い・・・。
同じものをJavaで実装してJavaのStringクラスと比較した結果がこれ。
Rope.java
Javaではなかなかいい結果が出てるので実装はそんなにはそんなにはおかしくないと思うのだけれども、VBScriptではいまひとつの結果になってしまたよ。
