Mercurial > hg > Papers > 2017 > tatsuki-master
view indexupdate.tex @ 15:33d8077a5d45
commit
author | tatsuki |
---|---|
date | Thu, 09 Feb 2017 17:25:56 +0900 |
parents | 7acd7d5afeb6 |
children | 33f56478f7a4 |
line wrap: on
line source
\chapter{Indexの差分Update} Jungleの木はIndexを持っており、木のCommit時にFull Updateを行っている。 そのため、Commitを行うたびO(n)のIndexのUpdateが入り、木の編集時大きなネックとなっていた。 なので、高速にIndexの更新を行うため、Index の差分アップデートを実装した。 \section{差分 Updateの実装} Indexの差分 Updateを行うためには、編集を行ったノードを覚えておく必要がある。 そこで、Jungle Tree Editor 内に、編集を加えたノードを覚えておくためのリストを定義した。 Editor は、木に編集を加えたら、リストに編集前のノードを保存する。 そして、Commit 時にリストにあるノードを使って Index の Update を行う。 Indexの Update は、削除と挿入の2つのプロセスで行われる。 \section{Indexの削除} IndexのUpdateを行う際、初めに、編集後の木に存在しないノードをIndexから削除する。 削除の対象は、変更を加えたノードと、ルートから変更を加えたノードまでの経路にあるノードである。 ノードの削除は、以下の手順で行われる。 \begin{enumerate} \item 編集を行ったノードのリストからノードを取得する。 \item 取得したノードが、保持している値をIndexから削除する。 \item 自身と子供のペアを ParentIndex から削除する。 \item ParentIndex から親を取得する。 \item 2 - 4をルートノードにたどり着くか、ParentIndexから親を取得できなくなるまで続ける。 \item 1 - 5をリストからノードが無くなるまで続ける。 \end{enumerate} Parent Index から値が取得できない場合は、以降ルートまでのノードは Index から削除されていることが保証されているため、削除を終えて次のノードに行っても構わない。 \section{Indexへのノードの挿入} Indexから不要なノードを削除した後は、新しく作られたノードをIndexに挿入する。 ノードの挿入は、以下の手順で行われる。 \begin{enumerate} \item 木からルートノードを取得する。 \item 取得したノードがIndexに登録されているかを調べる。 \item 登録されている場合、そのノード以下のSub Treeは、全てIndexに登録されているので、次のノードに移動する。 \item 登録されていなかった場合、自身が保持している値をIndexに登録する \item 自身と子ノードをParent Index に登録する。 \item 全てのノードを挿入するまで 2 - 5 を繰り返す。 \end{enumerate} \section{Full Update との使い分け} Indexの差分Updateは、不要なノードの削除と新しく木に追加されたノードの挿入を行っているため、1ノードに対する処理は Full Updateより大きい。 少ない回数編集を行った後の Commit は、差分Updateの方が高速に行えるが、多くの編集を行った後の Commitだと、Full Updateの方が高速に動作する可能性がある。 そのため、Commit 前の、木の編集回数によって、Indexの更新方法を変更したほうが高速に Update を行える可能性がある。 これに関しての検証は、性能測定の章に記述する。 \newpage