\chapter{例題}
\label{chap:poordirection}

\section{ファイルの読み込みに関する例題}
テキストファイルをある一定のサイズに分割して読み込むプログラムである。このプログラムでは、pread という関数で実装した。
pread 関数は UNIX 標準に関するヘッダファイル、unistd.h に含まれている関数である。(表\ref{table:pread})
読み込んだテキストファイルはバッファに格納されるが、その格納先は TaskManager の API でメモリを確保する。
\begin{tiny}
  \begin{table}[ht]
    \begin{center}
      \label{table:pread}
      \small
        ssize\_t pread(int fd, void *buf, size\_t nbyte, off\_t offset);
      \begin{tabular}[t]{c|l}
        \hline
        int fd & 読み込むファイルディスクリプタ \\
        \hline
        void *buf & 予め用意したバッファへの書き込み \\
        \hline
        size\_t nbyte & 読み込むサイズ \\
        \hline
        off\_t offset& ファイルの先頭からのオフセット \\
        \hline
      \end{tabular}
      \caption{pread 関数の概要}
    \end{center}
  \end{table}
\end{tiny}

この例題の Task 生成部分を以下に示す。
\\
\begin{breakbox}
\begin{verbatim}
HTaskPtr read = manager->create_task(Read_task);
read->set_cpu(SPE_ANY);

read->set_param(0,(long)task_number);
read->set_param(1,(long)division_size);
if(read_left_size <= division_size){
    read->set_param(2,(long)left_size);
}else{
    read->set_param(2,(long)division_size);
}
read->set_param(3,(long)fd);

read->set_outData(0,read_text + task_number*division_size,
                                            division_size);
read->spawn();

read_left_size -= division_size;
task_number++;
\end{verbatim}
\end{breakbox}

read という Task を宣言し、Task に CPU Type、パラメータとして生成した Task 番号の task\_number
1つの Task の読み込み量 division\_size、読み込むファイルのファイルディスクリプタ fd を設定する。
読み込んだデータの格納先を set\_outData にて設定を行い、そして spawn にて Task を生成する。

Task が生成されると、division\_size分の読み込みを行ったということで、残りの読み込み量 read\_left\_size から division\_size を引き、そして task\_numberを増加させる。
この Task 生成部分は ファイルサイズ を division\_size で割った数だけ生成され、もし余りがあれば更に1加えた数になる。
その数が Read Task の数となり、その数だけループ処理を行う。
中盤にある if 文は、最後の Read Task かどうかで実際に読み込む量が決定される。

read Task の記述を以下に示す。
\\
\begin{breakbox}
\begin{verbatim}
static int
read_task(SchedTask *s, void *rbuf, void *wbuf)
{
    long task_number = (long)s->get_param(0);
    long division_size = (long)s->get_param(1);
    long read_size = (long)s->get_param(2);
    long fd = (long)s->get_param(3);

    char *read_text = (char*)s->get_output(wbuf,0);

    pread(fd, read_text, (long)read_size , division_size*task_number);
    return 0;
}
\end{verbatim}
\end{breakbox}
生成時に設定したデータ群を受け取り、それらのデータを pread の引数に渡す。読み込まれたファイルは read\_text に格納される。

ハードディスクに保存されている 10GB のテキストファイルを分割して読み込み終わるまでの時間を表\ref{table:preaddata}に示す。
分割サイズとは、1回の読み込み量である。
\begin{tiny}
  \begin{table}[ht]
    \begin{center}
      \label{table:preaddata}
      \small
      \begin{tabular}[t]{c|l}
        \hline
        分割サイズ & 読み込み速度(s)\\
        \hline
        16KB & 391.7 \\
        \hline
        16MB & 123.6 \\
        \hline
      \end{tabular}
      \caption{file read の実行結果}
    \end{center}
  \end{table}
\end{tiny}

分割サイズを大きくすると、pread の呼ばれる回数が少なくなるので読み込むことが速くなる。

\newpage

\section{ファイルに対して処理を行う例題}
読み込んだテキストファイルに対して文字列検索を行う例題として、力任せ法と Boyer-Moore String Search を実装した。
Boyer-Moore String Search は 1977 年に Robert S. Boyer と J Strother Moore が開発した効率的なアルゴリズムである。
なお、テキストファイルに含まれている文字列を text、検索する文字列を pattern と定義する。

\subsection{力任せ法}
力任せ法(総当り法とも呼ばれる)は、text と pattern を先頭から比較していき、
pattern と一致しなければ pattern を1文字分だけ後ろにずらして再度比較をしていくアルゴリズムである。
text の先頭から pattern の先頭を比較していき、文字の不一致が起きた場合は、
pattern を右に 1 つだけずらして、再度 text と pattern の先頭を比較していく。
(図\ref{fig:bruteforth})

\begin{figure}[htbp]
\begin{center}
\includegraphics[width=0.7\textwidth]{fig/bruteforth.pdf}
\end{center}
\caption{力まかせ法}
\label{fig:bruteforth}
\end{figure}

\newpage
このアルゴリズムは実装が簡単であり、pattern が text に含まれていれば必ず探しだすことができる。
しかし、text と pattern の文字数が大きくなるにつれて、比較回数も膨大になる恐れがある。
text の文字数を $n$、pattern の文字数を $m$とすると、力任せ法の最悪計算時間は $O(nm)$ となる。

\subsection{Boyer-Moore String Search Algorithm}
力任せ法の比較回数を改善したアルゴリズムが Boyer-Moore String Search である。
力任せ法との大きな違いとして、text と pattern を先頭から比較するのではなく、
pattern の末尾から比較していくことである。そして不一致が起こった場合は、
その不一致が起こった text の文字で再度比較する場所が決まる。

まず始めに、比較する場所を着目点とおく。図\ref{fig:bmsearchthink}の場合、
最初に比較する patternの末尾 と、それに対応する text を着目点とする。
(a)ではその着目点で不一致が起こっているので、それ以上比較しなくてもよいことがわかる。
不一致が起こった場合は (b) のように着目点をずらしていく。着目点を1つ右にずらして再度 pattern の末尾から比較していく。これを繰り返しをして、(d) のときに初めて一致することがわかる。

(a)のときに不一致を起こした text の文字に注目する。その文字が pattern に含まれていない文字であるならば、着目点を1つずらしても、2つずらしても一致することはない。pattern に含まれていない文字で不一致になった場合は、pattern の文字数分だけ着目点をずらすことができる。

\begin{figure}[htbp]
\begin{center}
\includegraphics[width=0.5\textwidth]{fig/bmsearchthink.pdf}
\end{center}
\caption{pattern に含まれていない文字で不一致になった場合}
\label{fig:bmsearchthink}
\end{figure}

\newpage

次に、pattern に含まれている文字で不一致になった場合を紹介する。
図\ref{fig:bmsearchthink}と同様に、文字を比較していく。
図\ref{fig:bmsearchinclude}(a)のときに不一致が起こる。
その時の text の文字列は pattern に含まれている。
この場合は着目点を右に2つずらすと text と pattern が一致する。
もし、pattern に含まれている文字で不一致になった場合は、その text の文字に注目する。
その文字を pattern 内から探し、その文字が pattern の末尾から
どれだけ離れているかで着目点を右にずらす量が決定される。
図\ref{fig:bmsearchinclude}の場合であれば、不一致時の文字が a であれば右に2つ、
b であれば右に1つずらすことができる。

\begin{figure}[htbp]
\begin{center}
\includegraphics[width=0.7\textwidth]{fig/bmsearchinlucde.pdf}
\end{center}
\caption{pattern に含まれている文字で不一致になった場合}
\label{fig:bmsearchinclude}
\end{figure}

\newpage

pattern に同じ文字が複数入り、その文字で不一致になった場合は図\ref{fig:bmsearchsame}のようになる。
この場合 a という文字が pattern の末尾から 1つ離れている箇所と 3 つ離れている箇所が存在する。
(a) のように、a で不一致が起こった場合は、着目点を右に1つか3つ移動できる。
しかし、着目点を右に3つずらしてしまうと、(b-1)のように text の途中にある "abac" という文字列を見逃してしまう。着目点を右に1つずらせば、(b-2)のように検索漏れを起こすことはなくなる。

このように、pattern に同じ文字が複数入っている場合は、末尾から一番近いほうを適用する。よって、図\ref{fig:bmsearchinclude}では、不一致時の文字が a であれば右に1つ、b であれば右に2つ着目点をずらすことができる。

\begin{figure}[htbp]
\begin{center}
\includegraphics[width=0.7\textwidth]{fig/bmsearchsame.pdf}
\end{center}
\caption{pattern に同じ文字が複数入り、その文字で不一致になった場合}
\label{fig:bmsearchsame}
\end{figure}


\newpage
pattern と text と不一致時の処理をまとめると、

\begin{itemize}
\item pattern に含まれていない文字の場合は、 pattern の長さだけ着目点を右にずらす
\item pattern に含まれている文字の場合は、 その文字が pattern の末尾から離れている分だけ着目点を右にずらす
\item pattern に含まれている文字かつ、その文字が pattern に複数含まれている場合は、 pattern の末尾から一番近い分だけ着目点を右にずらす
\end{itemize}

となる。 図\ref{fig:bmsearchbasic}の例であれば、不一致字の text の文字が a であれば着目点を 2つ、 b であれば 1つ、それ以外の文字列は3つずらすことができる。

\begin{figure}[htbp]
\begin{center}
\includegraphics[width=0.7\textwidth]{fig/bmsearchbasic.pdf}
\end{center}
\caption{Boyer-Moore Search String}
\label{fig:bmsearchbasic}
\end{figure}

\newpage
このように、Boyer-Moore Search String は、不一致が起こった時の text の文字によって着目点をずらすということが起こるので、
文字列検索を行う前に、着目点をずらす量を参照するための BMsearch skip table を作成する。
"doing" という pattern であれば、そのテーブルは図\ref{fig:bmskiptable1}となる。

\begin{figure}[htbp]
\begin{center}
\includegraphics[width=0.8\textwidth]{fig/bmskiptable1.pdf}
\end{center}
\caption{BMsearch skip table のまとめ}
\label{fig:bmskiptable1}
\end{figure}

このようなテーブルを、文字列検索を行う前に生成する必要がある。
そのテーブル生成プログラムは以下のようになる。
\\
\begin{breakbox}
\begin{verbatim}
static int*
create_BMskiptable(unsigned char *pattern,
                    int pattern_len,int *skip_table)
{
    for(int i = 0; i < 128; ++i){
        skip_table[i] = pattern_len;
    }

    for(int j = 0; j < pattern_len - 1; ++j){
        skip_table[pattern[j]] = pattern_len - j - 1;
    }

    return skip_table;
}
\end{verbatim}
\end{breakbox}
このソースでの 128 とは ASCII コード表における最大値である。
それぞれの文字に対して pattern の長さであるpattern\_lenを格納する。pattern が "doing" という文字列だと仮定すると、
pattern\_len = 5 となる。次に pattern の先頭から文字を調べる。
先頭の文字は d であり、d に対応する table に着目点をずらすための移動量を格納する。
移動量を格納したら、pattern の次の文字を調べ、そして移動量を格納していく。(図\ref{fig:bmskiptable})

\begin{figure}[htbp]
\begin{center}
\includegraphics[width=0.8\textwidth]{fig/bmskiptable.pdf}
\end{center}
\caption{skip table の 生成時の様子}
\label{fig:bmskiptable}
\end{figure}

\newpage
生成したテーブルを利用して文字列検索を行うアルゴリズムを以下に示す。
\\
\begin{breakbox}
\begin{verbatim}
int i = pattern_len - 1;
int match_counter = 0;

while ( i < text_len){
    int j = pattern_len - 1;
    while (text[i] == pattern[j]){
        if (j == 0){
            match_counter++;
        }
        --i;
        --j;
    }
    i = i + max(skip_table[text[i]],pattern_len - j);
}
\end{verbatim}
\end{breakbox}
読み込まれたテキストファイル text[i] と、検索文字列 pattern[j]を末尾から比較していく。
一致していれば参照する場所を先頭方向にずらしていき、先頭まで完全一致した場合は、
検索文字列を発見したということで、ここではマッチした数 match\_counter を増やしている。

もし途中で不一致が起こった場合は、その不一致が起こった時の text[i] の文字列か pattern の長さから j 引いたものの最大値の分だけ text の参照先をずらす。

\newpage
\subsection{ファイル分割時の処理の注意点}
この例題ではファイルを読み込んで一定の大きさでファイルを分割する。分割したものにそれぞれ文字列検索を行う。
それぞれの結果は pattern が含まれている個数が返ってくるので、最後に集計をして個数を表示する。このような一つ一つの処理を Task と呼ぶ。
図\ref{fig:includeiotask}では、ファイルの読み込みが File Read、分割したものに文字列検索を行うことが Run Tasks、
返した結果が Output Data、それぞれの結果の集計が Run resultTask に相当する。

\begin{figure}[htbp]
\begin{center}
\includegraphics[width=1.0\textwidth]{fig/includeiotask.pdf}
\end{center}
\caption{IO を含む Task}
\label{fig:includeiotask}
\end{figure}

\newpage

ファイルを分割したときに、分割される部分で pattern が含まれる場合が存在する。
その場合は、本来の読み込み部分の text の長さ $L$ に加えて、pattern の長さ $s$ だけ多く読みこむように設計することでこの問題は解決できる。
しかし、1 つの Search Task の text の長さが $L+s$ の場合だと、pattern が Search Task 1 に含まれ、Search Task 2 にも含まれてしまう。
(図\ref{fig:includeiotask})

\begin{figure}[htbp]
\begin{center}
\includegraphics[width=1.0\textwidth]{fig/iodivfail.pdf}
\end{center}
\caption{分割周りの処理・失敗時 (例:doing の検索)}
\label{fig:includeiotask}
\end{figure}

それを解決するために、1つの Search task の text の長さに pattern の長さを加えてから 1 引いた数だけ読み込むようにすればそのような問題は起こらない。よって、読み込むデータ量は $ L + s -1 $となる。

\begin{figure}[htbp]
\begin{center}
\includegraphics[width=1.0\textwidth]{fig/iodivsuc.pdf}
\end{center}
\caption{分割周りの処理・成功時 (例:doing の検索)}
\label{fig:includeiotask}
\end{figure}

\newpage

力任せ法と Boyer-Moore String Search を比較してみた。以下に実験環境と結果を示す。(表\ref{table:search})

\begin{itemize}
\item Mac OS X 10.9.1
\item 2*2.66 GHz 6-Core Intel Xeon
\item File Size 10GB
\end{itemize}

\begin{tiny}
  \begin{table}[ht]
    \begin{center}
      \label{table:search}
      \small
      \begin{tabular}[t]{c|r}
        \hline
        文字列検索アルゴリズム & 処理速度(s)\\
        \hline
        力任せ法 & 11.792 \\
        \hline
        Boyer-Moore String Search & 6.508 \\
        \hline
      \end{tabular}
      \caption{文字列検索アルゴリズムの比較}
    \end{center}
  \end{table}
\end{tiny}

Boyer-Moore String Search によって 44\% 改善した。