Mercurial > hg > Papers > 2012 > yutaka-master
annotate paper/chapter3.tex @ 3:181befc58e1d draft
add Prime explanation
author | Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp> |
---|---|
date | Thu, 09 Feb 2012 04:30:17 +0900 |
parents | 5dbcea03717e |
children | 20d87c5e225a |
rev | line source |
---|---|
1 | 1 \chapter{TaskManagerを使った例題} |
2 本章では、TaskManager を使った例題を紹介する | |
3 \section{WordCount} | |
4 例題としTaskManagerを使ったWordCountを実装した。Taskの構成は以下のである。 | |
5 \begin{enumerate} | |
6 \item WordCountTask | |
7 \item PrintTask | |
8 \end{enumerate} | |
9 WordCountTaskは、input された data を word count し、単語数と行数を output に指定された data 領域に書きこむTaskである。 | |
10 分割されたデータが送られてくるため、分割された前後のテキストがどうなっているかはわからない。そのため担当範囲であるデータの先頭と末尾のパラメータを単語数と行数の他に付け加える。後にそのデータを他のword count 結果と照らし合わせ、分割されたテキストを正しく整合する。 | |
11 PrintTask は WordCountTask によって書き出された単語数と行数を集計し、出力するTaskである。WordCountTask を wait する設定で、すべてのWordCountTaskが終了したあとに、動作する。 | |
12 word count 対象として入力されたファイルは、mmapを用いてメモリに展開する。その後データを16kbyteの大きさに分割しながら、WordCountTaskに割り当てていく。(\figref{wc-graf}) | |
0 | 13 |
1 | 14 \begin{figure}[htb] |
15 \begin{center} | |
16 \includegraphics[scale=0.70]{./images/wc_graf1.pdf} | |
17 \end{center} | |
18 \caption{wordcount flow} | |
19 \label{fig:wc-graf} | |
20 \end{figure} | |
0 | 21 |
1 | 22 |
23 \section{Sort} | |
3
181befc58e1d
add Prime explanation
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
1
diff
changeset
|
24 例題としてTaskManagerを使ったSortを実装した。Taskの構成は以下の通りである。 |
181befc58e1d
add Prime explanation
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
1
diff
changeset
|
25 \begin{enumerate} |
181befc58e1d
add Prime explanation
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
1
diff
changeset
|
26 \item QuickSortTask |
181befc58e1d
add Prime explanation
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
1
diff
changeset
|
27 \item SortSimpleTask |
181befc58e1d
add Prime explanation
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
1
diff
changeset
|
28 \end{enumerate} |
181befc58e1d
add Prime explanation
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
1
diff
changeset
|
29 指定された数の乱数を生成し、Sortする例題である。 |
181befc58e1d
add Prime explanation
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
1
diff
changeset
|
30 |
181befc58e1d
add Prime explanation
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
1
diff
changeset
|
31 |
1 | 32 |
33 \section{Prime} | |
3
181befc58e1d
add Prime explanation
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
1
diff
changeset
|
34 例題としてTaskManagerを使ったPrimeを実装した。Taskの構成は以下の通りである。 |
181befc58e1d
add Prime explanation
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
1
diff
changeset
|
35 \begin{enumerate} |
181befc58e1d
add Prime explanation
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
1
diff
changeset
|
36 \item PrimeTask |
181befc58e1d
add Prime explanation
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
1
diff
changeset
|
37 \item PrintTask |
181befc58e1d
add Prime explanation
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
1
diff
changeset
|
38 \end{enumerate} |
181befc58e1d
add Prime explanation
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
1
diff
changeset
|
39 PrimeTaskは、指示された範囲を素数判定し、渡された配列に結果を収めるTaskである。 |
181befc58e1d
add Prime explanation
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
1
diff
changeset
|
40 ミラー-ラビン素数判定法を用いて、2, 3, 5, 7 及び 11 について調べることで、2,152,302,898,747以下において決定的アルゴリズムにしている。 |
181befc58e1d
add Prime explanation
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
1
diff
changeset
|
41 % 参考文献 http://primes.utm.edu/prove/prove2_3.html |
181befc58e1d
add Prime explanation
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
1
diff
changeset
|
42 % Jaeschkeによる |
181befc58e1d
add Prime explanation
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
1
diff
changeset
|
43 PrintTaskは、PrimeTaskによって判定された素数を出力するTaskである。出力指示がされている場合のみ、素数を出力する。 |
1 | 44 |
45 |