# HG changeset patch
# User Kazuma Takeda
# Date 1486728796 -32400
# Node ID 7313ae32fa21efa1f1e45f0a614914ce97cf3c5f
# Parent  9bffc31de0e61ee0616f127de78b200e78943908
Fix Code Frame, and Rewrite Summary.

diff -r 9bffc31de0e6 -r 7313ae32fa21 paper/main.pdf
Binary file paper/main.pdf has changed
diff -r 9bffc31de0e6 -r 7313ae32fa21 paper/main.tex
--- a/paper/main.tex	Fri Feb 10 15:14:48 2017 +0900
+++ b/paper/main.tex	Fri Feb 10 21:13:16 2017 +0900
@@ -102,7 +102,7 @@
 
 \section{Jungleの提案}
 
-非破壊的木構造データベースのJungleを提案している\cite{1}。
+非破壊的木構造データベースのJungleを提案している\cite{jungle}。
 Jungleはスケーラビリティのあるデータベースとして開発している。
 
 ウェブサイトの構造は大体が木構造であるため、データ構造として木構造を採用している。
@@ -196,13 +196,16 @@
 
 以下にルートノードの2番目の子どもを取ってくるのEitherのサンプルコードを記述する。
 
-\begin{lstlisting}[frame=lrbt,numbers=left,label=getAttributeCode]
+\begin{itembox}[l]{SaveData.cs}
+\scriptsize{
+\begin{verbatim}
 Either<Error,TreeNode> either = children.at(2);
 if (either.isA()) 
     return either.a();
 TreeNode child = either.b();
-\end{lstlisting}
-
+\end{verbatim}
+}
+\end{itembox}
 
 \section{ChildrenとAttribute}
 
@@ -256,10 +259,10 @@
 変数{\tt path}で指定した場所にある、ノードの子供の変数{\tt pos}で指定した位置子ノードを追加する\\ \hline
 {\tt Either<Error, JungleTreeEditor> deleteChildAt( NodePath path, int pos)}      &
 変数{\tt path}で指定した場所にある、ノードの子供の変数{\tt pos}で指定した位置の子ノードを削除する。 \\ \hline
-{\tt Either<Error, JungleTreeEditor> putAttribute( NodePath path, string key,　byte[] value)} &
-変数{\tt path}で指定した場所にあるノードに、属性名 変数{\tt key} 属性値 変数{\tt value} のペアで値を挿入する。 \\ \hline
+{\tt Either<Error, JungleTreeEditor> putAttribute( NodePath path, string key,　object value)} &
+変数{\tt path}で指定した場所にあるノードに、属性名 変数{\tt key} 属性値 変数{\tt value}で値を挿入する。 \\ \hline
 {\tt Either< Error, JungleTreeEditor> deleteAttribute( NodePath path, string key)}&
-変数{\tt path}で指定した場所にあるノードが持つ、属性名 変数{\tt key}とペアで保存されているデータを削除する。\\ \hline
+変数{\tt path}で指定した場所にあるノードが持つ、属性名 変数{\tt key}で保存されているデータを削除する。\\ \hline
 {\tt Either<Error, JungleTreeEditor> commit()}  &
 木へ行った変更をコミットする。自分が編集を行っていた間に、他のJungleTreeEditorクラスによって木が更新されていた場合、コミットは失敗する。 \\ \hline
 \end{tabular}
@@ -336,7 +339,7 @@
 
 \section{AtomicRefarenceの実装}
 
-Jungleの木の変更(commit)はCAS(Check and Set)を用いてatomicに行われる。競合している書き込み中に自分の書き込みが成功した場合に関数\verb+success()+が成功する。
+Jungleの木の変更(commit)はCAS(Check and Set)を用いてatomicに行われる。競合している書き込み中に自分の書き込みが成功した場合に関数\verb+commit()+が成功する。
 
 JavaではAtomicRefarenceが標準であるがC\#にはなかったためAtomicRefarenceのクラスを新たにつくった。
 
@@ -438,19 +441,20 @@
 }
 \end{itembox}
 
-Eitherをチェックしつつデータを格納する例を以下に記述する。
+bindでのEitherをチェックしつつデータを格納する例を以下に記述する。
 
-% サンプルのコードを簡単なものに変更
+%図を入れてもいいかも？
+
 \begin{itembox}[l]{DataSaveTest.cs}
 \scriptsize{
 \begin{verbatim}
-System.Collection.Generic.List<BoxItemInfo> infoList = new System.Collection.Generic.List<BoxItemInfo> ();
-    infoList.Add (new BoxItemInfo (1, 2, "Grass", "#019540FF"));
-    infoList.Add (new BoxItemInfo (2, 4, "Wood", "#7F3C01FF"));
-    infoList.Add (new BoxItemInfo (3, 1, "Sand", "#D4500EFF"));
-    infoList.Add (new BoxItemInfo (4, 5, "Water", "#2432ADFF"));
+    List<Item> info = new List<Item> ();
+    info.Add (new Item ("Sword"));
+    info.Add (new Item ("Shield"));
+    info.Add (new Item ("Bow"));
+    info.Add (new Item ("Boomerang"));
 
-    foreach (var info in infoList.Select((v, i) => new {v, i})) {
+    foreach (var info in info.Select((v, i) => new {v, i})) {
       either = either.bind ((JungleTreeEditor arg) => {
         return arg.addNewChildAt (path, info.i);
       });
@@ -463,7 +467,7 @@
 }
 \end{itembox}
 
-bindの実装により、ユーザ側がErrorのチェックする必要がなくなる。
+bindの実装により、ユーザ側がEitherのErrorチェックを行う必要がなくなる。
 
 
 \chapter{Unityで実装したアプリケーション}
@@ -473,7 +477,7 @@
 \section{例題ゲーム}
 
 本論文ではC\#で再実装を行ったJungleをUnityで作られたゲームの上に構築する。
-例題のゲームとしては図\ref{craft}に記載した、マインクラフトの簡易版を作成する。
+例題のゲームとしては図\ref{craft}に記載した、マインクラフト\cite{minecraft}の簡易版を作成する。
 
 \begin{figure}[h]
 \begin{center}
@@ -580,7 +584,6 @@
 \scriptsize{
 \begin{verbatim}
 Player player = attr.get<Player> ("Player");
-
 Enemy enemy = attr.get ("Enemy") as Enemy;
 \end{verbatim}
 }
@@ -597,49 +600,140 @@
 \section{Javaとの比較}
 
 本論文ではJavaで書かれたJungle DatabaseをC\#で再実装した。
-同じオペレーションでJavaとC\#で計測する。オペレーションは以下に記述する。
+同じオペレーションでJavaとC\#で計測する。
 なお、1回目の処理はキャッシュを作り処理が遅くなるため、計測は行わず、2回目以降から行う。
 
-%% これは変更する必要がある
-%% この例題はわかりにくい!!!
-\begin{itembox}[l]{Benchmark.cs}
+計測時に使用したデータ挿入のオペレーションを以下に記述する。
+
+% 単一のベンチマーク
+\begin{itembox}[l]{BenchMarkmark.cs}
 \scriptsize{
 \begin{verbatim}
-public JungleTreeEditor createTree(JungleTreeEditor editor, int _curY, int _maxHeight, NodePath path) {
-
-    if (_curY == _maxHeight) {
-      return editor;
-    }
-
-    for (int i = 0; i < 3; i++) {
-      Either<Error, JungleTreeEditor> either = editor.addNewChildAt (path, _curY);
-      DebugCommon.Assert (either.isA (), "Error");
-      editor = either.b ();
-      string value = path.add (_curY).ToString ();
-      either = editor.putAttribute (path.add (_curY), key, System.Text.Encoding.ASCII.GetBytes (value));
-      DebugCommon.Assert (either.isA (), "Error");
-      editor = either.b ();
-      string value2 = value + "+ index";
-      either = editor.putAttribute (path.add (_curY), indexKey, System.Text.Encoding.ASCII.GetBytes (value2));
-      DebugCommon.Assert (either.isA (), "Error");
-      editor = either.b ();
-      editor = createTree (editor, _curY + 1, _maxHeight, path);
-    }
-    return editor;
-  }
+for (int i = 0; i < trial; i++) {
+  Either<Error, JungleTreeEditor> either = edt.addNewChildAt (path, i);
+  either = either.bind ((JungleTreeEditor arg) => {
+    return arg.putAttribute ("name", "Kazuma");
+  });
+}
 \end{verbatim}
 }
 \end{itembox}
 
+計測に使用したマシンの環境を記述する。
+
+\begin{table}[htb]
+\begin{center}
+\caption{計測環境}
+\begin{tabular}{|p{14em}|p{14em}|}        \hline
+OS          & 
+Mac OS Sierra 10.12.3 \\ \hline
+Memory      &
+8 GB 2133 MHz LPDDR3  \\ \hline
+CPU         &
+2.9 GHz Intel Core i5 \\ \hline
+Java        &
+1.8.0111              \\ \hline
+.NET Runtimes (MonoDevelop-Unity) &
+Mono 4.0.5            \\ \hline
+.NET Runtimes (Xamarin) &
+Mono 4.6.2            \\ \hline
+\end{tabular}
+\label{itembox}
+\end{center}
+\end{table}
+
 %% データの図を入れる
 
+計測結果を図\ref{BenchMark}に示す。
+
+\begin{figure}[h]
+\begin{center}
+\includegraphics[height = 6cm , bb=0 0 568 455]{images/BenchMarkmark.pdf}
+\caption{BenchMark}
+\label{BenchMark}
+\end{center}
+\end{figure}
+
+Jungleの挿入の計算量はO(Log n)が期待される。
+図\ref{BenchMark}より、Unityで実行した結果ではO(n)となっている。
+Unityではレンダリングの機能も兼ねている。
+そのためプログラムを実行している間もレンダリングを行っているため、
+純粋なPutAttributeの計算時間ではないと考えられる。
+
+XamarinはC\#の性能を確認するために実行した。
+結果として見るとJavaに比べてC\#が早い。
+
+% なんでか？みたいなお話
+% プリミティブ型？データ型？
+% Javaは純粋オブジェクト指向言語ではないから？
+% if文が遅い？
+% Lambda式だから早い？ - いや遅い気がする
 
 \section{SQLite3とPlayerPrefsとの比較}
 
 Unityで使われているデータ保存としてSQLite3とPlayerPrefsがある。
-それぞれに対し、データの格納を行い、計測する。
+それぞれに対し、データの格納を100回行い、測定する。
+
+以下にJungle、SQLite3、PlayerPrefsでのデータ挿入を行うサンプルコードを記述する。
+
+% 単一のベンチマーク
+\begin{itembox}[l]{BenchMarkmark.cs}
+\scriptsize{
+\begin{verbatim}
+
+// Jungle
+for (int i = 0; i < TrialCount; i++) {
+    either.bind ((JungleTreeEditor arg) => {
+      return arg.putAttribute (rootPath ,"Player_" + i, HP);
+    });
+}
+
+either.bind ((JungleTreeEditor arg) => {
+    return arg.commit();
+});
+
+// SQLite3
+for (int i = 0; i < TrialCount; i++) {
+    sql.ExecuteNonQuery ("insert into player values("+ i + "," + HP + " )");
+}
 
-%% データの図を入れる/
+// PlayerPrefs
+for (int i = 0; i < TrialCount; i++) {
+    PlayerPrefs.SetInt ("Player_" + i, HP);
+}
+PlayerPrefs.Save ();
+\end{verbatim}
+}
+\end{itembox}
+
+Jungleは挿入後、\tt{commit()}を行うまでを挿入とする。
+
+PlayerPrefsは\tt{Save()}を行うとバイナリに書き出される。
+そこまでを挿入とする。
+
+計測結果を以下に記述する。
+
+\begin{table}[htb]
+\begin{center}
+\caption{実行結果}
+\begin{tabular}{|p{14em}|p{14em}|} \hline
+Jungle       & 
+12.217ms     \\ \hline
+SQLite3      &
+126.265ms    \\ \hline
+PlayerPrefs  &
+985.131ms    \\ \hline
+\end{tabular}
+\label{itembox}
+\end{center}
+\end{table}
+
+Jungleはデータを直接プログラム内部、つまりオンメモリに持っている。
+そのため通信を行わずにデータのやり取りができる。
+
+SQLite3ではデータを挿入のSQLを実行するたびデータベースとの通信を行うため遅くなっている。
+PlayerPrefsはデータをまとめてセットすることができる。
+しかし、バイナリ形式で保存されるため、書き出す時間がかかってしまう。
 
 \chapter{結論}
 \section{まとめ}
@@ -647,8 +741,24 @@
 本論文ではJungleDatabaseをC\#で再実装を行った。
 JavaとC\#は比較的似ている言語であるため移行は難しくはなかった。
 
-Jungleはオンメモリで動作する。
-その為SQLite3やPlayerPrefsよりも速く動作する。
+性能としてもJava版に劣らない、もしくはそれ以上のパフォーマンスを出せる。
+Eitherでのbindの実装で、より関数型プログラミングを意識しながら記述することができる。
+これはJava版にはない実装である。
+
+Jungle DatabaseはもともとWeb向けに作られたデータベースである。
+Webではリニアにデータが書き換わることは多くない。
+しかしゲームでは扱うデータが多くリニアに書き換わる。
+
+そのため、Jungleの構成は保ちつつ、ゲームに合わせたJungleの拡張を行った。
+データの格納の際にByteBufferであったものをObject型に変更した。
+これにより、シーンを構成するObjectを手間なく格納することを可能にした。
+
+Jungleは非破壊であるため、過去の変更を持っている。
+ゲームにおいて過去の木を持ち続けることはパフォーマンスの低下につながる。
+そのため、過去の木をどこまで必要かを検討しなければならない。
+
+現在C\#版のJungleにはデータを永続化させる仕組みは備わっていない。
+実用的なゲームのデータベースとして使うためには永続化を実装する必要がある。
 
 %\section{Alice での実装}
 
diff -r 9bffc31de0e6 -r 7313ae32fa21 paper/reference.bib
--- a/paper/reference.bib	Fri Feb 10 15:14:48 2017 +0900
+++ b/paper/reference.bib	Fri Feb 10 21:13:16 2017 +0900
@@ -1,13 +1,13 @@
-@Misc{rfbprotocol,
-  author = "{RICHARDSON, T., AND LEVINE, J.}",
-  title = "The remote framebuffer protocol. RFC 6143",
-  month = "mar",
-  year = 2011
+@Misc{minecraft,
+  author = "MicroSoft",
+  howpublished = "\url{https://minecraft.net/ja-jp/}"
 }
 
-@Misc{tightvnc,
-  author       = "{TightVNC Software}",
-  howpublished = "\url{http://www.tightvnc.com}"
+@Misc{jungle,
+  author       = "Shoshi Tamaki and Seiyu Tani and Shinji Kono",
+  title = "Cassandraを使ったスケーラビリティのあるCMSの設計",
+  year = 2011,
+  journal = "情報処理学会システムソフトウェアとオペレーティング・システム研究会",
 }
 
 @Misc{vnc,