Mercurial > hg > Papers > 2014 > toma-master
annotate paper/chapter3.tex @ 40:bd30d93097da
describe Jungle and Tree
| author | Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp> |
|---|---|
| date | Tue, 04 Feb 2014 04:41:52 +0900 |
| parents | ec3488a9ddd4 |
| children | 5b69636936cc |
| rev | line source |
|---|---|
| 10 | 1 \chapter{Haskellによる並列データベースの実装}\label{ch:impl} |
| 23 | 2 本章では、並列データベース Jungle の実装について述べる。 |
| 10 | 3 |
| 4 \section{木構造データベース Jungle} | |
| 23 | 5 非破壊的木構造データベース Jungle は、Haskell で実装された並列データベースである。 |
| 10 | 6 非破壊的木構造の方法に則ったAPIを提供する。 |
| 23 | 7 |
| 8 % 本研究では、HTTP サーバ Warp と組み合わせて掲示板システムとして利用しているが、他のシステムに組み込むことも可能である。 | |
| 9 Jungle の基本的な使い方の手順について説明する。 | |
| 10 \begin{enumerate} | |
|
40
bd30d93097da
describe Jungle and Tree
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
11 \item{木構造を保持する Jungle を作成する} |
| 23 | 12 \item{Jungle 内に新しい木を名前をつけて作成する} |
| 13 \item{木の名前を用いて、ルートノードの取得を行い、データを参照する} | |
| 14 \item{もしくは、木の名前を用いて、ルートノードの更新を行う} | |
| 15 \end{enumerate} | |
| 16 | |
|
40
bd30d93097da
describe Jungle and Tree
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
17 \subsubsection{Jungle が持つデータ型} |
|
bd30d93097da
describe Jungle and Tree
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
18 Jungle が持つのデータ型を表\ref{tab:components}に表す。 |
| 34 | 19 木構造の集まりを表現する Jungle、単体の木構造を表現する Tree がある。 |
| 20 Node は子と属性を任意の数持てる。 | |
|
40
bd30d93097da
describe Jungle and Tree
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
21 データ型として定義することで、データ内部の型の整合性が保たれ、また型検査でエラーがないか検出することができる。 |
|
bd30d93097da
describe Jungle and Tree
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
22 Jungle のデータ型について、ひとつずつ説明する。 |
| 35 | 23 |
| 34 | 24 \begin{table}[!htbp] |
| 25 \label{tab:components} | |
| 26 \begin{center} | |
| 27 \begin{tabular}{|c||c|} \hline | |
| 28 型名 & 概要 \\ \hline | |
| 29 Jungle & 木の作成・取得を担当する。 \\ \hline | |
| 30 Tree & 木の名前とルートノードの情報を保持している。 \\ \hline | |
| 31 Node & 基本的なデータ構造、子と属性を任意の数持てる。 \\ \hline | |
| 32 \end{tabular} | |
| 33 \end{center} | |
|
40
bd30d93097da
describe Jungle and Tree
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
34 \caption{Jungle が持つデータ型} |
| 34 | 35 \end{table} |
| 36 | |
|
40
bd30d93097da
describe Jungle and Tree
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
37 \subsection{Jungle} |
|
bd30d93097da
describe Jungle and Tree
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
38 Jungle は木構造の集まりを表現する。 |
|
bd30d93097da
describe Jungle and Tree
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
39 木には名前がついており、Tree の情報と一緒に保持している。 |
| 35 | 40 |
|
40
bd30d93097da
describe Jungle and Tree
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
41 \begin{lstlisting}[caption=Jungleのデータ型の定義] |
|
bd30d93097da
describe Jungle and Tree
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
42 data Jungle = Jungle { getJungleMap :: (TVar (Map String Tree)) } |
|
bd30d93097da
describe Jungle and Tree
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
43 \end{lstlisting} |
|
bd30d93097da
describe Jungle and Tree
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
44 |
|
bd30d93097da
describe Jungle and Tree
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
45 Jungle のデータ構造は、Jungle (TVar (Map String Tree)) である。 |
|
bd30d93097da
describe Jungle and Tree
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
46 getJungleMap :: というのは、Haskell のレコード構文である。 |
|
bd30d93097da
describe Jungle and Tree
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
47 |
|
bd30d93097da
describe Jungle and Tree
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
48 レコード構文は、データ構造へのアクセサを提供する。 |
|
bd30d93097da
describe Jungle and Tree
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
49 getJungleMap は関数で、以下のような型を持つ。 |
|
bd30d93097da
describe Jungle and Tree
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
50 これは、Jungleを受け取って、TVar (Map String Tree)を返す関数である。 |
|
bd30d93097da
describe Jungle and Tree
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
51 |
|
bd30d93097da
describe Jungle and Tree
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
52 レコード構文はデータ型を受け取って、:: の右側の型の値を取り出せる関数を作成すると思えば良い。 |
|
bd30d93097da
describe Jungle and Tree
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
53 |
|
bd30d93097da
describe Jungle and Tree
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
54 \begin{lstlisting}[caption=getJungleMap] |
|
bd30d93097da
describe Jungle and Tree
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
55 getJungleMap :: Jungle -> TVar (Map String Tree) |
|
bd30d93097da
describe Jungle and Tree
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
56 \end{lstlisting} |
|
bd30d93097da
describe Jungle and Tree
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
57 |
|
bd30d93097da
describe Jungle and Tree
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
58 Jungle の木の取り扱いには、Haskell の Data.Map を利用している。 |
|
bd30d93097da
describe Jungle and Tree
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
59 型名は、Map である。 |
|
bd30d93097da
describe Jungle and Tree
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
60 Map は、連想配列を扱うことのできるデータ構造である。 |
|
bd30d93097da
describe Jungle and Tree
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
61 平衡木を用いて、挿入や参照が O (log n)で済むように設計されている。 |
|
bd30d93097da
describe Jungle and Tree
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
62 Data.Mapを理解するためにはリストで考えると分かりやすい。 |
|
bd30d93097da
describe Jungle and Tree
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
63 |
|
bd30d93097da
describe Jungle and Tree
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
64 \begin{lstlisting}[caption=getJungleMap] |
|
bd30d93097da
describe Jungle and Tree
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
65 data Map k a = Map [(k,a)] |
|
bd30d93097da
describe Jungle and Tree
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
66 |
|
bd30d93097da
describe Jungle and Tree
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
67 lookup' :: Eq k => k -> Map k a -> Maybe a |
|
bd30d93097da
describe Jungle and Tree
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
68 lookup' k (Map []) = Nothing |
|
bd30d93097da
describe Jungle and Tree
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
69 lookup' k (Map ((k',a):xs)) = if k == k' |
|
bd30d93097da
describe Jungle and Tree
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
70 then Just a |
|
bd30d93097da
describe Jungle and Tree
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
71 else lookup k xs |
|
bd30d93097da
describe Jungle and Tree
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
72 |
|
bd30d93097da
describe Jungle and Tree
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
73 |
|
bd30d93097da
describe Jungle and Tree
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
74 insert :: k -> a -> Map k a -> Map k a |
|
bd30d93097da
describe Jungle and Tree
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
75 insert k a (Map x) = Map ((k,a):x) |
|
bd30d93097da
describe Jungle and Tree
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
76 |
|
bd30d93097da
describe Jungle and Tree
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
77 test = Map [("key","value"),("fizz","buzz")] |
|
bd30d93097da
describe Jungle and Tree
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
78 \end{lstlisting} |
|
bd30d93097da
describe Jungle and Tree
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
79 |
|
bd30d93097da
describe Jungle and Tree
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
80 Map は、キーと値のペアのリストだと考えることができる。 |
|
bd30d93097da
describe Jungle and Tree
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
81 キーが一致する値を探す場合、lookup'を用いる。 |
|
bd30d93097da
describe Jungle and Tree
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
82 Maybe モナドを用いて、データがなければ Nothing、データがあれば Just に包んで返す。 |
|
bd30d93097da
describe Jungle and Tree
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
83 $=>$ の前にある、Eq kは、型クラスの制約である。 |
|
bd30d93097da
describe Jungle and Tree
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
84 内部で k と k' の同値性をテストしているため、k は同値性をチェックできる型クラス Eq に属している型である必要がある。 |
|
bd30d93097da
describe Jungle and Tree
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
85 |
|
bd30d93097da
describe Jungle and Tree
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
86 新たにキーと値のペアを、Mapに追加するには insertを用いる。 |
|
bd30d93097da
describe Jungle and Tree
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
87 Haskell では、受け取った引数を変更することができないため、ペアを追加した新しい Map を返す。 |
|
bd30d93097da
describe Jungle and Tree
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
88 |
|
bd30d93097da
describe Jungle and Tree
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
89 |
|
bd30d93097da
describe Jungle and Tree
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
90 木の取り扱いには Haskell のソフトウェア・トランザクショナル・メモリ (STM) を利用して状態を持たせ、スレッド間で共有できるようにしてある。 |
|
bd30d93097da
describe Jungle and Tree
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
91 これは、各スレッドから木構造を新たに作成できるようにするためである。 |
|
bd30d93097da
describe Jungle and Tree
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
92 STM は、スレッド間でデータを共有するためのツールである。STM を利用することでロック忘れによる競合状態や、デッドロックといった問題から解放される。 |
|
bd30d93097da
describe Jungle and Tree
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
93 Jungle のデータ構造の Map の前に付いている TVar というのは、Transactional variablesの略で、STM で管理する変数に対して利用する。 |
| 34 | 94 |
| 23 | 95 \subsubsection{Jungle と木の作成} |
|
40
bd30d93097da
describe Jungle and Tree
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
96 Jungle は、Mapで木を管理しているため、複数の非破壊的木構造を持つことができる（図\ref{fig:jungle}）。 |
| 10 | 97 |
| 23 | 98 \begin{figure}[!htbp] |
| 99 \begin{center} | |
| 100 \includegraphics[scale=0.7]{./images/jungle.pdf} | |
| 101 \end{center} | |
| 102 \caption{複数の木を扱えるJungle} | |
| 103 \label{fig:jungle} | |
| 104 \end{figure} | |
| 10 | 105 |
|
40
bd30d93097da
describe Jungle and Tree
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
106 木構造の識別、つまり Map の キー にはString を利用する。 |
|
bd30d93097da
describe Jungle and Tree
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
107 String は Haskell の文字列の型で、Char のリスト [Char] の別名である。 |
|
bd30d93097da
describe Jungle and Tree
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
108 |
|
bd30d93097da
describe Jungle and Tree
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
109 Jungle を作成するには、createJungle を用いる。 |
|
bd30d93097da
describe Jungle and Tree
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
110 empty は空のMapを作成する関数である。 |
|
bd30d93097da
describe Jungle and Tree
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
111 |
|
bd30d93097da
describe Jungle and Tree
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
112 \begin{lstlisting}[caption=createJungle] |
|
bd30d93097da
describe Jungle and Tree
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
113 createJungle :: IO Jungle |
|
bd30d93097da
describe Jungle and Tree
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
114 createJungle = atomically $ do |
|
bd30d93097da
describe Jungle and Tree
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
115 map <- newTVar empty |
|
bd30d93097da
describe Jungle and Tree
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
116 return (Jungle map) |
|
bd30d93097da
describe Jungle and Tree
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
117 \end{lstlisting} |
|
bd30d93097da
describe Jungle and Tree
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
118 |
|
bd30d93097da
describe Jungle and Tree
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
119 \begin{lstlisting}[caption=STMの関数] |
|
bd30d93097da
describe Jungle and Tree
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
120 newTVar :: a -> STM (TVar a) |
|
bd30d93097da
describe Jungle and Tree
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
121 readTVar :: TVar a -> STM a |
|
bd30d93097da
describe Jungle and Tree
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
122 writeTVar :: TVar a -> a -> STM () |
| 23 | 123 |
|
40
bd30d93097da
describe Jungle and Tree
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
124 atomically :: STM a -> IO a |
|
bd30d93097da
describe Jungle and Tree
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
125 \end{lstlisting} |
|
bd30d93097da
describe Jungle and Tree
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
126 |
|
bd30d93097da
describe Jungle and Tree
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
127 createJungleは、新たにSTMの変数を作成する newTVar を実行する。 |
|
bd30d93097da
describe Jungle and Tree
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
128 newTVar などの STM の操作は STM モナド内で行う。 |
|
bd30d93097da
describe Jungle and Tree
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
129 最後にatomicallyを行うことで、do 構文内がトランザクションとして実行される。 |
|
bd30d93097da
describe Jungle and Tree
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
130 |
|
bd30d93097da
describe Jungle and Tree
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
131 atomically の隣にある \$ は関数適用演算子である。 |
|
bd30d93097da
describe Jungle and Tree
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
132 \$ 関数は最も低い優先順位を持っており、右結合である。 |
|
bd30d93097da
describe Jungle and Tree
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
133 括弧を減らすのに使う。\$ を使わない場合は以下の様に記述することになる。 |
|
bd30d93097da
describe Jungle and Tree
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
134 |
|
bd30d93097da
describe Jungle and Tree
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
135 \begin{lstlisting}[caption=STMの関数] |
|
bd30d93097da
describe Jungle and Tree
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
136 createJungle :: IO Jungle |
|
bd30d93097da
describe Jungle and Tree
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
137 createJungle = atomically (do |
|
bd30d93097da
describe Jungle and Tree
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
138 map <- newTVar empty |
|
bd30d93097da
describe Jungle and Tree
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
139 return (Jungle map)) |
|
bd30d93097da
describe Jungle and Tree
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
140 \end{lstlisting} |
|
bd30d93097da
describe Jungle and Tree
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
141 |
|
bd30d93097da
describe Jungle and Tree
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
142 createJungle は、IOを返すため使う際には main に関連付ける必要がある。 |
| 23 | 143 |
|
40
bd30d93097da
describe Jungle and Tree
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
144 \subsection{Tree} |
|
bd30d93097da
describe Jungle and Tree
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
145 Jungleが保持する木の情報は、内部的には Tree というデータ型で保持している。 |
|
bd30d93097da
describe Jungle and Tree
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
146 Tree は木の名前と、ルートノードの情報を持っている。 |
|
bd30d93097da
describe Jungle and Tree
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
147 実際にユーザがJungleを利用する際は、Jungle と木の名前を使ってルートノードを取ってくるため、Tree という構造は見えない。 |
|
bd30d93097da
describe Jungle and Tree
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
148 |
|
bd30d93097da
describe Jungle and Tree
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
149 ルートノードの情報はスレッド間で状態を共有する必要がある。 |
|
bd30d93097da
describe Jungle and Tree
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
150 スレッドセーフに取り扱う必要があるため、この情報も Haskell の ソフトウェア・トランザクショナル・メモリ (STM) を用いて管理している。 |
|
bd30d93097da
describe Jungle and Tree
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
151 |
|
bd30d93097da
describe Jungle and Tree
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
152 \begin{lstlisting}[caption=Treeのデータ型の定義] |
|
bd30d93097da
describe Jungle and Tree
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
153 data Tree = Tree |
|
bd30d93097da
describe Jungle and Tree
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
154 { rootNode :: (TVar Node) |
|
bd30d93097da
describe Jungle and Tree
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
155 , treeName :: String } |
|
bd30d93097da
describe Jungle and Tree
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
156 \end{lstlisting} |
|
bd30d93097da
describe Jungle and Tree
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
157 |
|
bd30d93097da
describe Jungle and Tree
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
158 新たな非破壊的木構造を作るには、createTree を用いる。 |
|
bd30d93097da
describe Jungle and Tree
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
159 createTree は、createJungleで作成した Jungle と木の名前を String で受け取る。 |
| 10 | 160 |
|
40
bd30d93097da
describe Jungle and Tree
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
161 \begin{lstlisting}[caption=createTree] |
|
bd30d93097da
describe Jungle and Tree
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
162 createTree :: Jungle -> String -> IO () |
|
bd30d93097da
describe Jungle and Tree
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
163 createTree (Jungle tmap) tree_name = atomically $ do |
|
bd30d93097da
describe Jungle and Tree
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
164 map <- readTVar tmap |
|
bd30d93097da
describe Jungle and Tree
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
165 tree <- emptyTree tree_name |
|
bd30d93097da
describe Jungle and Tree
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
166 writeTVar tmap (insert tree_name tree map) |
|
bd30d93097da
describe Jungle and Tree
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
167 |
|
bd30d93097da
describe Jungle and Tree
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
168 emptyTree :: String -> STM Tree |
|
bd30d93097da
describe Jungle and Tree
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
169 emptyTree tree_name = do |
|
bd30d93097da
describe Jungle and Tree
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
170 node <- newTVar emptyNode |
|
bd30d93097da
describe Jungle and Tree
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
171 return (Tree node tree_name) |
|
bd30d93097da
describe Jungle and Tree
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
172 |
|
bd30d93097da
describe Jungle and Tree
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
173 emptyNode :: Node |
|
bd30d93097da
describe Jungle and Tree
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
174 emptyNode = Node (empty) (empty) |
|
bd30d93097da
describe Jungle and Tree
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
175 \end{lstlisting} |
|
bd30d93097da
describe Jungle and Tree
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
176 |
|
bd30d93097da
describe Jungle and Tree
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
177 createJungleも STM を操作するため IOを返す。 |
|
bd30d93097da
describe Jungle and Tree
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
178 Jungle の持つ、tmapをreadTVarで取得し、複数の木構造を管理するためのMapを取得する。 |
|
bd30d93097da
describe Jungle and Tree
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
179 STM の変数をもった Tree を作成し、Map に insert する。 |
|
bd30d93097da
describe Jungle and Tree
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
180 writeTVar は更新する先の変数と、更新内容の2つを受け取る STM の関数である。 |
|
bd30d93097da
describe Jungle and Tree
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
181 |
|
bd30d93097da
describe Jungle and Tree
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
182 実際にcreateJungleとcreateTreeを使う時は以下のように記述する。 |
| 34 | 183 |
| 10 | 184 \begin{lstlisting}[caption=データベースと木の作成] |
|
40
bd30d93097da
describe Jungle and Tree
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
185 main = do |
|
bd30d93097da
describe Jungle and Tree
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
186 jungle <- createJungle |
|
bd30d93097da
describe Jungle and Tree
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
187 createTree jungle "name of new tree here" |
| 10 | 188 \end{lstlisting} |
| 189 | |
|
40
bd30d93097da
describe Jungle and Tree
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
190 |
| 10 | 191 \subsubsection{ルートノード} |
| 23 | 192 非破壊的木構造データベース Jungle では、木の最新の状態を更新・参照するのにルートノードを使う。 |
| 193 ルートノードは、最新の木構造の根がどれかの情報を保持している（図\ref{fig:getrootnode}）。 | |
| 194 | |
| 195 \begin{figure}[!htbp] | |
| 196 \begin{center} | |
| 197 \includegraphics[scale=0.7]{./images/get_root_node.pdf} | |
| 198 \end{center} | |
| 199 \caption{ルートノード} | |
| 200 \label{fig:getrootnode} | |
| 201 \end{figure} | |
| 202 | |
| 10 | 203 ルートノードに関する API を説明する。 |
| 204 | |
| 205 getRootNode は、最新のルートノードを取得できる。 | |
| 23 | 206 データベースと木の名前を渡すことで利用できる。 |
| 207 例えば、図\ref{fig:getrootnode}の状態の時は、B というルートノードが取得できる。 | |
| 10 | 208 |
| 209 \begin{lstlisting}[caption=最新のルートノードの取得] | |
| 34 | 210 getRootNode :: Jungle -> String -> IO Node |
|
40
bd30d93097da
describe Jungle and Tree
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
211 getRootNode (Jungle tmap) tree_name = atomically $ do |
|
bd30d93097da
describe Jungle and Tree
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
212 map <- readTVar tmap |
|
bd30d93097da
describe Jungle and Tree
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
213 readTVar (root_node map) |
|
bd30d93097da
describe Jungle and Tree
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
214 where |
|
bd30d93097da
describe Jungle and Tree
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
215 root_node map = case lookup tree_name map of |
|
bd30d93097da
describe Jungle and Tree
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
216 Just x -> rootNode x |
| 10 | 217 \end{lstlisting} |
| 218 | |
|
40
bd30d93097da
describe Jungle and Tree
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
219 まず、readTVarでJungleが持つmapを参照する。 |
|
bd30d93097da
describe Jungle and Tree
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
220 Haskell の where キーワードは、計算の中間結果に名前をつけるために用いられる。 |
|
bd30d93097da
describe Jungle and Tree
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
221 今回は、root\_node という map を受け取る関数を定義している。 |
|
bd30d93097da
describe Jungle and Tree
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
222 root\_node map では、Jungle が持つ Map をみて取得しようとしている名前の木構造があるかどうか調べている。 |
|
bd30d93097da
describe Jungle and Tree
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
223 木構造があった場合、rootNodeというTreeに定義されているレコード構文のアクセサ関数を使って、(TVar Node)を取得する。 |
|
bd30d93097da
describe Jungle and Tree
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
224 最後に、(TVar Node)に対して、readTVarを行うことで最新のルートノードが取得できる。 |
| 10 | 225 |
| 226 木構造を編集する API は全て Node を受け取って Node を返す。 | |
| 23 | 227 その返ってきた Node をルートノードとして登録することで、木構造の最新のルートノードが更新される。 |
|
40
bd30d93097da
describe Jungle and Tree
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
228 updateRootNode は、データベースと木の名前、変更して返ってきた木構造の 3 つを渡す。 |
| 23 | 229 updateRootNodeをした後は、getRootNodeで取得できるルートノードが更新された状態になっている。 |
| 10 | 230 |
| 231 \begin{lstlisting}[caption=ルートノードの更新] | |
| 34 | 232 updateRootNode :: Jungle -> String -> Node -> IO () |
|
40
bd30d93097da
describe Jungle and Tree
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
233 updateRootNode (Jungle tmap) tree_name node = |
|
bd30d93097da
describe Jungle and Tree
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
234 atomically $ do |
|
bd30d93097da
describe Jungle and Tree
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
235 map <- readTVar tmap |
|
bd30d93097da
describe Jungle and Tree
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
236 writeTVar (root_node map) node |
|
bd30d93097da
describe Jungle and Tree
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
237 where |
|
bd30d93097da
describe Jungle and Tree
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
238 root_node map = case M.lookup tree_name map of |
|
bd30d93097da
describe Jungle and Tree
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
239 Just x -> rootNode x |
|
bd30d93097da
describe Jungle and Tree
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
240 \end{lstlisting} |
| 34 | 241 |
|
40
bd30d93097da
describe Jungle and Tree
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
242 updateRootNodeWithは、ノードを更新する関数とデータベース、木の名前を渡して利用する。 |
|
bd30d93097da
describe Jungle and Tree
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
243 ノードを更新する関数とは、ノードを受け取ってノードを返す関数である。(Node -> Node) がそれにあたる。 |
|
bd30d93097da
describe Jungle and Tree
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
244 このupdateRootNodeWithを利用することで、getRootNodeをした後に編集しupdateRootNodeを行う一連の操作がatomicallyに行われることが保証される。 |
|
bd30d93097da
describe Jungle and Tree
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
245 |
|
bd30d93097da
describe Jungle and Tree
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
246 \begin{lstlisting}[caption=ルートノードの更新] |
|
bd30d93097da
describe Jungle and Tree
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
247 updateRootNodeWith :: (Node -> Node) -> Jungle -> String -> IO () |
|
bd30d93097da
describe Jungle and Tree
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
248 updateRootNodeWith f (Jungle tmap) tree_name = |
|
bd30d93097da
describe Jungle and Tree
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
249 atomically $ do |
|
bd30d93097da
describe Jungle and Tree
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
250 map <- readTVar tmap |
|
bd30d93097da
describe Jungle and Tree
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
251 n <- readTVar (root_node map) |
|
bd30d93097da
describe Jungle and Tree
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
252 writeTVar (root_node map) (f n) |
|
bd30d93097da
describe Jungle and Tree
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
253 where |
|
bd30d93097da
describe Jungle and Tree
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
254 root_node map = case M.lookup tree_name map of |
|
bd30d93097da
describe Jungle and Tree
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
255 Just x -> rootNode x |
|
bd30d93097da
describe Jungle and Tree
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
256 \end{lstlisting} |
|
bd30d93097da
describe Jungle and Tree
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
257 |
|
bd30d93097da
describe Jungle and Tree
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
258 並列データベース Jungle で、他のスレッドと状態を共有する操作は、 |
|
bd30d93097da
describe Jungle and Tree
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
259 createJungle、createTree、getRootNode、updateRootNode、updateRootNodeWith |
|
bd30d93097da
describe Jungle and Tree
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
260 で全てである。 |
|
bd30d93097da
describe Jungle and Tree
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
261 並列データベース Jungle では、なるべく状態を共有しないようにすることで並列実行時の性能の向上を実現する。 |
|
bd30d93097da
describe Jungle and Tree
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
262 ソフトウェアトランザクショナルメモリは書き込み時に他から変更があった場合にやり直しという操作はあるものの、読み込みに関してはロックなしで高速に読み込める。 |
|
bd30d93097da
describe Jungle and Tree
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
263 |
|
bd30d93097da
describe Jungle and Tree
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
264 \subsection{Node} |
|
bd30d93097da
describe Jungle and Tree
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
265 Node は木構造を表現するデータ構造である。 |
|
bd30d93097da
describe Jungle and Tree
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
266 再帰的に定義されている。 |
|
bd30d93097da
describe Jungle and Tree
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
267 各ノードは Children としてノードを複数持つことができる（図\ref{fig:node_components}）。 |
|
bd30d93097da
describe Jungle and Tree
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
268 |
|
bd30d93097da
describe Jungle and Tree
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
269 \begin{figure}[!htbp] |
|
bd30d93097da
describe Jungle and Tree
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
270 \begin{center} |
|
bd30d93097da
describe Jungle and Tree
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
271 \includegraphics[width=110mm]{./images/node_component.pdf} |
|
bd30d93097da
describe Jungle and Tree
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
272 \end{center} |
|
bd30d93097da
describe Jungle and Tree
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
273 \caption{Nodeの構成要素} |
|
bd30d93097da
describe Jungle and Tree
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
274 \label{fig:node_components} |
|
bd30d93097da
describe Jungle and Tree
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
275 \end{figure} |
|
bd30d93097da
describe Jungle and Tree
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
276 |
|
bd30d93097da
describe Jungle and Tree
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
277 Children および Attributes も Data.Map を用いて定義されている（ソースコード \ref{src:node}）。 |
|
bd30d93097da
describe Jungle and Tree
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
278 |
|
bd30d93097da
describe Jungle and Tree
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
279 \begin{lstlisting}[label=src:node, caption=Nodeのデータ型の定義] |
|
bd30d93097da
describe Jungle and Tree
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
280 data Node = Node |
|
bd30d93097da
describe Jungle and Tree
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
281 { children :: (Map Int Node) |
|
bd30d93097da
describe Jungle and Tree
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
282 , attributes :: (Map String ByteString) } |
| 10 | 283 \end{lstlisting} |
| 284 | |
| 35 | 285 \newpage |
|
40
bd30d93097da
describe Jungle and Tree
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
286 |
| 10 | 287 |
|
40
bd30d93097da
describe Jungle and Tree
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
35
diff
changeset
|
288 \newpage |
| 10 | 289 |
| 290 \subsubsection{木の編集} | |
| 291 木の編集には、Node を使う。 | |
| 292 木の編集に用いる API は全て Node を受け取って Node を返す。 | |
| 293 非破壊的木構造を利用しているため、getRootNode などで取得してきた Node は他のスレッドと干渉することなく自由に参照、編集できる。 | |
| 294 これらの編集のためのAPIは、編集後updateRootNodeするか、ひとつの関数にまとめてupdateRootNodeWithをすることで木構造に反映させることができる。 | |
| 295 | |
| 296 編集対象のノードを指定するには、NodePath を利用する。 | |
| 297 NodePath は、ルートノードからスタートし、ノードの子どもの場所を次々に指定したものである。 | |
| 298 Haskell の基本データ構造であるリストを利用している。 | |
| 299 | |
| 300 | |
| 301 \begin{figure}[!htbp] | |
| 302 \begin{center} | |
| 303 \includegraphics[width=100mm]{./images/nodepath.pdf} | |
| 304 \end{center} | |
| 305 \caption{NodePath} | |
| 306 \label{fig:nodepath} | |
| 307 \end{figure} | |
| 308 | |
| 309 addNewChildAt で、ノードに新しい子を追加できる。 | |
| 310 addNewChildAt には、Node と NodePath を渡す。 | |
| 311 子には Position という場所の情報があるが、インクリメントしながら自動的に指定される。 | |
| 23 | 312 |
| 10 | 313 \begin{lstlisting}[caption=子の追加] |
| 34 | 314 addNewChildAt :: Node -> Path -> Node |
| 315 | |
| 10 | 316 new_node = addNewChildAt node [l,2] |
| 317 \end{lstlisting} | |
| 318 | |
| 319 deleteChildAt で、ノードの子を削除できる。 | |
| 320 deleteChildAt には、Node と NodePath、削除したい子のPositionを指定する。 | |
| 23 | 321 |
| 10 | 322 \begin{lstlisting}[caption=子の削除] |
| 34 | 323 deleteChildAt :: Node -> Path -> Position -> Node |
| 324 | |
| 10 | 325 new_node = deleteChildAt node [1,2] 0 |
| 326 \end{lstlisting} | |
| 327 | |
| 328 putAttribute で、ノードに属性を追加できる。 | |
| 329 putAttribute には、Node と NodePath、Key、Valueを渡す。 | |
| 330 Key は String、 Value は、ByteString である。 | |
| 23 | 331 |
| 10 | 332 \begin{lstlisting}[caption=属性の追加] |
| 34 | 333 putAttribute :: Node -> Path -> String -> ByteString -> Node |
| 334 | |
| 10 | 335 new_node = putAttribute node [1,2] "key" "value" |
| 336 \end{lstlisting} | |
| 337 | |
| 338 deleteAttribute で、ノードの属性を削除できる。 | |
| 339 deleteAttribute には、Node と NodePath、Keyを渡す。 | |
| 23 | 340 |
| 10 | 341 \begin{lstlisting}[caption=属性の削除] |
| 34 | 342 deleteAttribute :: Node -> Path -> String -> Node |
| 343 | |
| 10 | 344 new_node = deleteAttribute node [1,2] "key" |
| 345 \end{lstlisting} | |
| 346 | |
| 347 | |
| 348 \subsubsection{木の参照} | |
| 349 木の参照にも Node を用いる。 | |
| 350 様々な参照の API があるため、ひとつずつ紹介していく。 | |
| 351 | |
| 352 getAttributes は、対象の Path に存在する属性を Key を用いて参照できる。 | |
| 23 | 353 |
| 10 | 354 \begin{lstlisting}[caption=属性の取得] |
| 34 | 355 getAttributes :: Node -> Path -> String -> Maybe ByteString |
| 356 | |
| 10 | 357 bytestring = getAttributes node [1,2] "key" |
| 358 \end{lstlisting} | |
| 2 | 359 |
| 10 | 360 あるNodeに存在する全ての子に対して、参照を行いたい場合に利用する。 |
| 361 getChildren は、対象の Node が持つ全ての子を Node のリストとして返す | |
| 23 | 362 |
| 10 | 363 \begin{lstlisting}[caption=対象のNodeの全ての子を取得] |
| 34 | 364 getChildren :: Node -> Path -> [Node] |
| 365 | |
| 10 | 366 nodelist = getChildren node [1,2] |
| 367 \end{lstlisting} | |
| 368 | |
| 369 あるNodeに存在する全ての子に対して、参照を行いたい場合に利用する。 | |
| 370 getChildren と違い、子のPositionも取得できる。 | |
| 371 assocsChildren は、対象の Node が持つ全ての子を Position とのタプルにし、そのタプルのリストを返す。 | |
| 23 | 372 |
| 10 | 373 \begin{lstlisting}[caption=対象のNodeの全ての子とPositionを取得] |
| 34 | 374 assocsChildren :: Node -> Path -> [(Int, Node)] |
| 375 | |
| 10 | 376 nodelist = assocsChildren node [1,2] |
| 377 \end{lstlisting} | |
| 378 | |
| 379 あるNodeに存在する全ての属性に対して、参照を行いたい場合に利用する。 | |
| 380 assocsAttribute は、対象の Node が持つ全ての属性を、Key と Value のタプルとし、そのタプルのリストを返す。 | |
| 23 | 381 |
| 10 | 382 \begin{lstlisting}[caption=対象のNodeの全てのAttributeのKeyとValueを取得] |
| 34 | 383 assocsAttribute :: Node -> Path -> [(String, B.ByteString)] |
| 384 | |
| 10 | 385 attrlist = assocsAttribute node [1,2] |
| 386 \end{lstlisting} | |
| 387 | |
| 388 numOfChild では、対象の Node が持つ子どもの数を取得できる。 | |
| 23 | 389 |
| 10 | 390 \begin{lstlisting}[caption=対象のNodeの子どもの数を取得] |
| 34 | 391 numOfChild :: Node -> Path -> Int |
| 392 | |
| 10 | 393 num = numOfChild node [1,2] |
| 394 \end{lstlisting} | |
| 395 | |
| 396 currentChild では、対象の Node が持つ最新の子を取得できる。 | |
| 23 | 397 |
| 10 | 398 \begin{lstlisting}[caption=対象のNodeの最新の子を取得] |
| 34 | 399 currentChild :: Node -> Path -> Maybe Node |
| 400 | |
| 10 | 401 node = currentChild node [1,2] |
| 402 \end{lstlisting} | |
| 403 | |
| 23 | 404 \subsubsection{並列実行} |
| 405 木構造データベース Jungle は、並列に実行することができる。 | |
| 406 アプリケーション側で、データベースを参照や変更する際に各スレッドから呼び出しても問題ない。 | |
| 407 利用方法も、シングルスレッドで実行する場合と同じである。 | |
| 408 | |
| 409 \clearpage | |
| 10 | 410 |
| 411 | |
| 23 | 412 \clearpage |
|
20
ff03e6179f19
describe the design.
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
10
diff
changeset
|
413 \section{Haskellの並列処理} |
|
ff03e6179f19
describe the design.
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
10
diff
changeset
|
414 純粋関数型言語 Haskell は並列処理に向いていると言われる。 |
|
ff03e6179f19
describe the design.
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
10
diff
changeset
|
415 しかしながら、安直にそう言い切ることはできない。 |
|
ff03e6179f19
describe the design.
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
10
diff
changeset
|
416 参照透過性があるため、各々の関数の処理は独立している。 |
|
ff03e6179f19
describe the design.
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
10
diff
changeset
|
417 そのため、並列で走らせても問題ないように思われるが、Haskell は遅延評価を行うため問題が発生する。 |
| 23 | 418 遅延評価では、結果が必要になるまで評価されない。 |
| 419 実装においては、deepseqを用いて即時評価を挟むか、出力など計算が必要となる処理を挟むようにする。 | |
|
20
ff03e6179f19
describe the design.
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
10
diff
changeset
|
420 |
|
ff03e6179f19
describe the design.
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
10
diff
changeset
|
421 Haskellでは、様々な並列化手法が提供されている。 |
| 23 | 422 スレッドを直接操作することも可能である。 |
| 423 | |
|
20
ff03e6179f19
describe the design.
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
10
diff
changeset
|
424 本研究では、抽象度の高い Eval モナドを利用した。 |
| 23 | 425 Eval モナドを利用することで、並列処理のために必要な処理の流れを分かりやすく記述することができた。 |
| 426 しかしながら Eval モナドは実行順序を細かく制御することはできない。 | |
|
20
ff03e6179f19
describe the design.
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
10
diff
changeset
|
427 Par モナドを利用すれば、並列処理の流れを細かく記述できるが、 |
|
ff03e6179f19
describe the design.
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
10
diff
changeset
|
428 Eval モナドのように処理と並列処理の流れを分けて記述し、後からプログラムに並列処理を組み込むというようなことはできない。 |
|
ff03e6179f19
describe the design.
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
10
diff
changeset
|
429 |
|
ff03e6179f19
describe the design.
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
10
diff
changeset
|
430 Haskellで並列処理を実装する場合は、どの並列化手法を採用するかということをよく考察する必要がある。 |
|
ff03e6179f19
describe the design.
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
10
diff
changeset
|
431 |
| 10 | 432 \section{Haskell の生産性} |
| 433 Java を用いた Jungle の実装と比較して、コード行数が約 3000 行から約 300 行へと短くなった。 | |
| 434 | |
| 435 これは Haskell の表現力が高いためである。 | |
| 23 | 436 Haskell では、独自のデータ型を簡単に作成することができる。 |
| 10 | 437 再帰的なデータ構造の定義も容易である。 |
| 438 共通の性質を扱うための型クラスという仕組みが存在し、既存のライブラリを作成したデータ型に利用できる。 | |
| 439 また、Haskellは参照透過性を持つため、コードの再利用が行い易く、関数同士の結合も簡単である。 | |
| 440 | |
| 441 同じような機能を実装する場合でも、Java と比較してコード行数が短くなり生産性が向上する。 |