Mercurial > hg > Papers > 2017 > tatsuki-master

comparison indexupdate.tex @ 16:33f56478f7a4

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