Mercurial > hg > Papers > 2017 > tatsuki-master
changeset 26:4365c210d1cb
commit
| author | tatsuki |
|---|---|
| date | Sun, 12 Feb 2017 01:51:51 +0900 |
| parents | 8d1f5ab7b420 |
| children | 796c18a4aa0d |
| files | benchMark.tex databases.tex jungle.tex jungleUpdatePoint.tex master_paper.pdf master_paper.tex renderingEngine.tex result/createIndex.xbb result/createListTree.xbb result/createRedBlackTreeAndDefaultTreeTime.eps result/createRedBlackTreeAndDefaultTreeTime.pdf result/createRedBlackTreeAndDefaultTreeTime.xbb result/defaultJungleTreeCreateTime result/findTime.xbb result/redBlackTreeCreateTime |
| diffstat | 15 files changed, 270 insertions(+), 307 deletions(-) [+] |
line wrap: on
line diff
--- a/benchMark.tex Sat Feb 11 19:04:30 2017 +0900 +++ b/benchMark.tex Sun Feb 12 01:51:51 2017 +0900 @@ -1,8 +1,8 @@ \chapter{性能測定} - 前章までに、Jungle へ行った改善点・開発したアプリケーションについて述べた。 本章では、実装した新機能の性能測定を行う。 - +また、最後に既存のDBとの検索速度の比較を行う。 +比較対象には、MongoDBとPostgreSQLを選択した。 \section{測定環境} 表\ref{environment}に、測定を行ったマシンの環境を記述する。 @@ -30,7 +30,7 @@ 5章で実装した TreeMap の性能測定を行う。 比較対象には、 TreeMap 実装前に Jungle で使用していた Functional Java の TreeMap を使用する。 -図\ref{find}は、 TreeMap に1000回の Get を行った際のベンチマークである。 +図\ref{find}は、 TreeMap に1000回の Get を行った際のグラフである。 X 軸は Get を行う TreeMap のノード数。 Y 軸は Get にかかった時間を表す @@ -51,7 +51,7 @@ \newpage \section{Index の差分 Update の測定} 6章で実装した、Index の差分 Update の測定を行う。 -図\ref{index}は、Index の差分 Update と FullUpdate の両方で木のCommitを行った際のグラフである。 +図\ref{index}は、Index の差分 Update と FullUpdate の速度比較のグラフである。 測定は、木にノードを追加、Commit を1セットの変更として行う。 X 軸は、木に行った変更のセット数。 Y 軸は、Commit にかかった時間を表す。 @@ -64,18 +64,16 @@ \end{center} \end{figure} -図\ref{index}より、Index の Full Update は、グラフがO(n\verb|^|2)なのに対し、 差分 Update は、O(n)で行えている。 - +図\ref{index}より、Index の Full Update に比べて差分 Updateの方が高速に木の構築に成功している。 しかし、Jungleでは木に変更を加える際、毎回 Commit を行うわけでなく、 基本的に複数回変更を行った後、一気にCommit を行う。 差分 Update は、変更を加えたノードを記憶し、 Commit 時に Index の更新を行う。 一方、Full Update では、 Commit を行うまでに木に加えた変更の数に関係なく、新しい Index を構築する。 -よって、 Commit を行うまでに行う木の編集回数が増えた場合、 Index の Full Update と 差分 Update では、差分 Update の方が、Index に対して多くの変更を行うことになる。 +よって、 Commit 前の木の編集回数が増えた場合、 Index の Full Update と 差分 Update では、差分 Update の方が、Index に対して多くの変更を行うことになる。 そのため、Commit を行うまでの 木に対する変更回数によっては、 Full Update の方が高速に Index の構築を行える可能性がある。 そこで、図\ref{index2}に、Commit を行うまでに行った木の編集回数と、 Index の Update 速度の測定結果を記述する。 -X軸は、1回の Commit を行うまでに木に行った変更のセット回数。 -Y軸は、Commit にかかった時間を表す。 -また、構築する木のノード数は1000ノードとする。 +X 軸は、1回の Commit を行うまでに木に行った編集回数。 +Y 軸は、Commit にかかった時間を表す。 \begin{figure}[htpb] \begin{center} \includegraphics[scale=0.6,angle = -90]{result/createIndex2.pdf} @@ -91,7 +89,7 @@ \section{正順の線形木の構築時間の測定} 7章で実装した、 Differential Jungle Tree の性能測定を行う。 比較対象は、Default Jungle Tree を用いる。 -図\ref{dfTree}は、正順の木を構築するまでにかかった時間のベンチマークである。 +図\ref{dfTree}は、正順の木を構築するまでにかかった時間のグラフである。 X 軸は、構築した木のノード数。 Y 軸は、構築にかかった時間を表す。 また、木のみを構築する時間を測定するため、Index は作っていない。 @@ -112,36 +110,35 @@ \section{Red Black Jungle Tree の測定} 8章で実装した、Red Black Jungle Tree の性能測定を行う。 比較対象は、Default Jungle Tree を用いる。 -図\ref{redblack}は、正順の木を構築するまでにかかった時間のベンチマークである。 +図\ref{redblack}は、木を構築するまでにかかった時間のグラフである。 X 軸は、構築した木のノード数。 Y 軸は、構築にかかった時間を表す。 \begin{figure}[htpb] \begin{center} -\includegraphics[scale=0.6]{result/createRedBlackTreeAndDefaultTreeTime.pdf} +\includegraphics[scale=0.6,angle=-90]{result/createRedBlackTreeAndDefaultTreeTime.pdf} \caption{Red Black Jungle Tree と Default Jungle Tree} \label{redblack} \end{center} \end{figure} 図\ref{redblack}より、Default Jungle Tree より、 Red Black Jungle Tree の方が高速に木を構築している。 -これは、Default Jungle Tree が、木を構築する際に Index を生成しているのに対し、 Red Black Jungle Tree は、自身の木構造が Index と同等の働きを持つため、Index を構築する必要がない。 -その差が出たためである。 +これは、Default Jungle Tree が、木を構築する際に Index を生成しているのに対し、 Red Black Jungle Tree は、自身の木構造が Index と同等の働きを持つため、Index を構築する必要がないからである。 \section{既存のデータベースとの比較} Jungle と既存のデータベースとの比較を行う。 -比較対象は PostgreSql と mongoDB を選択した。 -検索対象のデータは10000件。 +比較対象は PostgreSQL と mongoDB を選択した。 データの検索の速度を比較した。 図\ref{compareDB}に結果のグラフを記述する。 - +X 軸は、データベースのデータ数。 +Y 軸は、検索にかかった時間を表す。 \begin{figure}[htpb] \begin{center} -\includegraphics[scale=0.6,angle=-90]{result/findTime.pdf} +\includegraphics[scale=0.6,angle=-90]{result/comparedb.pdf} \caption{既存の DB との比較} \label{compareDB} \end{center} \end{figure} -図\ref{compareDB}より、Jungle は PostgreSql と mongDB と比較して、非常に高速な検索を行えている。 -理由として、PostgreSql と mongoDB は、通信を介してデータにアクセスするのに対し、Jungle は、アプリケーション内にデータがあるため、通信を介さないためだと考えられる。 +図\ref{compareDB}より、Jungle は PostgreSQL と mongDB と比較して、非常に高速な検索を行えている。 +理由として、PostgreSQL と mongoDB は、通信を介してデータにアクセスするのに対し、Jungle は、アプリケーション内にデータがあるため、通信を介さないためだと考えられる。
--- a/databases.tex Sat Feb 11 19:04:30 2017 +0900 +++ b/databases.tex Sun Feb 12 01:51:51 2017 +0900 @@ -8,81 +8,73 @@ データベースへのアクセスは、SQLを用いて行う。 データの格納を行う際は、まずテーブルのデータの型と・制約を定義する。 -テーブルの定義は、 +テーブルの定義は{\tt CREATE TABLE}文を用いて行う。 +ソースコード\ref{createTablePSQL}に{\tt int}型の{\tt id}と{\tt TEXT}型の{\tt name}を持つテーブル{\tt person}を作成するサンプルコードを記述する。 -\begin{vervatime} -CREATE TABLE table名 ( \\ -\ \ 値の名前 型 制約 , …… \\ -) \\ -} -の構文で行う。 -制約というのは、テーブルに値を入れる際に守らなければならない条件のことである。 -値の重複を許さない行を特定する際に用いる{\tt PRIMARY KEY}などがある。 -また、テーブル同士は{\tt PRIMARY KEY}を用いて参照を行うことが可能である。 +\begin{lstlisting}[frame=lrbt,numbers=left,label=createTablePSQL,caption=テーブルの作成] +create table person(id int,name TEXT); +\end{lstlisting} + +%制約というのは、テーブルに値を入れる際に守らなければならない条件のことである。 +%値の重複を許さない行を特定する際に用いる{\tt PRIMARY KEY}などがある。 +%また、テーブル同士は{\tt PRIMARY KEY}を用いて参照を行うことが可能である。 -テーブルへのデータの格納は、 +テーブルへのデータの格納は、Insert文を用いて行う。 +ソースコード\ref{insertPSQL}に、{\tt id}が{3}、{\tt name}が{kanagawa}の値を格納するサンプルコードを記述する。 -\vspace{0.1in} -{\tt -INSERT INTO テーブル名 VALUES( \\ -\ \ 格納するデータ \\ -); \\ -} -の構文で行う。 +\begin{lstlisting}[frame=lrbt,numbers=left,label=insertPSQL,caption=データの挿入] +insert into person(id,name) values(3,'kanagawa'); +\end{lstlisting} + テーブルにデータを格納する際にはスキーマの定義に沿ってなければならない。 もし、スキーマに反するデータを格納した場合 エラーが発生しデータの格納に失敗する。 -作成したテーブルからのデータの取得は、 - -\vspace{0.1in} -{\tt -Select 表示する値 FROM テーブル名;\\ -} +テーブルへのデータの検索は、select文を用いて行う。 +select文では、表示するデータの指定などが行える。 +ソースコード\ref{selectPSQL}に、テーブル{\tt person}から{\tt name}が{\tt kanagawa}のデータのidを取得するコードを記述する。 +\begin{lstlisting}[frame=lrbt,numbers=left,label=selectPSQL,caption=データの検索] +select id from person where name='kanagawa'; +\end{lstlisting} -の構文で行う。 -またテーブル名の後ろに表示する値の絞込や、データの並び替えなどのオプションをつけることも可能である。 PostgreSQLでは、Json形式をJson・JsonBという型を用いて格納する。 Json型は、Jsonデータを文字列で格納し、JsonBはバイナリで格納する。 Json型で格納した場合、データにアクセスするたびにパースする必要がある。 -JsonのIndex を張ることが可能になっている。 -%JsonのIndexの貼る例題 +%JsonのIndex を張ることが可能になっている。 % Jsonデータのアップデートは、Jsonの大きさnに対してO(n)になってしまう。 \section{MongoDB} -MongoDB\cite{mongo} は2009年に公開された NoSQL のデータベースである。 -JSON フォーマットのドキュメントデータベースであり、スキーマレスト呼ばれる。 +MongoDB\cite{mongoDBDoc} は2009年に公開された NoSQL のデータベースである。 +JSON フォーマットのドキュメントデータベースであり、スキーマレスと呼ばれる。 MongoDBでは、テーブルの代わりにコレクションにデータを保持する。 スキーマが無いため、事前にデータの定義を行う必要がなく、同じコレクションであっても、他のドキュメントが持っていないフィルドやデータ型をドキュメントに含めることができる。 そのためリレーショナルデータベースに比べてデータの追加・削除が行いやすい。 -コレクションへのデータの格納は、 +コレクションへのデータの格納は、{\tt insert()}を用いて行う。 +ソースコード\ref{insertMongo}に、{\tt id}が{\tt 5}、{\tt name}が{\tt kanagawa}のデータをコレクション{\tt person}に挿入するサンプルコードを記述する。 -\vspace{0.1in} -{\tt -db.コレクション名.insert({Jsonフォーマットで記述されたデータ});\\ -} +\begin{lstlisting}[frame=lrbt,numbers=left,label=insertMongo,caption=データの検索] +db.person.insert({id:5,name:"kanagawa"}); +\end{lstlisting} -の構文で行う。 -Json形式のデータは任意の深さまでネストすることが可能である。 +また、Json形式のデータは任意の深さまでネストすることが可能である。 -作成したコレクションからのデータの取得は、 +作成したコレクションからのデータの取得は、{\tt find}を用いて行う。 +ソースコード\ref{findMongo}に、{\tt id}が{\tt 5}のユーザーの{\tt name}を取得するサンプルコードを記述する。 -\vspace{0.1in} -{\tt -db.コレクション名.find(検索条件,表示する値の絞込);\\ -} +\begin{lstlisting}[frame=lrbt,numbers=left,label=findMongo,caption=データの検索] +db.person.find({id:5},{name:1}); +\end{lstlisting} -の構文で行う。 -引数を渡さなかった場合、コレクションの中身が全て表示される。 +findに引数を渡さなかった場合、コレクションの中身が全て表示される。 MongDBは、あらゆる箇所でJavaScriptを用いており、前述した{\tt insert()}・{\tt find()}といった関数もJavaScriptで実装されている。 dbですらJavaScriptのオブジェクトである。 @@ -92,64 +84,63 @@ MongoDBは実装にmmapを使用しているため、トランザクションを安全に行うことが難しい。 そのためデータの喪失などが発生することが知られている。 -このようにMongoDBは、非常に柔軟なデータモデルを扱え、 JavaScript を用いることで複雑な検索も可能である。 -一方でデータの設計を行わないと、そのパフォーマンスを活かすことはできない。 \section{Cassandra} Cassandraは2008年7月にFacebookによって開発された Key-Value なデータベースである。 -データは4次元の連想配列のようになっている。 -{\tt [KeySpace][ColumnFamily][Key][Column]}\\ - -データを格納する場合初めに、KeySpaceを構築する。 -KeySpaceは、 +Cassandraは、分散環境下では複数のノードにデータのレプリカを置くことで、データの信頼性を確保する。 +いくつのノードにレプリカを置くかはレプリケーション係数を指定することで決定する。 +またノードの集合をデータセンターとして管理している。 -\vspace{0.1in} -{\tt -create keyspace KeySpace名 with replication = {レプリケーションの設定};\\ -} +Cassandraはデータを +{\tt [KeySpace][ColumnFamily][Key][Column]}\\ +の4次元の連想配列で持つ。 +データを格納する場合初めにKeySpaceを構築する。 +KeySpaceを作る際は、データセンターの設定とレプリケーション係数の設定を同時に行う。 +ソースコード\ref{createKeySpace}に単一のデータセンターにレプリケーションを一つしか持たないKeySpaceである{\tt testKeySpace}を作成するサンプルコードを記述する。 -の構文で行う。 -レプリケーションとは、データベースを別のノードに複製し、データの編集時に同期を取ることである。 -障害時に、複製したデータを持つサーバにリクエストを行うことで、データの取得を行える。 -データベースに対する負荷が高まった際に、複製を行ったノードに分散を行えるなどのメリットがある。 + + +\begin{lstlisting}[frame=lrbt,numbers=left,label=createKeySpace,caption=KeySpaceの作成] +create keyspace testKeySpace with replication = {'class':'SimpleStrategy', 'replication_factor':1}; +\end{lstlisting} KeySpaceは、PostgreSQLでいうところのデータベースに近い働きをする。 - -作成した KeySpace に対してColumnFamily を構築する。 -ColumnSpace は、 +次は、作成した KeySpace に対してColumnFamily を構築する。 +ColumnSpaceは、RDBでいうテーブルに似た働きをする。 +ソースコード\ref{createColumnFamily}に、{\tt int}型の{\tt id}と{\tt text}型の{name}を持つColumnSpaceを作成するサンプルコードを記述する。 -\vspace{0.1in} -{\tt -create table テーブル名 (Key Column PRIMARY KEY, Key Column); \\ -} +\begin{lstlisting}[frame=lrbt,numbers=left,label=createColumnFamily,caption=ColumnFamilyの作成] +create table person (id int PRIMARY KEY, name text); +\end{lstlisting} + -の構文で行う。 -また、テーブルの定義で最低１つは Key にオプションで PRIMARY KEY を指定する必要がある。 -ColumnFamily は、PostgreSQL でいうところのテーブルに近い働きをする。 +また、ColumnSpaceの定義を行う際最低１つKeyに値を特定するためのPRIMARY KEY を指定する必要がある。 -作成したColumnFamily への値の挿入は、 +作成したColumnFamily への値の挿入は、insert文を用いて行う。 +ソースコード\ref{insertCassandra}に、{\tt id}が{1}、{\tt name}が{\tt kanagawa}のデータを挿入するサンプルコードを記述する。 -\vspace{0.1in} -{\tt -INSERT INTO テーブル名 (key1,key2) VALUES (column1, column2);\\ -} +\begin{lstlisting}[frame=lrbt,numbers=left,label=insertCassandra,caption=ColumnFamilyの作成] +insert into person(id,name) values(1,'kanagawa'); +\end{lstlisting} -の構文で行う。 -また、Cassandra は、PRIMARY KEY で指定した Key で、Column を管理しているため、重複した PRIMARY KEY で 値を挿入すると、データの更新扱いになり上書きされる。 +作成した ColumnFamily からのデータの取得は、select文を用いて行う。 +ソースコード\ref{findCas}に、{\tt id}が{\tt 1}のユーザーの{\tt name}を取得するサンプルコードを記述する。 -作成した ColumnFamily からのデータの取得は、 +\begin{lstlisting}[frame=lrbt,numbers=left,label=findCas,caption=ColumnFamilyの作成] + select name from person where id = 1; +\end{lstlisting} + -\vspace{0.1in} -{\tt -SELECT 表示する値 FROM テーブル名 オプション;\\ -} +Cassandraはデータの読み書きをいくつのノードに行うかをConsistteency Levelで設定する。 +Consistency Levelは主に、ONE、QUORAM、ALLがある。 +データの複製であるレプリケーションの数をNとした場合、ONEは１つのノード、QUERUMはN/2 + 1のノード、ALLはNのノードへと読み書きを行う。 +CassandraはConsistency Levelを変えることで、最新のデータを取得するかどうかを決めることができる。 +しかし、最新のデータを取得するために、Consistency LevelをQUERUMやALLに変えた場合、データの読み書き時に問い合わせるノードが増えるため速度は落ちてしまう問題もある。 -で行う。 -またテーブル名の後ろに表示する値の絞込や、データの並び替えなどのオプションをつけることも可能である。 \section{非破壊的木構造データベースJungle}
--- a/jungle.tex Sat Feb 11 19:04:30 2017 +0900 +++ b/jungle.tex Sun Feb 12 01:51:51 2017 +0900 @@ -70,44 +70,6 @@ 木の変更は非破壊的に行われ、木のルートを変更後の木に置き換えるAtomicOperationがトランザクションとなる。 木の変更はLogとして記録され、分散ノードあるいはディスクに格納される。 JungleのAPIは、Eitherを返すようになっており、Eitherの型をチェックすることにより成功と失敗がわかるようになっている。 -今回効率的な木の非破壊アップデートを可能にするために追加した機能である、 -Jungleの中で使用する非破壊赤黒木、Indexの差分アップデート、Differential Jungle Tree、Red Black Jungle Treeについて説明する。 - - -\section{NodePath} -Jungleでは、木のノードの位置を{\tt NodePath}クラスを使って表す。 -{\tt NodePath}クラスはルートノードからスタートし、対象のノードまでの経路を数字を用いて指し示す。また、ルートノードは例外として-1と表記される。 -{\tt NodePath}クラスを用いて{\tt< -1,1,2,3>}を表している際の例を図\ref{NodePath}に記す。 - -\begin{figure}[htpb] -\begin{center} -\includegraphics[scale=0.7]{figures/nodePath.pdf} -\caption{NodePath} -\label{NodePath} -\end{center} -\end{figure} - -\newpage -\section{Either} -Jungleは、失敗する可能性のある関数では返り値を{ \tt Either<A、B>}に包んで返す。 -AにはError、Bには処理に成功した際の返り値の型が入る。 -Eitherは、AかBどちらかの値しか持たない。 -以下にEitherクラスが提供しているAPI(表\ref{EitherAPI})を記す。 -\begin{table}[htb] -\begin{center} -\caption{Eitherに実装されているAPI} -\begin{tabular}{|p{15em}|p{24em}|} \hline -{\small{\tt boolean isA()}} & {\small EitherがAを持っているかどうかを調べる。持っている場合trueを返す。}\\ \hline -{\small{\tt boolean isB()}} & {\small EitherがBを持っているかどうかを調べる。持っている場合trueを返す。}\\ \hline -{\small{\tt A a()}} &{\small Aの値を取得する。}\\ \hline -{\small{\tt B b()}} &{\small Bの値を取得する。}\\ \hline -\end{tabular} -\label{EitherAPI} -\end{center} -\end{table} - -{\tt Either<A、B>} の使い方は、{\tt isA()}を用いて関数が{\tt Error}を返していないかを調べる。 -{\tt Error}でない場合は{\tt b()}で関数の返り値を取得する。 \section{木の生成} @@ -167,6 +129,29 @@ \end{center} \end{table} +\section{Either} +Jungleは、失敗する可能性のある関数では返り値を{ \tt Either<A、B>}に包んで返す。 +AにはError、Bには処理に成功した際の返り値の型が入る。 +Eitherは、AかBどちらかの値しか持たない。 +以下にEitherクラスが提供しているAPI(表\ref{EitherAPI})を記す。 +\begin{table}[htb] +\begin{center} +\caption{Eitherに実装されているAPI} +\begin{tabular}{|p{15em}|p{24em}|} \hline +{\small{\tt boolean isA()}} & {\small EitherがAを持っているかどうかを調べる。持っている場合trueを返す。}\\ \hline +{\small{\tt boolean isB()}} & {\small EitherがBを持っているかどうかを調べる。持っている場合trueを返す。}\\ \hline +{\small{\tt A a()}} &{\small Aの値を取得する。}\\ \hline +{\small{\tt B b()}} &{\small Bの値を取得する。}\\ \hline +\end{tabular} +\label{EitherAPI} +\end{center} +\end{table} + +{\tt Either<A、B>} の使い方は、{\tt isA()}を用いて関数が{\tt Error}を返していないかを調べる。 +{\tt Error}でない場合は{\tt b()}で関数の返り値を取得する。 + + + \section{TreeNode} Jungleの木構造は、複数のノードの集合で出来ている。 @@ -231,6 +216,24 @@ 3 - 7行目でルートノードの1番目の子ノードを取得し、 8 - 9行目で、ルートの1番目の子ノードから、属性名 "name" とペアの属性値を取得している。 + +\section{NodePath} +Jungleでは、木のノードの位置を{\tt NodePath}クラスを使って表す。 +{\tt NodePath}クラスはルートノードからスタートし、対象のノードまでの経路を数字を用いて指し示す。また、ルートノードは例外として-1と表記される。 +{\tt NodePath}クラスを用いて{\tt< -1,1,2,3>}を表している際の例を図\ref{NodePath}に記す。 + +\begin{figure}[htpb] +\begin{center} +\includegraphics[scale=0.7]{figures/nodePath.pdf} +\caption{NodePath} +\label{NodePath} +\end{center} +\end{figure} + +\newpage + + + \section{木の編集API} Jungleの木の編集は{\tt Default Jungle Tree Editor}クラスを用いて行われる。 {\tt Default Jungle Tree Editor}クラスは、木に対する編集を行うAPIが定義されているJungle Tree Editorインターフェースを実装している。
--- a/jungleUpdatePoint.tex Sat Feb 11 19:04:30 2017 +0900 +++ b/jungleUpdatePoint.tex Sun Feb 12 01:51:51 2017 +0900 @@ -1,5 +1,7 @@ \chapter{データベースJungleに\\新たに追加した構成要素} -本章では、本研究でJungleに追加した、大まかな構成要素の概要を記述する。 +本章では、今回効率的な木の非破壊アップデートを可能にするために追加した機能である、 +Jungleの中で使用する非破壊赤黒木、Indexの差分アップデート、Differential Jungle Tree、Red Black Jungle Treeについて大まかな説明する。 + \section{非破壊 Red Black Treeの実装} JungleのIndexは、Java上で関数型プログラミングが行えるFunctional Java の非破壊 TreeMapを使って実装されていた。
--- a/master_paper.tex Sat Feb 11 19:04:30 2017 +0900 +++ b/master_paper.tex Sun Feb 12 01:51:51 2017 +0900 @@ -73,7 +73,6 @@ %要旨 \input{abstract.tex} -\input{abstract_eng.tex} %目次 \tableofcontents @@ -95,6 +94,7 @@ \input{redBlackJungleTree.tex} % 赤黒木の説明 \input{jungleTreeBrowser.tex} % Jungle Tree Brower \input{renderingEngine.tex} % Rendering Engine +\input{maTrix.tex} %maTrix \input{benchMark.tex} % \input{conclusion.tex}
--- a/renderingEngine.tex Sat Feb 11 19:04:30 2017 +0900 +++ b/renderingEngine.tex Sun Feb 12 01:51:51 2017 +0900 @@ -153,4 +153,4 @@ そのため、全てのノードを参照し、値を集める処理を行う必要があり、コードの可読性が下がり余計な処理も増えてしまう。 これより、Jungleの木構造を効率的に扱うためには、設計手法を確立する必要があることがわかった。 - +\newpage
--- a/result/createIndex.xbb Sat Feb 11 19:04:30 2017 +0900 +++ b/result/createIndex.xbb Sun Feb 12 01:51:51 2017 +0900 @@ -4,5 +4,5 @@ %%HiResBoundingBox: 0.000000 0.000000 792.000000 612.000000 %%PDFVersion: 1.3 %%Pages: 1 -%%CreationDate: Mon Feb 6 02:56:13 2017 +%%CreationDate: Sun Feb 12 01:31:39 2017
--- a/result/createListTree.xbb Sat Feb 11 19:04:30 2017 +0900 +++ b/result/createListTree.xbb Sun Feb 12 01:51:51 2017 +0900 @@ -4,5 +4,5 @@ %%HiResBoundingBox: 0.000000 0.000000 792.000000 612.000000 %%PDFVersion: 1.3 %%Pages: 1 -%%CreationDate: Mon Feb 6 02:56:13 2017 +%%CreationDate: Sun Feb 12 01:31:39 2017
--- a/result/createRedBlackTreeAndDefaultTreeTime.eps Sat Feb 11 19:04:30 2017 +0900 +++ b/result/createRedBlackTreeAndDefaultTreeTime.eps Sun Feb 12 01:51:51 2017 +0900 @@ -1,7 +1,7 @@ %!PS-Adobe-2.0 %%Title: createRedBlackTreeAndDefaultTreeTime.eps -%%Creator: gnuplot 5.0 patchlevel 2 -%%CreationDate: Wed Feb 1 08:58:26 2017 +%%Creator: gnuplot 5.0 patchlevel 5 +%%CreationDate: Sun Feb 12 01:27:37 2017 %%DocumentFonts: (atend) %%BoundingBox: 50 50 554 770 %%Orientation: Landscape @@ -468,11 +468,11 @@ SDict begin [ /Title (createRedBlackTreeAndDefaultTreeTime.eps) /Subject (gnuplot plot) - /Creator (gnuplot 5.0 patchlevel 2) + /Creator (gnuplot 5.0 patchlevel 5) /Author (e115731) % /Producer (gnuplot) % /Keywords () - /CreationDate (Wed Feb 1 08:58:26 2017) + /CreationDate (Sun Feb 12 01:27:37 2017) /DOCINFO pdfmark end } ifelse @@ -524,156 +524,145 @@ 1.000 UL LTb LCb setrgbcolor -686 448 M +602 448 M 63 0 V -6198 0 R +6282 0 R -63 0 V stroke -602 448 M +518 448 M [ [(Helvetica) 140.0 0.0 true true 0 ( 0)] ] -46.7 MRshow 1.000 UL LTb LCb setrgbcolor -686 1080 M +602 1080 M 63 0 V -6198 0 R +6282 0 R +-63 0 V +stroke +518 1080 M +[ [(Helvetica) 140.0 0.0 true true 0 ( 5)] +] -46.7 MRshow +1.000 UL +LTb +LCb setrgbcolor +602 1712 M +63 0 V +6282 0 R -63 0 V stroke -602 1080 M +518 1712 M +[ [(Helvetica) 140.0 0.0 true true 0 ( 10)] +] -46.7 MRshow +1.000 UL +LTb +LCb setrgbcolor +602 2344 M +63 0 V +6282 0 R +-63 0 V +stroke +518 2344 M +[ [(Helvetica) 140.0 0.0 true true 0 ( 15)] +] -46.7 MRshow +1.000 UL +LTb +LCb setrgbcolor +602 2975 M +63 0 V +6282 0 R +-63 0 V +stroke +518 2975 M [ [(Helvetica) 140.0 0.0 true true 0 ( 20)] ] -46.7 MRshow 1.000 UL LTb LCb setrgbcolor -686 1712 M +602 3607 M 63 0 V -6198 0 R +6282 0 R -63 0 V stroke -602 1712 M -[ [(Helvetica) 140.0 0.0 true true 0 ( 40)] -] -46.7 MRshow -1.000 UL -LTb -LCb setrgbcolor -686 2344 M -63 0 V -6198 0 R --63 0 V -stroke -602 2344 M -[ [(Helvetica) 140.0 0.0 true true 0 ( 60)] -] -46.7 MRshow -1.000 UL -LTb -LCb setrgbcolor -686 2975 M -63 0 V -6198 0 R --63 0 V -stroke -602 2975 M -[ [(Helvetica) 140.0 0.0 true true 0 ( 80)] +518 3607 M +[ [(Helvetica) 140.0 0.0 true true 0 ( 25)] ] -46.7 MRshow 1.000 UL LTb LCb setrgbcolor -686 3607 M +602 4239 M 63 0 V -6198 0 R +6282 0 R -63 0 V stroke -602 3607 M -[ [(Helvetica) 140.0 0.0 true true 0 ( 100)] +518 4239 M +[ [(Helvetica) 140.0 0.0 true true 0 ( 30)] ] -46.7 MRshow 1.000 UL LTb LCb setrgbcolor -686 4239 M +602 4871 M 63 0 V -6198 0 R +6282 0 R -63 0 V stroke -602 4239 M -[ [(Helvetica) 140.0 0.0 true true 0 ( 120)] +518 4871 M +[ [(Helvetica) 140.0 0.0 true true 0 ( 35)] ] -46.7 MRshow 1.000 UL LTb LCb setrgbcolor -686 4871 M -63 0 V -6198 0 R --63 0 V -stroke -602 4871 M -[ [(Helvetica) 140.0 0.0 true true 0 ( 140)] -] -46.7 MRshow -1.000 UL -LTb -LCb setrgbcolor -686 448 M +602 448 M 0 63 V 0 4360 R 0 -63 V stroke -686 308 M +602 308 M [ [(Helvetica) 140.0 0.0 true true 0 ( 0)] ] -46.7 MCshow 1.000 UL LTb LCb setrgbcolor -1730 448 M +1871 448 M 0 63 V 0 4360 R 0 -63 V stroke -1730 308 M -[ [(Helvetica) 140.0 0.0 true true 0 ( 500)] -] -46.7 MCshow -1.000 UL -LTb -LCb setrgbcolor -2773 448 M -0 63 V -0 4360 R -0 -63 V -stroke -2773 308 M -[ [(Helvetica) 140.0 0.0 true true 0 ( 1000)] +1871 308 M +[ [(Helvetica) 140.0 0.0 true true 0 ( 200)] ] -46.7 MCshow 1.000 UL LTb LCb setrgbcolor -3817 448 M +3140 448 M 0 63 V 0 4360 R 0 -63 V stroke -3817 308 M -[ [(Helvetica) 140.0 0.0 true true 0 ( 1500)] +3140 308 M +[ [(Helvetica) 140.0 0.0 true true 0 ( 400)] ] -46.7 MCshow 1.000 UL LTb LCb setrgbcolor -4860 448 M +4409 448 M 0 63 V 0 4360 R 0 -63 V stroke -4860 308 M -[ [(Helvetica) 140.0 0.0 true true 0 ( 2000)] +4409 308 M +[ [(Helvetica) 140.0 0.0 true true 0 ( 600)] ] -46.7 MCshow 1.000 UL LTb LCb setrgbcolor -5904 448 M +5678 448 M 0 63 V 0 4360 R 0 -63 V stroke -5904 308 M -[ [(Helvetica) 140.0 0.0 true true 0 ( 2500)] +5678 308 M +[ [(Helvetica) 140.0 0.0 true true 0 ( 800)] ] -46.7 MCshow 1.000 UL LTb @@ -684,7 +673,7 @@ 0 -63 V stroke 6947 308 M -[ [(Helvetica) 140.0 0.0 true true 0 ( 3000)] +[ [(Helvetica) 140.0 0.0 true true 0 ( 1000)] ] -46.7 MCshow 1.000 UL LTb @@ -692,11 +681,11 @@ 1.000 UL LTB LCb setrgbcolor -686 4871 N -686 448 L -6261 0 V +602 4871 N +602 448 L +6345 0 V 0 4423 V --6261 0 V +-6345 0 V Z stroke 1.000 UP 1.000 UL @@ -705,13 +694,13 @@ LCb setrgbcolor 112 2659 M currentpoint gsave translate -270 rotate 0 0 moveto -[ [(Helvetica) 140.0 0.0 true true 0 (time\(m\))] +[ [(Helvetica) 140.0 0.0 true true 0 (time\(ms\))] ] -46.7 MCshow grestore LTb LCb setrgbcolor -3816 98 M -[ [(Helvetica) 140.0 0.0 true true 0 (NodeCount)] +3774 98 M +[ [(Helvetica) 140.0 0.0 true true 0 (nodeCount)] ] -46.7 MCshow LTb % Begin plot #1 @@ -727,22 +716,17 @@ LCb setrgbcolor 6380 4738 M 399 0 V -686 638 M -417 1326 V -418 -473 V -417 31 V -418 -126 V -417 95 V -417 410 V -418 32 V -417 569 V -418 -127 V -417 190 V -417 474 V -418 94 V -417 632 V -418 -63 V -417 664 V +602 448 M +635 379 V +634 379 V +635 -126 V +634 884 V +635 127 V +634 379 V +635 253 V +634 252 V +635 506 V +634 885 V % End plot #1 % Begin plot #2 stroke @@ -759,22 +743,17 @@ LCb setrgbcolor 6380 4598 M 399 0 V -686 574 M -417 348 V -418 -95 V -417 -95 V -2356 606 L -417 0 V -417 0 V -418 0 V -417 0 V -418 0 V -417 0 V -417 63 V -418 -31 V -417 0 V -418 0 V -417 31 V +602 448 M +635 0 V +634 126 V +635 0 V +634 127 V +635 0 V +4409 574 L +635 0 V +634 0 V +635 253 V +6947 574 L % End plot #2 stroke 2.000 UL @@ -783,11 +762,11 @@ 1.000 UL LTB LCb setrgbcolor -686 4871 N -686 448 L -6261 0 V +602 4871 N +602 448 L +6345 0 V 0 4423 V --6261 0 V +-6345 0 V Z stroke 1.000 UP 1.000 UL
--- a/result/createRedBlackTreeAndDefaultTreeTime.xbb Sat Feb 11 19:04:30 2017 +0900 +++ b/result/createRedBlackTreeAndDefaultTreeTime.xbb Sun Feb 12 01:51:51 2017 +0900 @@ -1,8 +1,8 @@ %%Title: ./createRedBlackTreeAndDefaultTreeTime.pdf %%Creator: extractbb 20140317 -%%BoundingBox: 0 0 792 612 -%%HiResBoundingBox: 0.000000 0.000000 792.000000 612.000000 +%%BoundingBox: 0 0 612 792 +%%HiResBoundingBox: 0.000000 0.000000 612.000000 792.000000 %%PDFVersion: 1.3 %%Pages: 1 -%%CreationDate: Mon Feb 6 02:56:13 2017 +%%CreationDate: Sun Feb 12 01:31:39 2017
--- a/result/defaultJungleTreeCreateTime Sat Feb 11 19:04:30 2017 +0900 +++ b/result/defaultJungleTreeCreateTime Sun Feb 12 01:51:51 2017 +0900 @@ -1,16 +1,12 @@ -0 6 -200 48 -400 33 -600 34 -800 30 -1000 33 -1200 46 -1400 47 -1600 65 -1800 61 -2000 67 -2200 82 -2400 85 -2600 105 -2800 103 -3000 124 +0 0 +100 3 +200 6 +300 5 +400 12 +500 13 +600 16 +700 18 +800 20 +900 24 +1000 31 +
--- a/result/findTime.xbb Sat Feb 11 19:04:30 2017 +0900 +++ b/result/findTime.xbb Sun Feb 12 01:51:51 2017 +0900 @@ -4,5 +4,5 @@ %%HiResBoundingBox: 0.000000 0.000000 612.000000 792.000000 %%PDFVersion: 1.3 %%Pages: 1 -%%CreationDate: Mon Feb 6 02:56:13 2017 +%%CreationDate: Sun Feb 12 01:31:39 2017
--- a/result/redBlackTreeCreateTime Sat Feb 11 19:04:30 2017 +0900 +++ b/result/redBlackTreeCreateTime Sun Feb 12 01:51:51 2017 +0900 @@ -1,16 +1,11 @@ -0 4 -200 15 -400 12 -600 9 -800 5 -1000 5 -1200 5 -1400 5 -1600 5 -1800 5 -2000 5 -2200 7 -2400 6 -2600 6 -2800 6 -3000 7 +0 0 +100 0 +200 1 +300 1 +400 2 +500 2 +600 1 +700 1 +800 1 +900 3 +1000 1