Mercurial > hg > Papers > 2017 > tatsuki-master

comparison indexupdate.tex @ 2:90e06e17ca6b

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
commit
author tatsuki
date Sat, 28 Jan 2017 19:28:01 +0900
parents
children 498b8f4175f9
comparison
equal deleted inserted replaced
1:da6a6eba893d 2:90e06e17ca6b
1 \chapter{Indexの差分Update}
2 Jungleの木はIndexを持っており、木のCommit時に、Full Updateを行っている。
3 そのため、Commitを行うたび、O(n)のIndexのUpdateが入り、木の編集時大きなネックとなっていた。
4 なので、Indexの差分アップデートを実装した。
5
6 \section{差分 Updateの実装}
7 Jungleの木に編集を行う際、編集を行ったノードをリストに格納する。
8 そして、Commit時にリストにあるノードと、そのノードまでの経路にあるノードに対して、IndexをのUpdateを行う。
9
10 Indexの Update は、ノードの削除とノードの挿入の２つのプロセスで行われる。
11
12 \section{Indexの中身の削除}
13 IndexのUpdateを行う際、初めに木の編集後の木に存在しないノードをIndexから削除する。
14 削除の対象は、変更を加えたノードと、ルートから変更を加えたノードまでの経路にあるノードである。
15 ノードの削除は、以下の手順で行われる。
16
17 \begin{enumerate}
18 \item 編集を行ったノードのリストからノードを取得する。
19 \item 取得したノードから、保持しているデータを扱うAttributesクラスを取得する。
20 \item Attributesクラスから、ノードが保持している属性名のIteratorを取得する。
21 \item Attributesクラスから、3で取得した属性名とペアの属性値を取得する。
22 \item 3・4で取得した属性名・属性値を使ってIndexから自身を削除する。
23 \item 自身と子供のペアを ParentIndex から削除する。
24 \item ParentIndex から親を取得する。
25 \item 2 - 7をルートノードにたどり着くか、ParentIndexから親を取得できなくなるまで続ける。
26 \item 1 - 8をリストからノードが無くなるまで続ける。
27 \end{enumerate}
28
29
30 \section{Indexへのノードの挿入}
31 Indexから不要なノードを削除した後は、木に編集を加えた際に新しく作られたノードをIndexに挿入する。
32 ノードの挿入は、以下の手順で行われる。
33
34 \begin{enumerate}
35 \item 木からルートノードを取得する。
36 \item 取得したノードがIndexに登録されているかを調べる。
37 \item 登録されている場合、そのノード以下のSub Treeは、全てIndexに登録されているので、次のノードに移動する。
38 \item 登録されていなかった場合、取得したノードから保持しているデータを扱うAttributesクラスと、子供を扱うChildrenクラスを取得する。
39 \item Attributesクラスから、ノードが保持している属性名のIteratorを取得する。
40 \item Attributesクラスから、5で取得した属性名とペアの属性値を取得する。
41 \item 5・6で取得した属性名・属性値を使ってIndexに自身を登録する。
42 \item 2で取得したChildrenクラスから自身の子ノードを取得する。
43 \item 自身と取得した子ノードをParent Index に登録する。
44 \item 全てのノードを挿入するまで 2 - 9 を繰り返す。
45 \end{enumerate}
46
47
48 \section{Full Update との使い分け}
49 Indexの差分Updateは、不要なノードの削除と新しく木に追加されたノードの挿入を行っているため、1ノードに対する処理は Full Updateより大きい。
50 そのため、少ない編集後の Commit は、差分Updateの方が高速に行えるが、多くの編集を行った後の Commitだと、Full Updateの方が高速に動作する。
51 なので、木の編集回数によって、Indexの更新方法を変更する必要がある。
52
53
54 \newpage