Mercurial > hg > Papers > 2010 > jsst-shinya
changeset 18:890d3517870a
add DFA graph
| author | Ryoma SHINYA <shinya@firefly.cr.ie.u-ryukyu.ac.jp> |
|---|---|
| date | Mon, 13 Sep 2010 12:13:37 +0900 |
| parents | 54987da33049 |
| children | df4ce962e5ce |
| files | presen/index.html presen/pix/bench_grep.png presen/pix/complex-regex.png presen/pix/fig.numbers presen/pix/fixed-string.png presen/pix/simple-regex.png |
| diffstat | 6 files changed, 14 insertions(+), 6 deletions(-) [+] |
line wrap: on
line diff
--- a/presen/index.html Mon Sep 13 08:42:47 2010 +0900 +++ b/presen/index.html Mon Sep 13 12:13:37 2010 +0900 @@ -231,7 +231,7 @@ <li class="incremental">3つの生成系は, 生成する言語が違うが, 生成するコードの処理内容は同じ.</li> </ul> <li class="incremental">生成されたコードは, 関数呼び出しとswitch文によるシンプルなプログラムなので, 最適化によって性能の等しいネイティブコードが生成されたためと思われる.</li> - <li class="incremental">CbCでは, 関数呼び出しより軽量な状態遷移である継続を用いて実装しているため, コンパイラの最適化に依らず性能の高いコードが保証されている.</li> + <li class="incremental">CbCでは, 関数呼び出しより軽量な状態遷移である継続を用いて実装しているため, コンパイラの最適化に依らず性能の高いコードが保証されている -> 生成コードとして最適.</li> </ul> </div> <!-- PAGE --> @@ -278,21 +278,21 @@ <ul> <li> <strong>fixed-string</strong> - 固定文字列でのマッチング<br/> - パターン : "<blue>Wikipedia</blue>"<br/> + パターン : "<blue>Wikipedia</blue>" - <a href="pix/fixed-string.png" target="blank">図</a><br/> マッチ行数: 348936行 </li> <li> <strong>simple-regex</strong> - 単純な正規表現でのマッチング<br/> <span class="incremental">Wikipediaの記事のカテゴリタグ記述にマッチ</span><br/> - パターン : "<blue>^\*+ \[\[</blue>"<br/> + パターン : "<blue>^\*+ \[\[</blue>" - <a href="pix/simple-regex.png" target="blank">図</a><br/> マッチ行数: 1503行 </li> <li> <strong>complex-regex</strong> - 複雑な正規表現でのマッチング<br/> - パターン : "<blue>(Python|Perl|Pascall|Prolog|PHP|Ruby|Haskell|Lisp|Scheme)</blue>"<br/> + パターン : "<blue>(Python|Perl|Pascall|Prolog|PHP|Ruby|Haskell|Lisp|Scheme)</blue>" - <a href="pix/complex-regex.png" target="blank">図</a><br/> マッチ行数: 3439028行 </li> - <li class="incremental">"複雑さ" = DFAに変換時の分岐の多さ.</li> + <li class="incremental">"複雑さ" = 変換されたDFAの状態数/遷移規則の多さ.</li> </ul> </div> <!-- PAGE --> @@ -301,7 +301,7 @@ <img src="pix/bench_grep.png" style="height: 11em;"/> <ul> <li class="incremental">fixed-stringでは, 固定文字列フィルタの差が大きい.</li> - <li class="incremental">complex-regexでは, 本実装がGNU grepより高速な結果を出した.</li> + <li class="incremental">complex-regexでは, 本実装がGNU grepより高速な結果を出した. *Repeat: コード生成, コンパイル時間も含む.</li> </ul> </div> <!-- PAGE --> @@ -327,8 +327,16 @@ <li>後方参照: "(A*)B\1" -> "\1"は(A*)でマッチした文字列.</li> <li class="incremental">本実装は関数遷移によるマッチングを行うので, バックトラック処理を容易に記述できる.</li> </ul> + <li>コード生成の最適化, 生成手法の評価.</li> + </ul> + </div> + <!-- PAGE --> + <div class="slide"> + <h1>展望</h1> + <ul> <li>grep 以外のソフトウェアへの応用</li> <ul> + <li>正規表現に対して, 検索対象の規模が大きいプログラムと相性が良い.</li> <li>一度コンパイルすればマッチングを行うネイティブコードが得られる.</li> <li>同様のパターンで何度もマッチングを行うプログラムと相性が良い.</li> <li class="incremental">スパムフィルタの単語検索など.</li>