Mercurial > hg > Papers > 2016 > masa-master

changeset 56:49526135ba64

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
remove
author Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
date Sun, 14 Feb 2016 02:16:29 +0900
parents 64ba0ae4c169
children 4efa1c7604f5
files c4.tex c5.tex images/regex/cfab.bb images/regex/cfab.pdf images/regex/cfdg.bb images/regex/cfdg.pdf images/regex/cfdgab.bb images/regex/cfdgab.pdf images/regex/efgi.bb images/regex/efgi.pdf master_paper.pdf memo/result.txt
diffstat 12 files changed, 240 insertions(+), 149 deletions(-) [+]
line wrap: on
line diff
--- a/c4.tex	Fri Feb 12 15:00:13 2016 +0900
+++ b/c4.tex	Sun Feb 14 02:16:29 2016 +0900
@@ -1,5 +1,5 @@
 \chapter{Cerium による文字列処理の例題}
-本項ではファイルを読み込んで処理する流れとそれの例題を記述する。例題として、単語数を数える Word Count、文字列探索を行う Boyer Moore Search、正規表現を挙げる。
+本項ではファイルを読み込んで処理する流れとそれの例題を記述する。例題として、単語数を数える Word Countとファイルからあるパターンを検索する正規表現を挙げる。
 
 \section{文字列処理の並列処理}
 文字列処理を並列で処理する場合を考える。
@@ -15,9 +15,9 @@
   \caption{File 読み込みから処理までの流れ}
   \label{fig:dividefile}
 \end{figure}
-File 分割時に分割された部分の整合性についてはそれぞれの例題にて述べる。
 
-
+ファイルを分割したときに、分割された部分でそれぞれの例題の整合性が取れなくなってしまうことがある。
+整合性の取り方についてはそれぞれの例題にて述べる。
 
 \section{Word Count}
 Word Count は読み込んだテキストに対して単語数を数える処理である。
@@ -53,99 +53,6 @@
 
 \newpage
 
-\section{Boyer-Moore String Search}
-
-読み込んだテキストファイルに対してある特定の文字列検索を行う例題として、Boyer-Moore String Search が挙げられる。
-Boyer-Moore String Search は 1977 年に Robert S. Boyer と J Strother Moore が開発した効率的なアルゴリズムである。\cite{bmsearch}
-
-以下、テキストファイルに含まれている文字列を text、検索する文字列を pattern と定義する。
-
-原始的な検索アルゴリズムとして力任せ法が挙げられる。
-力任せ法は text と pattern を先頭から比較していき、
-pattern と一致しなければ pattern を1文字分だけ後ろにずらして再度比較をしていくアルゴリズムである。
-text の先頭から pattern の先頭を比較していき、文字の不一致が起きた場合は pattern を後ろに 1 つだけずらして再比較を行う。
-(図\ref{fig:bruteforth})
-
-\begin{figure}[htbp]
-\begin{center}
-\includegraphics[width=0.7\textwidth]{images/example/bruteforth.pdf}
-\end{center}
-\caption{力まかせ法}
-\label{fig:bruteforth}
-\end{figure}
-
-\newpage
-このアルゴリズムは実装が容易であるが、 text と pattern の文字数が大きくなるにつれて、比較回数も膨大になる恐れがある。
-text の長さを $n$、pattern の長さを $m$とすると、力任せ法の最悪計算時間は $O(nm)$ となる。
-
-力任せ法の比較回数を改善したアルゴリズムが Boyer-Moore String Search である。
-力任せ法との大きな違いとして、text と pattern を先頭から比較するのではなく、 pattern の末尾から比較していくことである。
-さらに不一致が起こった場合は、その不一致が起こった text の文字で再度比較する場所が決まる。
-
-図\ref{fig:bmsearchthink}は、text と pattern の末尾が不一致を起こして、そのときの text が pattern に含まれていない場合である。
-不一致した text の文字が pattern に含まれていない場合は、pattern を比較する場所に match することはないので、pattern の長さ分だけ後ろにずらすことができる。
-
-\begin{figure}[htbp]
-\begin{center}
-\includegraphics[width=0.7\textwidth]{images/example/bmsearchthink.pdf}
-\end{center}
-\caption{pattern に含まれていない文字で不一致になった場合}
-\label{fig:bmsearchthink}
-\end{figure}
-
-\newpage
-
-図\ref{fig:bmsearchinclude} は不一致が起こったときの text の文字が pattern に含まれている場合である。
-この場合は pattern を後ろに2つずらすと text と pattern が一致する。
-
-不一致したときの text の文字が pattern に含まれていた場合の後ろにずらす量は、pattern の長さから含まれていた文字が pattern の何文字目に含まれているかを引いた値となる。
-この場合、pattern の文字列の長さは 3 で text で不一致を起こした文字 `a' が pattern の 1 文字目に含まれているので、2 文字分だけ後ろにずらすことができる。
-
-\begin{figure}[htbp]
-\begin{center}
-\includegraphics[width=0.7\textwidth]{images/example/bmsearchinlucde.pdf}
-\end{center}
-\caption{pattern に含まれている文字で不一致になった場合}
-\label{fig:bmsearchinclude}
-\end{figure}
-
-\newpage
-
-図\ref{fig:bmsearchsame} は不一致が起こったときの text の文字が pattern に含まれ、その不一致文字が pattern に複数含まれている場合である。
-
-pattern の長さは 4 で、不一致を起こした時の text の文字 `a' は pattern の 1 番目と 3 番目に含まれている。
-pattern を後ろにずらす量は 1 か 3 となる。
-ずらす量を 3 にすると、pattern が含まれている text を見逃す可能性があるので、この場合 `a' で不一致したときは最小の値 1 をとる。
-
-\begin{figure}[htbp]
-\begin{center}
-\includegraphics[width=0.7\textwidth]{images/example/bmsearchsame.pdf}
-\end{center}
-\caption{pattern に同じ文字が複数入り、その文字で不一致になった場合}
-\label{fig:bmsearchsame}
-\end{figure}
-
-pattern と text と不一致時の処理をまとめると、
-
-\begin{itemize}
-\item pattern に含まれていない文字で不一致した場合は、 pattern の長さだけ後ろにずらす。
-\item pattern に含まれている文字の場合は、pattern の長さから pattern に含まれている文字の位置を引いた数だけ後ろにずらす。
-\item pattern に含まれている文字でその文字が pattern に複数含まれている場合は後ろにずらす量も複数現れる。その中の最小の値だけ後ろにずらす。
-\end{itemize}
-
-text 分割時に、分割部分で pattern が含まれる場合が存在する。
-その場合は、本来の読み込み部分の text の長さ $L$ に加えて、pattern の長さ $s$ から 1 引いた数だけ多く読みこむように設計することで、正しく結果を算出することができる。
-(図\ref{fig:iodivsuc})
-
-\begin{figure}[htbp]
-\begin{center}
-\includegraphics[width=1.0\textwidth]{images/example/iodivsuc.pdf}
-\end{center}
-\caption{分割周りの処理}
-\label{fig:iodivsuc}
-\end{figure}
-
-\newpage
 \section{正規表現}
 正規表現は文字列のパターンを表現するための方法である。
 
@@ -619,8 +526,6 @@
 一文字ずつそれぞれに状態を割り振った場合、状態数 5 のオートマトンが構成される。
 これを一つの文字列に対して状態を割り振った場合、状態数 2 のオートマトンが構成され、状態数を削減することができる。
 
-また、文字列
-
 \begin{figure}[htpb]
   \begin{center}
     \includegraphics[scale=0.17]{images/regex/wordstate.pdf}
@@ -628,3 +533,92 @@
   \caption{文字単位の状態割り振りを文字列単位での状態割り振りに変更}
   \label{fig:wordstate}
 \end{figure}
+
+実際にファイルに対して文字列を検索するときは、Boyer-Moore String Search と呼ばれる 1977 年に Robert S. Boyer と J Strother Moore が開発した文字列検索アルゴリズムを採用する。\cite{bmsearch}
+
+以下、テキストファイルに含まれている文字列を text、検索する文字列を pattern と定義する。
+
+Boyer-Moore String Search を紹介する前に原始的な文字列検索アルゴリズムである力任せ法を紹介する。
+力任せ法は text と pattern を先頭から比較していき、
+pattern と一致しなければ pattern を1文字分だけ後ろにずらして再度比較をしていくアルゴリズムである。
+text の先頭から pattern の先頭を比較していき、文字の不一致が起きた場合は pattern を後ろに 1 つだけずらして再比較を行う。
+(図\ref{fig:bruteforth})
+
+\begin{figure}[htbp]
+\begin{center}
+\includegraphics[width=0.7\textwidth]{images/example/bruteforth.pdf}
+\end{center}
+\caption{力まかせ法}
+\label{fig:bruteforth}
+\end{figure}
+
+\newpage
+このアルゴリズムは実装が容易であるが、 text と pattern の文字数が大きくなるにつれて、比較回数も膨大になる恐れがある。
+text の長さを $n$、pattern の長さを $m$とすると、力任せ法の最悪計算時間は $O(nm)$ となる。
+
+力任せ法の比較回数を改善したアルゴリズムが Boyer-Moore String Search である。
+力任せ法との大きな違いとして、text と pattern を先頭から比較するのではなく、 pattern の末尾から比較していくことである。
+さらに不一致が起こった場合は、その不一致が起こった text の文字で再度比較する場所が決まる。
+
+図\ref{fig:bmsearchthink}は、text と pattern の末尾が不一致を起こして、そのときの text が pattern に含まれていない場合である。
+不一致した text の文字が pattern に含まれていない場合は、pattern を比較する場所に match することはないので、pattern の長さ分だけ後ろにずらすことができる。
+
+\begin{figure}[htbp]
+\begin{center}
+\includegraphics[width=0.7\textwidth]{images/example/bmsearchthink.pdf}
+\end{center}
+\caption{pattern に含まれていない文字で不一致になった場合}
+\label{fig:bmsearchthink}
+\end{figure}
+
+\newpage
+
+図\ref{fig:bmsearchinclude} は不一致が起こったときの text の文字が pattern に含まれている場合である。
+この場合は pattern を後ろに2つずらすと text と pattern が一致する。
+
+不一致したときの text の文字が pattern に含まれていた場合の後ろにずらす量は、pattern の長さから含まれていた文字が pattern の何文字目に含まれているかを引いた値となる。
+この場合、pattern の文字列の長さは 3 で text で不一致を起こした文字 `a' が pattern の 1 文字目に含まれているので、2 文字分だけ後ろにずらすことができる。
+
+\begin{figure}[htbp]
+\begin{center}
+\includegraphics[width=0.7\textwidth]{images/example/bmsearchinlucde.pdf}
+\end{center}
+\caption{pattern に含まれている文字で不一致になった場合}
+\label{fig:bmsearchinclude}
+\end{figure}
+
+\newpage
+
+図\ref{fig:bmsearchsame} は不一致が起こったときの text の文字が pattern に含まれ、その不一致文字が pattern に複数含まれている場合である。
+
+pattern の長さは 4 で、不一致を起こした時の text の文字 `a' は pattern の 1 番目と 3 番目に含まれている。
+pattern を後ろにずらす量は 1 か 3 となる。
+ずらす量を 3 にすると、pattern が含まれている text を見逃す可能性があるので、この場合 `a' で不一致したときは最小の値 1 をとる。
+
+\begin{figure}[htbp]
+\begin{center}
+\includegraphics[width=0.7\textwidth]{images/example/bmsearchsame.pdf}
+\end{center}
+\caption{pattern に同じ文字が複数入り、その文字で不一致になった場合}
+\label{fig:bmsearchsame}
+\end{figure}
+
+pattern と text と不一致時の処理をまとめると、
+
+\begin{itemize}
+\item pattern に含まれていない文字で不一致した場合は、 pattern の長さだけ後ろにずらす。
+\item pattern に含まれている文字の場合は、pattern の長さから pattern に含まれている文字の位置を引いた数だけ後ろにずらす。
+\item pattern に含まれている文字でその文字が pattern に複数含まれている場合は後ろにずらす量も複数現れる。その中の最小の値だけ後ろにずらす。
+\end{itemize}
+
+text 分割時に、分割部分で pattern が含まれる場合が存在する。
+その場合は、本来の読み込み部分の text の長さ $L$ に加えて、pattern の長さ $s$ から 1 引いた数だけ多く読みこむように設計することで、正しく結果を算出することができる。
+(図\ref{fig:iodivsuc})
+
+\begin{figure}[htbp]
+\begin{center}
+\includegraphics[width=1.0\textwidth]{images/example/iodivsuc.pdf}
+\end{center}
+\caption{分割周りの処理}
+\label{fig:iodivsuc}
+\end{figure}
--- a/c5.tex	Fri Feb 12 15:00:13 2016 +0900
+++ b/c5.tex	Sun Feb 14 02:16:29 2016 +0900
@@ -7,31 +7,77 @@
 \item 1TB HDD
 \end{itemize}
 
-I/O を含む/含まない Cerium の Word Count と Mac の wc の比較、
+Cerium で実装した Word Count と Mac の wc の比較と、今回実装した正規表現と Mac の egrep の比較を行なった。
+また、それぞれの結果に実装した並列処理向け I/O の結果も含む。
 
 \section{Word Count}
+ファイルの大きさは 約500MByte で、このファイルには 約650万行、約8300万単語が含まれている。
+図\ref{fig:wordcount} はファイル読み込みを含まない Word Count の結果である。
 
-図\ref{fig:wordcount}
+Mac の wc ではこのファイルを処理するのに 4.08 秒かかる。それに対して、Cerium Word Count は 1 CPU で 3.70 秒、12 CPU だと 0.40 秒で処理できる。
 
-\begin{figure}[htpb]
-  \begin{center}
-    \includegraphics[scale=0.6]{images/result/wordcount.pdf}
-  \end{center}
-  \caption{ファイル読み込み無しの Word Count}
-  \label{fig:wordcount}
-\end{figure}
+1 CPU で動作させると Mac の wc よりも 1.1 倍ほど速くなり、12 CPU で動作させると wc よりも 10.2 倍ほど速くなった。
+
+1 CPU と 12 CPU で比較すると、9.25 倍ほど速くなった。
+12 倍速くなるはずだが、Word Count の処理以外にも Word Count のタスクを作る、タスクを CPU に送るなどの通信部分も含まれるため理論値は出ない。
+
+表\ref{table:metachar}
 
-
+\begin{tiny}
+  \begin{table}[ht]
+    \begin{center}
+      \begin{tabular}[t]{r|r}
+        \hline
+        実行方式 & 実行速度(秒)\\
+        \hline
+        Mac(wc) & 4.08 \\
+        \hline
+        Cerium Word Count(CPU 1) & 3.70\\
+        \hline
+        Cerium Word Count(CPU 4) & 1.00\\
+        \hline
+        Cerium Word Count(CPU 8) & 0.52\\
+        \hline
+        Cerium Word Count(CPU 12) & 0.40\\
+        \hline
+      \end{tabular}
+      \caption{ファイル読み込み無しの Word Count}
+      \label{fig:wordcount}
+    \end{center}
+  \end{table}
+\end{tiny}
 
-図\ref{fig:IOwordcount}
+図\ref{fig:IOwordcount} は、ファイル読み込みを含めた Word Count の結果である。
+Mac の wc ではこのファイルを処理するのに 10.59 秒かかる。それに対して、Cerium Word Count は mmap Blocked Read 全ての状況で Mac の wc よりも速いことを示している。
+Cerium Word Count 12 CPU のとき、7.83 秒で処理をしており、Mac の wc の 1.4 倍ほど速くなっている。
 
-\begin{figure}[htpb]
-  \begin{center}
-    \includegraphics[scale=0.6]{images/result/IOwordcount.pdf}
-  \end{center}
+mmap は読み込みを OS が制御しており、書き手が制御できない。
+また Word Count が走る際ファイルアクセスはランダムアクセスとなる。
+mmap はランダムアクセスを想定していなくてグラフにばらつきが起こっていると考えられる。
+Blocked Read では読み込みをプログラムの書き手が制御しており、ファイルの読み込みもファイルの先頭から順次読み込みを行なっている。
+そのため、読み込みを含めた結果にばらつきが起こりにくくなっていると予想される。
+
+\begin{tiny}
+  \begin{table}[ht]
+    \begin{center}
+      \begin{tabular}[t]{r|r|r|r}
+        \hline
+        CPU Num / 実行方式 & Mac(wc) & mmap & Blocked Read\\
+        \hline
+        1 & 10.590  & 9.96  & 9.33 \\
+        \hline
+        2 & ---     & 8.63  & 8.52 \\
+        \hline
+        4 & ---     & 10.35 & 8.04 \\
+        \hline
+        8 & ---     & 9.26  & 7.82 \\
+        \hline
+      \end{tabular}
   \caption{ファイル読み込みを含む Word Count}
-  \label{fig:IOwordcount}
-\end{figure}
+  \label{table:IOwordcount}
+    \end{center}
+  \end{table}
+\end{tiny}
 
 \section{正規表現}
 
@@ -40,25 +86,55 @@
 \item 並列処理時に NFA・DFA を分割した Task に配りそれぞれの Taskで 照らし合わせる。照らし合わせた際に NFA だとわかった場合にはその場で Subset Construction し DFA を生成する。
 \end{itemize}
 
-図\ref{fig:AZaz}
+図\ref{table:AZaz}
 
-\begin{figure}[htpb]
-  \begin{center}
-    \includegraphics[scale=0.6]{images/result/AZaz.pdf}
-  \end{center}
+\begin{tiny}
+  \begin{table}[ht]
+    \begin{center}
+      \begin{tabular}[t]{r|r|r|r}
+        \hline
+        CPU Num / 実行方式 & egrep & mmap & Blocked Read\\
+        \hline
+        1 & 56.51   & 35.78 & 30.68 \\
+        \hline
+        2 & ---     & 17.19 & 16.50 \\
+        \hline
+        4 & ---     & 15.90 & 15.91 \\
+        \hline
+        8 & ---     & 15.80 & 15.00 \\
+        \hline
+      \end{tabular}
   \caption{AZaz}
-  \label{fig:AZaz}
-\end{figure}
+  \label{table:AZaz}
+    \end{center}
+  \end{table}
+\end{tiny}
+
 
-図\ref{fig:abab}
+表\ref{table:abab}
+
 
-\begin{figure}[htpb]
-  \begin{center}
-    \includegraphics[scale=0.6]{images/result/abab.pdf}
-  \end{center}
+\begin{tiny}
+  \begin{table}[ht]
+    \begin{center}
+      \begin{tabular}[t]{r|r|r|r}
+        \hline
+        CPU Num / 実行方式 & egrep & mmap & Blocked Read\\
+        \hline
+        1 & 83.09   & 57.65 & 40.49 \\
+        \hline
+        2 & ---     & 43.96 & 33.72 \\
+        \hline
+        4 & ---     & 33.37 & 34.26 \\
+        \hline
+        8 & ---     & 35.48 & 32.46 \\
+        \hline
+      \end{tabular}
   \caption{abab}
-  \label{fig:abab}
-\end{figure}
+  \label{table:abab}
+    \end{center}
+  \end{table}
+\end{tiny}
 
 
 表\ref{table:metachar}
--- a/images/regex/cfab.bb	Fri Feb 12 15:00:13 2016 +0900
+++ /dev/null	Thu Jan 01 00:00:00 1970 +0000
@@ -1,5 +0,0 @@
-%%Title: images/regex/cfab.pdf
-%%Creator: extractbb 20150315
-%%BoundingBox: 0 0 768 399
-%%CreationDate: Mon Feb  8 11:22:40 2016
-
Binary file images/regex/cfab.pdf has changed
--- a/images/regex/cfdg.bb	Fri Feb 12 15:00:13 2016 +0900
+++ /dev/null	Thu Jan 01 00:00:00 1970 +0000
@@ -1,5 +0,0 @@
-%%Title: images/regex/cfdg.pdf
-%%Creator: extractbb 20150315
-%%BoundingBox: 0 0 768 300
-%%CreationDate: Mon Feb  8 11:22:40 2016
-
Binary file images/regex/cfdg.pdf has changed
--- a/images/regex/cfdgab.bb	Fri Feb 12 15:00:13 2016 +0900
+++ /dev/null	Thu Jan 01 00:00:00 1970 +0000
@@ -1,5 +0,0 @@
-%%Title: images/regex/cfdgab.pdf
-%%Creator: extractbb 20150315
-%%BoundingBox: 0 0 1278 396
-%%CreationDate: Mon Feb  8 11:22:40 2016
-
Binary file images/regex/cfdgab.pdf has changed
--- a/images/regex/efgi.bb	Fri Feb 12 15:00:13 2016 +0900
+++ /dev/null	Thu Jan 01 00:00:00 1970 +0000
@@ -1,5 +0,0 @@
-%%Title: images/regex/efgi.pdf
-%%Creator: extractbb 20150315
-%%BoundingBox: 0 0 888 360
-%%CreationDate: Mon Feb  8 11:22:40 2016
-
Binary file images/regex/efgi.pdf has changed
Binary file master_paper.pdf has changed
--- a/memo/result.txt	Fri Feb 12 15:00:13 2016 +0900
+++ b/memo/result.txt	Sun Feb 14 02:16:29 2016 +0900
@@ -1,5 +1,46 @@
+Sat Feb 13 22:59:03 JST
+
+
+'[A-Z][A-Za-z0-9]*'  50MB.txt
+./regexParser -ts               
+./cerium/ceriumGrep -cpu 12     
+./cerium/ceriumGrep -cpu  2     
+egrep                           6.05
+
+./regexParser -regex '[A-Z][A-Za-z0-9]*' -ts -file file/5GB.txt > /dev/null  159.87s user 3.33s system 86% cpu 3:07.78 total 2016
+
+egrep -o '[A-Z][A-Za-z0-9]*' file/5GB.txt > /dev/null  562.16s user 2.28s system 99% cpu 9:24.50 total
+
+'[A-Z][A-Za-z0-9]*'  5GB.txt
+./regexParser -ts               3:07.78
+./cerium/ceriumGrep -cpu 12     
+./cerium/ceriumGrep -cpu  2     
+egrep                           9:24.50
+
+./cerium/ceriumGrep -cpu 2 -regex '[A-Z][A-Za-z0-9]*' -file file/500MB.txt >   25.00s user 0.74s system 95% cpu 27.061 total
+
+./regexParser -regex '[A-Z][A-Za-z0-9]*' -ts -file file/500MB.txt > /dev/null  15.98s user 0.23s system 76% cpu 21.171 total
+
+./cerium/ceriumGrep -regex '[A-Z][A-Za-z0-9]*' -file file/500MB.txt >   24.50s user 0.66s system 65% cpu 38.293 total
+
+./cerium/ceriumGrep -cpu 12 -regex '[A-Z][A-Za-z0-9]*' -file file/500MB.txt >  25.65s user 0.83s system 254% cpu 10.419 total
+
+egrep -o '[A-Z][A-Za-z0-9]*' file/500MB.txt > /dev/null  57.46s user 0.23s system 99% cpu 57.753 total
+
+./sequentialSearchCbC -file file/500MB.txt > /dev/null  10.51s user 0.22s system 64% cpu 16.530 total
+
+
+
+
+-------------------------------------------
 Fri Feb 12 12:15:42 JST 2016
 
+50MB 5GB
+マッチしにくいファイル
+CbC
+
+将来 nkf との組み合わせ
+
 
 
 -------------------------------------------