|
2
|
1 \chapter{Indexの差分Update}
|
|
|
2 Jungleの木はIndexを持っており、木のCommit時に、Full Updateを行っている。
|
|
|
3 そのため、Commitを行うたび、O(n)のIndexのUpdateが入り、木の編集時大きなネックとなっていた。
|
|
6
|
4 なので、高速にIndexの更新を行う差分アップデートを実装した。
|
|
2
|
5
|
|
|
6 \section{差分 Updateの実装}
|
|
6
|
7 Indexの差分 Updateを行うためには、編集を行ったノードを覚えておく必要がある。
|
|
13
|
8 Jungleの木に編集を行ったノードをリストに格納する。
|
|
2
|
9 そして、Commit時にリストにあるノードと、そのノードまでの経路にあるノードに対して、IndexをのUpdateを行う。
|
|
|
10
|
|
|
11 Indexの Update は、ノードの削除とノードの挿入の２つのプロセスで行われる。
|
|
|
12
|
|
|
13 \section{Indexの中身の削除}
|
|
6
|
14 IndexのUpdateを行う際、初めに、編集後の木に存在しないノードをIndexから削除する。
|
|
2
|
15 削除の対象は、変更を加えたノードと、ルートから変更を加えたノードまでの経路にあるノードである。
|
|
|
16 ノードの削除は、以下の手順で行われる。
|
|
|
17
|
|
|
18 \begin{enumerate}
|
|
|
19 \item 編集を行ったノードのリストからノードを取得する。
|
|
6
|
20 \item 取得したノードが、保持している値をIndexから削除する。
|
|
2
|
21 \item 自身と子供のペアを ParentIndex から削除する。
|
|
|
22 \item ParentIndex から親を取得する。
|
|
6
|
23 \item 2 - 4をルートノードにたどり着くか、ParentIndexから親を取得できなくなるまで続ける。
|
|
|
24 \item 1 - 5をリストからノードが無くなるまで続ける。
|
|
2
|
25 \end{enumerate}
|
|
|
26
|
|
|
27
|
|
|
28 \section{Indexへのノードの挿入}
|
|
6
|
29 Indexから不要なノードを削除した後は、新しく作られたノードをIndexに挿入する。
|
|
2
|
30 ノードの挿入は、以下の手順で行われる。
|
|
|
31
|
|
|
32 \begin{enumerate}
|
|
|
33 \item 木からルートノードを取得する。
|
|
|
34 \item 取得したノードがIndexに登録されているかを調べる。
|
|
|
35 \item 登録されている場合、そのノード以下のSub Treeは、全てIndexに登録されているので、次のノードに移動する。
|
|
6
|
36 \item 登録されていなかった場合、自身が保持している値をIndexに登録する
|
|
|
37 \item 自身と子ノードをParent Index に登録する。
|
|
|
38 \item 全てのノードを挿入するまで 2 - 5 を繰り返す。
|
|
2
|
39 \end{enumerate}
|
|
|
40
|
|
|
41
|
|
|
42 \section{Full Update との使い分け}
|
|
|
43 Indexの差分Updateは、不要なノードの削除と新しく木に追加されたノードの挿入を行っているため、1ノードに対する処理は Full Updateより大きい。
|
|
13
|
44 少ない回数編集を行った後の Commit は、差分Updateの方が高速に行えるが、多くの編集を行った後の Commitだと、Full Updateの方が高速に動作する可能性がある。
|
|
|
45 そのため、Commit 前の、木の編集回数によって、Indexの更新方法を変更したほうが高速に Update を行える可能性がある。
|
|
|
46 これに関しての検証は、性能測定の章に記述する。
|
|
2
|
47
|
|
|
48 \newpage
|
