|
2
|
1 \chapter{既存のJungleとの変更点}
|
|
|
2 本章では、本研究で既存のJungleに行った大まかな変更概要を記述する。
|
|
|
3
|
|
|
4 \section{非破壊 Red Black Treeの実装}
|
|
|
5 JungleのIndexは、Java上で関数型プログラミングが行えるFunctional Java の非破壊 TreeMapを使って実装されていた。
|
|
|
6 しかし、Functional Javaは、処理が重く、実用的な性能ではなかったため、非破壊の TreeMap の実装を新しく行った。
|
|
|
7
|
|
|
8 \section{Indexの差分 Update}
|
|
13
|
9 Jungleは、Indexの更新をCommit時に Full Updateで行っている。
|
|
|
10 そのため、Commitを行うたび、O(n)のIndexのUpdateが入り、木の編集時大きなネックとなっている。
|
|
2
|
11
|
|
11
|
12 Index の更新処理を高速に行えるようにするため、
|
|
|
13 前の木との差分だけIndexを更新する機能を Jungle に追加した。
|
|
2
|
14
|
|
|
15
|
|
|
16 \section{Differential Jungle Treeの実装}
|
|
|
17 Jungleの木の変更の手間は木の形によって異なる。
|
|
|
18 特に線形の木は、変更の手間がO(n)となってしまう。
|
|
11
|
19 線形の木をO(1)で変更するために、Jungleは、ルートノードを追加していくPushPopの機能を持つ。
|
|
|
20 しかし、PushPopは木の並びが逆順になってしまうため、正順の木を構築する際には使用できない。
|
|
2
|
21 その問題を解決するために、Differential Jungle Treeの実装を行った。
|
|
|
22 Differential Jungle Treeは、木のバージョンごとに、自身の末尾のノードを保持する。
|
|
|
23
|
|
11
|
24 Differential Jungle Tree は、木を破壊的に更新するが、編集・検索時に、末尾ノードを使用することで、過去の木の形を残すことが可能となっている。
|
|
|
25
|
|
2
|
26
|
|
|
27 \section{Red Black Jungle Tree}
|
|
|
28 Default Jungle Treeにおいて、Indexの更新は大きな手間となっている。
|
|
|
29 Indexに使用する属性名が1種類で、木構造の形がデータを表現していない場合、Jungle Tree自身をIndexとしたほうが、効率的に木構造を構築できる。
|
|
6
|
30 そこで、Red Black Treeの性質を組み込んだRed Black Jungle Treeの実装を行った。
|
|
2
|
31 Red Black Jungle Tree は、生成時に木のバランスを取る際に使用する属性名(Balance Key)を指定する。
|
|
13
|
32 そして、ノードの挿入・削除時、Balance Keyを用いて木のバランスを取る。
|
|
2
|
33
|
|
13
|
34 木の探索に関してはBalanceKeyを用いた場合N(Logn)、そうでない場合はO(n)で行える。
|
