\documentclass[twocolumn,twoside,9.5pt]{jarticle}
\usepackage[dvipdfmx]{graphicx}
\usepackage{picins}
\usepackage{ascmac}
\usepackage{fancyhdr}
\usepackage{here}
%\pagestyle{fancy}
\lhead{\parpic{\includegraphics[height=1zw,keepaspectratio,bb=0 0 251 246]{pic/emblem-bitmap.pdf}}琉球大学主催 工学部情報工学科 中間発表予稿}
\rhead{}
\cfoot{}

\setlength{\topmargin}{-1in \addtolength{\topmargin}{15mm}}
\setlength{\headheight}{0mm}
\setlength{\headsep}{5mm}
\setlength{\oddsidemargin}{-1in \addtolength{\oddsidemargin}{11mm}}
\setlength{\evensidemargin}{-1in \addtolength{\evensidemargin}{21mm}}
\setlength{\textwidth}{181mm}
\setlength{\textheight}{261mm}
\setlength{\footskip}{0mm}
\pagestyle{empty}

\begin{document}
\title{UnityにおけるJungleDBの有用性}
\author{135768K 武田和馬 {}{} 指導教員 : 河野真治}
\date{}
\maketitle
\thispagestyle{fancy}

\section{非破壊木構造データベース}

当研究室ではデータの変更の際に過去の木構造を保存する非破壊木構造データベースであるJungleを開発している\cite{1}。

本研究ではJungleをUnityを用いたネットワークゲームで使用する方法を提案する。
データベースとしてJungle DBをC\#で再実装を行い、Unity向けに組み込みを行う。

Jugnleの木は、子供を複数持つノードからなる。子供は順序付けられており、任意の位置で作成削除することができる。
ノードは属性名と属性値の組からなる表を持つ。

\section{UnityでのDBの取り扱い}

Unityは3Dゲームエンジンで、ゲームを構成する要素(Object)をC\#で制御する。
Objectは一つのゲームのシーン(一画面の状況)の中で木構造を持つ。
これをシーングラフと言う。
シーングラフをそのままJungleに格納するという手法が考えられる。

JungleはJavaで書かれていたので、Unityで使うにはJungleをC\#で実装する必要がある。
クライアント側はC\#、サーバー側はJavaで動作するJungleを用いる。
Jungleの分散機構を用いてネットワークゲームに必要な通信を行う。
通信はMessagePackを基本に実装されている。
従って、C\#側でもMessagePackを用いてデータのやり取りを行いたい。

図\ref{fig:clienttree}のようにクライアント側では2つのTreeを持っている。
GameTreeからCommunityTreeにコピーする。
サーバー側とはCommunityTreeで同期する。

図\ref{fig:servertree}のようにサーバー側ではPlayerごとにTreeを持っている。

\begin{figure}[h]
\includegraphics[width=2cm, bb=0 0 172 200]{pic/clientTree.pdf}
\label{fig:clienttree}
\captation{クライアント側の木構造}
\end{figure}

\begin{figure}[h]
\includegraphics[width=2cm, bb=0 0 172 200]{pic/serverTree.pdf}
\label{fig:servertree}
\captation{サーバー側の木構造}
\end{figure}

Unityではデータの保存の際にSQlite3、PlayerPrefsといったDBがよく使われている。
PlayerPrefsとは、Unityに特化したバイナリ形式でKey,Valueのみで保存されるものである。
これらのDBにはObjectを直接格納することはできない。
また、セーブ機能に特化していてメモリ上にDBを展開するものではない。

\section{Jungle-Sharpの実装}

%スムーズにできた部分を書く
%Jungleがプログラミング言語に依存しないものだというのをかくほうがいい
JavaとC\#はよく似た言語であり、移行はそれほど難しくはない。
実際Jungleの中心部分である木構造とIndexを構成する赤黒木\cite{2}のコードはほぼ変更なく移行できた。
C\#ではインナークラスが使えないので明示的なクラスに変換する必要があった。

異なる部分は一つは木を変更した後、木のルートをAtomicに置き部分である。
もう一つは木をたどる時に使うItertorである。

%\section{AtomicRefefarenceの実装}
% atomic reference問題
Jungleの木の更新(commit)は、CAS(check and setを用いて atomic に行われる。競合している書き込みにの中で自分の書き込みが成功した場合に関数 \verb+success()+が成功する。
JavaにはAtomicRefarenceが標準であるがC\#はなかったため、AtomicReferenceのClassを新たに作った。

\begin{itembox}[l]{AtomicReplace}
\begin{verbatim}
// C#  
public bool CompareAndSet(T newValue, T prevValue) {
    T oldValue = value;
    return (oldValue 
        != Interlocked.CompareExchange (ref value, newValue, prevValue));
}

// Java

\end{verbatim}
\end{itembox}

%\section{Listの実装}
木やリストをたどる時にJavaではIteratorを用いる。
Iteratorは次の値があるかを返すboolean hasNext()と、Tという型の次の値を取ってくるT next()を持つObjectである。
C\#では木やリストをたどりながらyeildで次の値を返す。

\begin{itembox}[l]{List.java}
\begin{verbatim}
public Iterator<T> iterator() {
  return new Iterator<T>() {
    Node<T> currentNode = head.getNext();

    @Override
    public boolean hasNext() {
      return currentNode.getAttribute() 
                                    != null;
    }

    @Override
    public T next() {
      T attribute 
            = currentNode.getAttribute();
      currentNode 
            = currentNode.getNext();
      return attribute;
    }
  };
}
\end{verbatim}
\end{itembox}

C\#にはIEnumeratorがあるのでそれを利用した。
ListのforeachではIteratorを呼び出すため、一つずつ要素を返す必要がある。
yield returnステートメントを利用することで位置が保持され、次に呼ばれた際に続きから値の取り出しが可能になる。

\begin{itembox}[l]{List.cs}
\begin{verbatim}
public IEnumerator<T> iterator() {
  Node<T> currentNode = head.getNext();
  while (currentNode.getAttribute() != null) {
    yield return (T)currentNode.getAttribute();
    currentNode = currentNode.getNext ();
  }
}
\end{verbatim}
\end{itembox}

\section{ベンチマーク}

UnityではSqlite3,PlayerPrefsがデータの保存として利用される。
今回の検証はInsertを1000回行い、push(またはSave)を行うまでの時間を測定する。

使用した機材は以下の通りである。

\begin{itemize}
\item OS : Windows 10
\item CPU : Intel Core i7-4700MQ 2.4GHz
\item Unity : 5.4.2f1
\end{itemize}

%\begin{figure}[htbp]
%    \includegraphics[width=70mm]{pic/benchmark.pdf}
%\end{figure}
\begin{table}[htbp]
  \caption{速度測定}
  \label{table:data_type}
  \begin{tabular}{lcrr} \hline
  データベース & 速度(ms) \\ \hline \hline
  Jungle & 100 \\
  Sqlite3 & 100 \\
  PlayerPrefs & 100 \\
  \end{tabular}
\end{table}

Jungleが早い理由として赤黒木を使っている、データを書き出さずメモリ上にデータを持っているからである。
Sqlite3が遅い理由としてはデータをInsertする毎にDBを書き込みを行っているからである。
PlayerPrefsはデータを書き出すが、データをセットしたのち一度だけまとめて書き出すため早い。

\section{これからの作業}

Jungleは分散型のデータベースを目指しているため、MessagePackの実装を行う。
今後はサーバーとの連携も行う。
JungleはRDBと異なりデータを自由に格納することができる。
そこでデータベース設計を確立させる必要がある。

\begin{thebibliography}{9}

\bibitem{1}
金川竜己 非破壊的木構造データベースJungleとその評価
\end{thebibliography}

\bibitem{2}
: {これで分かった赤黒木}, {http://www.moon.sannet.ne.jp/okahisa/rb-tree/}
\end{thebibliography}


\end{document}