Mercurial > hg > Papers > 2017 > tatsuki-master
diff jungle.tex @ 18:d5306971efbf
eng abst
author | tatsuki |
---|---|
date | Fri, 10 Feb 2017 10:24:52 +0900 |
parents | 33d8077a5d45 |
children | 8d1f5ab7b420 |
line wrap: on
line diff
--- a/jungle.tex Thu Feb 09 19:28:45 2017 +0900 +++ b/jungle.tex Fri Feb 10 10:24:52 2017 +0900 @@ -3,7 +3,7 @@ 初めに Jungle の特徴である非破壊的木構造の説明をし、その後提供しているAPIについて述べる。 -\section{非破壊的木構造} +\section{破壊的木構造と非破壊的木構造} Jungle は、非破壊的木構造という特殊な木構造を持つ。 本節では、破壊的木構造と非破壊的木構造の編集・メリットデメリットについて記述する。 @@ -57,7 +57,7 @@ \end{center} \end{figure} -また、過去の木を保持する場合、非破壊的木構造は、木の複製後編集を行う必要がある。 +また、過去の木を保持する場合、破壊的木構造は、木の複製後編集を行う必要がある。 一方、非破壊的木構造は過去の木を上書きしないため、過去の木のルートノードを保持するだけで良い。 \section{NodePath} @@ -115,8 +115,7 @@ \section{JungleTree} Jungleは複数の木の集合で出来ている。 -Jungleの木は、自身の情報をTreeContext というオブジェクトに保持している。 -TreeContextとは、木構造のデータ(表\ref{TreeContext1})を持つクラスである。 +Jungleの木は、自身の情報をTreeContext という木構造のデータを持つ(表\ref{TreeContext1})オブジェクトに保持している。 \newpage \begin{table}[htb] @@ -157,7 +156,7 @@ \section{TreeNode} Jungleの木構造は、複数のノードの集合で出来ている。 -ノードは、自身の子のListと属性名と属性値の組でデータを持つ。 +ノードは、自身の子のリストと属性名と属性値の組でデータを持つ。 ノードに対するアクセスは、表\ref{TreeNodeAPI}に記述されているAPIを用いて行われる。 \begin{table}[htb] @@ -225,6 +224,8 @@ 表\ref{editor}にJungle Tree Editorインターフェースに定義されているAPIを記述する。 また、表\ref{editor}に記述しているAPIは全て、{\tt Either<Error,JungleTreeEditor>} を返す。 +\newpage + \begin{table}[htb] \begin{center} \caption{Editorに実装されているAPI} @@ -289,7 +290,7 @@ Jungle Tree Editor を用いて木に変更を加えた後は、Commit を行う必要がある。 Commit は、前節で記述した Jungle Tree Editor が持つ関数 {\tt success()} を使用することで行われる。 -Commit を行うと、Jungle Tree Editor が保持している編集後の木構造のデータを持つ TreeContext を作成する。 +Commit を行うと、Jungle Tree Editor は、保持している編集後の木構造のデータを持つ TreeContext を作成する。 そして、編集前の木が持つ TreeContext と 新しく作った TreeContext を置き換えることで Commit は完了する。 TreeContext の置き換えは、編集を行っている他の Thread と競合した際に、木の整合性を保つために以下の手順で行われる。 @@ -355,11 +356,9 @@ 2行目で、検索を行う関数 {\tt find()} を使用する。 今回は、Index を使って、属性名 {\tt "belong"} 属性値 {\tt "ryukyu"} を持つノード取得し、 3 - 5行目で定義されたクエリに渡す。 - そして、クエリの中で属性名 {\tt "name"} 属性値 {\tt "kanagawa"} を持つノードかどうかを確かめる。 結果として、属性名 {\tt "belong"} 属性値{\tt "ryukyu"}と、属性名 {\tt "name"} 属性値{\tt kanagawa}の2つのデータを持つノードの {\tt Iterator} が取得できる。 - 検索の際に使用する Index の実装については次節に記述する。 \begin{comment} @@ -382,7 +381,7 @@ Jungleは、非破壊的木構造というデータ構造上、過去の版の木構造を全て保持している。 よって、全ての版に独立したIndexが必要となるため、前の版のIndexを破壊すること無く、Indexを更新する必要がある。 既存のTreeMapでは、一度Indexの複製を行ない、その後更新する必要があったため、Indexの更新オーダーがO(n)となっていた。 -その問題を解決するため、非破壊TreeMapを自作し、それを用いてIndexの実装を行った。 +その問題を解決するため、Java 上で関数型プログラミングを行えるライブラリである、 Functional Java の TreeMapを使用し、それを用いてIndexの実装を行った。 このTreeMapは、Jungleと同じようにルートから変更を加えたノードまでの経路の複製を行い、データの更新を行った際、前の版と最大限データを共有した新しいTreeMapを作成する。 Jungleとの違いは、木の回転処理が入ることである。 これにより複数の版全てに対応したIndexをサポートすることが可能になった。