Mercurial > hg > Papers > 2014 > toma-master
diff paper/chapter3.tex @ 60:79d168016df4
add memorize
author | Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp> |
---|---|
date | Tue, 11 Feb 2014 22:58:43 +0900 |
parents | 0a8d66c9ccd1 |
children | d11f4c6c7657 |
line wrap: on
line diff
--- a/paper/chapter3.tex Tue Feb 11 19:45:40 2014 +0900 +++ b/paper/chapter3.tex Tue Feb 11 22:58:43 2014 +0900 @@ -16,7 +16,7 @@ \subsubsection{Jungle が持つデータ型} 非破壊的木構造データベース Jungle が持つのデータ型を表\ref{tab:components}に表す. -また, データ型内部のデータ構造を\ref{tab:components2}に表す. +また, データ型内部のデータ構造を表\ref{tab:components2}に表す. 木構造の集まりを表現する Jungle, 単体の木構造を表現する Tree がある. Node は子と属性を任意の数持てる. @@ -25,7 +25,6 @@ 非破壊的木構造データベース Jungle のデータ型について, ひとつずつ説明する. \begin{table}[!htbp] -\label{tab:components} \begin{center} \begin{tabular}{|c||c|c|} \hline 型名 & 概要 \\ \hline @@ -34,11 +33,12 @@ Node & 基本的なデータ構造, 子と属性を任意の数持てる. \\ \hline \end{tabular} \end{center} +\label{tab:components} \caption{Jungle が持つデータ型} \end{table} -\begin{table}[!htbp] -\label{tab:components2} +\newpage +\begin{table}[htbp] \begin{center} \begin{tabular}{|c||c|} \hline 型名 & データ構造 \\ \hline @@ -47,10 +47,12 @@ Node & Node (Map Int Node) (Map String ByteString) \\ \hline \end{tabular} \end{center} +\label{tab:components2} \caption{データ型のデータ構造} \end{table} -\subsection{Jungle} +\clearpage +\section{Jungle} Jungle は木構造の集まりを表現する. 木には名前がついており, Tree の情報と一緒に保持している(ソースコード\ref{src:jungle}). @@ -75,9 +77,9 @@ 型名は, Map である. Map は, 連想配列を扱うことのできるデータ構造である. 平衡木を用いて, 挿入や参照が O (log n)で済むように設計されている. -Data.Mapを理解するためにはリストで考えると分かりやすい. +Data.Mapを理解するためにはリストで考えると分かりやすい(ソースコード\ref{src:map_list}). -\begin{lstlisting}[caption=getJungleMap] +\begin{lstlisting}[label=src:map_list, caption=リストで定義した場合のMap] data Map k a = Map [(k,a)] lookup' :: Eq k => k -> Map k a -> Maybe a @@ -102,7 +104,6 @@ 新たにキーと値のペアを, Mapに追加するには insertを用いる. Haskell では, 受け取った引数を変更することができないため, ペアを追加した新しい Map を返す. - 木の取り扱いには Haskell のソフトウェア・トランザクショナル・メモリ (STM) を利用して状態を持たせ, スレッド間で共有できるようにしてある. これは, 各スレッドから木構造を新たに作成できるようにするためである. STM は, スレッド間でデータを共有するためのツールである. STM を利用することでロック忘れによる競合状態や, デッドロックといった問題から解放される. @@ -147,7 +148,7 @@ atomically :: STM a -> IO a \end{lstlisting} -atomically の隣にある \$ は関数適用演算子である. +ソースコード\ref{src:createJungle}の atomically の隣にある \$ は関数適用演算子である. \$ 関数は最も低い優先順位を持っており, 右結合である. 括弧を減らすのに使う. \$ を使わない場合はソースコード\ref{src:dollar}の様に記述することになる. @@ -160,7 +161,8 @@ createJungle は, IOを返すため使う際には main に関連付ける必要がある. -\subsection{Tree} +\clearpage +\section{Tree} Jungleが保持する木の情報は, 内部的には Tree というデータ型で保持している. Tree は木の名前と, ルートノードの情報を持っている(ソースコード\ref{src:tree}). 実際にユーザがJungleを利用する際は, Jungle と木の名前を使ってルートノードを取ってくるため, Tree という構造は見えない. @@ -226,7 +228,7 @@ 例えば, 図\ref{fig:getrootnode}の状態の時は, B というルートノードが取得できる. -getRootNode 関数の定義を示す(\ref{src:getrootnode}). +getRootNode 関数の定義を示す(ソースコード\ref{src:getrootnode}). まず, readTVarでJungleが持つmapを参照する. Haskell の where キーワードは, 計算の中間結果に名前をつけるために用いられる. 今回は, root\_node という map を受け取る関数を定義している. @@ -249,7 +251,7 @@ updateRootNode は, データベースと木の名前, 変更して返ってきた木構造の 3 つを渡す. updateRootNodeをした後は, getRootNodeで取得できるルートノードが更新された状態になっている. -updateRootNode 関数の定義を示す(\ref{src:updaterootnode}). +updateRootNode 関数の定義を示す(ソースコード\ref{src:updaterootnode}). getRootNodeと同じように, Treeの(TVar Node)を取得し, 最後にwriteTVarを用いて更新している. \begin{lstlisting}[label=src:updaterootnode, caption=ルートノードの更新] @@ -266,7 +268,8 @@ updateRootNodeWithは, ノードを更新する関数とデータベース, 木の名前を渡して利用する. ノードを更新する関数とは, ノードを受け取ってノードを返す関数である. (Node $->$ Node) がそれにあたる. このupdateRootNodeWithを利用することで, getRootNodeをした後に編集しupdateRootNodeを行う一連の操作が分断されずに行われることが保証される. -updateRootNode 関数の定義を示す(\ref{src:updaterootnodewith}). + +updateRootNodeWith 関数の定義を示す(ソースコード\ref{src:updaterootnodewith}). updateRootNodeWithでは, 一連の操作を分断せずに行うためにreadTVarからwriteTVarまで同じ STM モナド内で行っている. atomicallyに関数にdo構文で繋げたSTMモナドを渡すことで, このブロックがトランザクションとして実行される. @@ -288,7 +291,8 @@ 並列データベース Jungle では, なるべく状態を共有しないようにすることで並列実行時の性能の向上を実現する. ソフトウェアトランザクショナルメモリは書き込み時に他から変更があった場合にやり直しという操作はあるものの, 読み込みに関してはノンブロッキングで高速に読み込める. -\subsection{Node} +\clearpage +\section{Node} Node は木構造を表現するデータ構造である. 再帰的に定義されている. 各ノードは children として子ノードを複数持つことができる(図\ref{fig:node_components}). @@ -358,6 +362,7 @@ これらの関数は, ほぼ同一の関数で定義できる. addNewChildAtを用いて説明する(ソースコード\ref{src:addNewChildAt}). +\newpage \begin{lstlisting}[label=src:addNewChildAt, caption=木の編集を行う関数] addNewChildAt :: Node -> Path -> Node addNewChildAt parent [] = addChildAt parent emptyNode @@ -444,10 +449,10 @@ pos = size map \end{lstlisting} -参照関数の基本的な流れは、getNode関数を使って参照したいPathのノードを取ってくることである. -そのノードにはwhereキーワードを利用して、targetという名前をつけている. -targetに対して、子のMapや属性のMapを取得した後、lookup関数などを適用する. -elems, assocs, sizeなどはData.Mapの参照関数で、Jungle ではその関数をそのまま利用している. +参照関数の基本的な流れは, getNode関数を使って参照したいPathのノードを取ってくることである. +そのノードにはwhereキーワードを利用して, targetという名前をつけている. +targetに対して, 子のMapや属性のMapを取得した後, lookup関数などを適用する. +elems, assocs, sizeなどはData.Mapの参照関数で, Jungle ではその関数をそのまま利用している. 参照関数の基本的な機能をまとめて説明する.