Mercurial > hg > Papers > 2017 > tatsuki-master

comparison indexupdate.tex @ 15:33d8077a5d45

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
commit
author tatsuki
date Thu, 09 Feb 2017 17:25:56 +0900
parents 7acd7d5afeb6
children 33f56478f7a4
comparison
equal deleted inserted replaced
14:e4da23b04260 15:33d8077a5d45
1 \chapter{Indexの差分Update} 1 \chapter{Indexの差分Update}
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の更新を行う差分アップデートを実装した。 4 なので、高速にIndexの更新を行うため、Index の差分アップデートを実装した。
5 5
6 \section{差分 Updateの実装} 6 \section{差分 Updateの実装}
7 Indexの差分 Updateを行うためには、編集を行ったノードを覚えておく必要がある。 7 Indexの差分 Updateを行うためには、編集を行ったノードを覚えておく必要がある。
8 Jungleの木に編集を行ったノードをリストに格納する。 8 そこで、Jungle Tree Editor 内に、編集を加えたノードを覚えておくためのリストを定義した。
9 そして、Commit時にリストにあるノードと、そのノードまでの経路にあるノードに対して、IndexをのUpdateを行う。 9 Editor は、木に編集を加えたら、リストに編集前のノードを保存する。
10 そして、Commit 時にリストにあるノードを使って Index の Update を行う。
10 11
11 Indexの Update は、ノードの削除とノードの挿入の２つのプロセスで行われる。 12 Indexの Update は、削除と挿入の２つのプロセスで行われる。
12 13
13 \section{Indexの中身の削除} 14 \section{Indexの削除}
14 IndexのUpdateを行う際、初めに、編集後の木に存在しないノードをIndexから削除する。 15 IndexのUpdateを行う際、初めに、編集後の木に存在しないノードをIndexから削除する。
15 削除の対象は、変更を加えたノードと、ルートから変更を加えたノードまでの経路にあるノードである。 16 削除の対象は、変更を加えたノードと、ルートから変更を加えたノードまでの経路にあるノードである。
16 ノードの削除は、以下の手順で行われる。 17 ノードの削除は、以下の手順で行われる。
17 18
18 \begin{enumerate} 19 \begin{enumerate}
21 \item 自身と子供のペアを ParentIndex から削除する。 22 \item 自身と子供のペアを ParentIndex から削除する。
22 \item ParentIndex から親を取得する。 23 \item ParentIndex から親を取得する。
23 \item 2 - 4をルートノードにたどり着くか、ParentIndexから親を取得できなくなるまで続ける。 24 \item 2 - 4をルートノードにたどり着くか、ParentIndexから親を取得できなくなるまで続ける。
24 \item 1 - 5をリストからノードが無くなるまで続ける。 25 \item 1 - 5をリストからノードが無くなるまで続ける。
25 \end{enumerate} 26 \end{enumerate}
27
28 Parent Index から値が取得できない場合は、以降ルートまでのノードは Index から削除されていることが保証されているため、削除を終えて次のノードに行っても構わない。
29
26 30
27 31
28 \section{Indexへのノードの挿入} 32 \section{Indexへのノードの挿入}
29 Indexから不要なノードを削除した後は、新しく作られたノードをIndexに挿入する。 33 Indexから不要なノードを削除した後は、新しく作られたノードをIndexに挿入する。
30 ノードの挿入は、以下の手順で行われる。 34 ノードの挿入は、以下の手順で行われる。