Mercurial > hg > Papers > 2016 > masa-master

changeset 74:1f1ef47ba380

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
fix
author Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
date Wed, 17 Feb 2016 15:11:49 +0900
parents a2004b9f1517
children c8893a5b53cf
files paper/c5.tex paper/master_paper.pdf
diffstat 2 files changed, 55 insertions(+), 33 deletions(-) [+]
line wrap: on
line diff
--- a/paper/c5.tex	Wed Feb 17 14:32:16 2016 +0900
+++ b/paper/c5.tex	Wed Feb 17 15:11:49 2016 +0900
@@ -81,19 +81,59 @@
 \end{tiny}
 
 \section{正規表現}
-当実験では、Mac の egrep 、C で実装した逐次に DFA の状態遷移と照らし合わせる CGrep、Cerium で並列処理をする CeriumGrep を比較している。
+当実験では、Mac の egrep 、C で実装した逐次に DFA の状態遷移と照らし合わせマッチングをするC実装の Grep、Cerium で並列処理をする CeriumGrep を比較している。
+
+
+表\ref{table:metachar} 500MB(単語数約8500万) のファイルに対して正規表現 '[A-Z][A-Za-z0-9]*s' をマッチングした結果である。
+これはファイル読み込みを含めた結果と読み込みを含めていない結果の比較である。
 
-表\ref{table:AZaz} は正規表現 '[A-Z][A-Za-z0-9]*s' を 500MB(単語数約8500万)、1GB(単語数約1.7億語)のファイルに対してマッチングを行なった。
+C実装Grep や CeriumGrep は繰返し実行をすると実行速度が短くなる。
+これは、読み込んだファイルがキャッシュに残っており、ファイル読み込みが省略されるためである。
+同じファイルに対して違う正規表現でマッチングさせたとしてもファイル読み込みが省略されるため、高速に結果が返ってくる。
+
+しかし egrep は繰返し実行しても同じ速度で実行されるため、毎回ファイルを読み込む。
+そのため、同じファイルに違う正規表現をマッチさせようとすると毎回読み込みが行われる。
 
 \begin{tiny}
   \begin{table}[ht]
     \begin{center}
-        正規表現 '[A-Z][A-Za-z0-9]*s'
+        正規表現 '[A-Z][A-Za-z0-9]*s'\\
+        ファイルサイズ : 500MB(単語数約8500万)
+      \begin{tabular}[t]{|c|r|r|}
+        \hline
+        実行方式 & ファイル読み込み有 & ファイル読み込み無\\
+        \hline
+        C実装Grep & 21.17 & 16.15\\
+        \hline
+        CeriumGrep(CPU 12) mmap  & 18.00 & 5.12\\
+        \hline
+        CeriumGrep(CPU 12) bread & 15.76 & 5.18\\
+        \hline
+        egrep & 59.51 & 59.51 \\
+        \hline
+      \end{tabular}
+      \caption{ファイル読み込み有りと無しを変化させた各 grep の結果}
+      \label{table:metachar}
+    \end{center}
+  \end{table}
+\end{tiny}
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+表\ref{table:AZaz} は正規表現 '[A-Z][A-Za-z0-9]*s' を 500MB(単語数約8500万)、1GB(単語数約1.7億語)のファイルに対してマッチングを行なった。
+
+ファイルサイズに比例して処理時間も長くなっていく。
+
+\begin{tiny}
+  \begin{table}[ht]
+    \begin{center}
+        正規表現 '[A-Z][A-Za-z0-9]*s'\\
+        ファイルサイズ : 500MB(単語数約8500万)\\
       \begin{tabular}[t]{|c|r|r|r|r|}
         \hline
         実行方式/File Size(Match Num)    & 50MB(54万) & 100MB(107万) & 500MB(536万) & 1GB(1072万) \\
         \hline
-        CGrep                            & 4.51 &  9.42 & 20.62 & 40.10\\
+        C実装 Grep                            & 4.51 &  9.42 & 20.62 & 40.10\\
         \hline
         CeriumGrep(CPU 12) mmap          & 8.97 & 10.79 & 18.00 & 29.16\\
         \hline
@@ -110,42 +150,20 @@
 
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 
-表\ref{table:metachar} 500MB(単語数約8500万) のファイルに対して正規表現 '[A-Z][A-Za-z0-9]*s' をマッチングした結果である。
-これはファイル読み込みを含めた結果と読み込みを含めていない結果の比較である。
-egrep は実行するたびにファイル読み込みを行うため、ファイル読み込み無しの測定はなし。
-\begin{tiny}
-  \begin{table}[ht]
-    \begin{center}
-      \begin{tabular}[t]{|c|r|r|}
-        \hline
-        実行方式 & ファイル読み込み有 & ファイル読み込み無\\
-        \hline
-        CGrep & 21.17 & 16.15\\
-        \hline
-        CeriumGrep(CPU 2) & 27.06 & 15.40\\
-        \hline
-        CeriumGrep(CPU 12) & 12.48 & 7.39\\
-        \hline
-        egrep & 59.51 & 59.51 \\
-        \hline
-      \end{tabular}
-      \caption{ファイル読み込み有りと無しを変化させた各 grep の結果}
-      \label{table:metachar}
-    \end{center}
-  \end{table}
-\end{tiny}
+表\ref{table:abab}
+は aとb が多く含まれている約500MB(単語数約2400万)のファイルに対して、正規表現の状態数を変化させてみた。
+これは読み込みを含んでいる結果で、CeriumGrep のファイル読み込みは Blocked Read、CPU 数 12 にて実行した。
 
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-表\ref{table:abab}
-aとb が多く含まれている約500MB(単語数約2400万)のファイルに対して、正規表現の状態数を変化させてみた。
-これは読み込みを含んでいる結果で、CeriumGrep のファイル読み込みは Blocked Read、CPU 数 12 にて実行した。
+この例題で使用した正規表現は `(a \textbar b)' を `*a' の直後に付け加えていくと、それだけ状態数が指数関数的に増えていく。
+CeriumGrep は状態数が指数関数的に増加しても 1 秒ほど増加するが、egrep では 5,6 秒ほど増加していく。
 
 \begin{tiny}
   \begin{table}[ht]
     \begin{center}
+        ファイルサイズ : 500MB(単語数約2400万)\\
       \begin{tabular}[t]{|l|r|r|r|r|}
         \hline
-        正規表現 & 状態数 & マッチ数 & CeriumGrep time (s) & egrep time(s)\\
+        正規表現 & 状態数 & マッチ数 & CeriumGrep (CPU 12) bread & egrep \\
         \hline
         '(a \textbar b)*a(a \textbar b)(a \textbar b)z'                                               & 12 & 約10万 & 26.58 &  70.11 \\
         \hline
@@ -167,9 +185,13 @@
 表\ref{table:nomatch} ab の文字列がならんでいるところに (W \textbar w)ord の正規表現
 aとb が多く含まれている約500MB(単語数約2300万)のファイルに対して、全くマッチしない正規表現を与えてパターンマッチングさせてみた。
 
+
+
 \begin{tiny}
   \begin{table}[ht]
     \begin{center}
+        ファイルサイズ : 500MB(単語数約2400万)\\
+        正規表現 : (W \textbar w)ord\\
       \begin{tabular}[t]{|c|r|}
         \hline
         実行方式/File Size(Match Num) & time (s)\\
Binary file paper/master_paper.pdf has changed