SkRegExp 2.0 変更の詳細「最適化のための情報収集」

SkRegExp verion 2.0 は仕様が変更になっています。

今回は最適化のための情報収集の変更について説明します。

version 1.5 までは NFA を3回スキャンして情報を収集していました。

version 2.0 からはこれらの情報を NFA を作りながら収集するようにしました。

これにより最適化の処理速度の向上が見込め、より柔軟な最適化が可能になります。

可能になった”では無いことに注意してください。

最適化はまだ途上です。

たとえば、version 2.0 になって退化した最適化があります。

a*b と言う正規表現パターンを例に説明します。

1.5 では先頭の文字が [ab] の位置で正規表現エンジンを起動します。b が先頭位置に来ることをエンジンが分析できるからです。

2.0 の場合、現状では b が先頭位置に来ることを分析できなくなっています。

そのため、このようなパターンの処理速度は低下しています。

その代わり、正規表現パターンの中にリテラル文字が含まれているときの処理速度は大幅に改善しています。

たとえば、次のようなパターンです。

([^ @]+)@([^ @]+)

1.5 ではこのようなパターンでも先頭文字列のチェックを行ないます。

このパターンの先頭文字は [^ @] です。

しかし、[^ @] はスペースと @ 以外の文字列にマッチします。これでは候補が多すぎて絞り込みになりません。

2.0 は @ を最適化に使います。

この正規表現パターンで @ は必須な文字列だからです。

SkRegExp は、正規表現エンジンを起動する前に @ が対象文字列に含まれているかをチェックします。

含まれている場合だけ、正規表現エンジンを起動します。

この種のパターンの場合、最大で20倍の高速化が実現できました。

正規表現としては、このようなパターンの方が多いです。

そのため、現状ではマイナスよりプラスの方が多いと考えています。

SkRegExp version 2.0 はコチラでダウンロードできます。

コメントを残す

メールアドレスが公開されることはありません。