カテゴリー別アーカイブ: 正規表現

ループ展開よりルックアラウンドアサーションの方が速い場合もある

Onemanのテンプレート処理のコードの中で、HTML抽出部分の正規表現にループ展開を用いて高速化する事を課題にしていたのですが、いざやってみると、ループ展開は使わずに元のルックアラウンドアサーションのままが一番速そうだという事が分かりました。
これまでもループ展開の方が絶対に速いと思い込みベンチマークも取っていなかったのですが、分からないものですね。恐るべしオプティマイザ。

やりたかった事

Onemanのテンプレート処理部分をなるべく速いコードに置き換える事。

Onemanはテンプレート処理の最初のフェーズでソースのHTML部分をPerlコードに変換します。具体的には、以下のようなテンプレートの%>と<%で囲まれた太字部分を抽出して、各種エスケープと出力処理に置き換えます。

%><table>
  <caption>環境変数一覧</caption>
  <tbody><%
    for my $key ( sort keys %ENV ) { %>
        <tr>
          <th><%= $key %></th>
          <td><%= $ENV{$key} %></th>
        </tr><%
    } %>
  </tbody>
</table><%

抽出するためのオリジナルの正規表現は以下です。.+?によるマッチの前後にルックアラウンドアサーションで%>と<%を除外するというシンプルなコードでした。

(?<= %> ) (?! <% ) (.+?) (?= <% )

これを、高速化のためにループ展開へ置き換える、というのがやりたかった事です。

試した内容

おそらく最も最適化できていて、タグを優先するか否かが異なる2パターンのループ展開(221、222)とそれに至るまでの計8パターンの正規表現を作成し、オリジナルと比較してみました。

use Benchmark qw( cmpthese );

my $HTML = '%>' . ( << 'END_OF_HTML' x 10 ) . '<%';
    <table>
      <tbody><%
        for my $key ( sort keys %ENV ) { %>
            <tr>
              <th><%= $key %></th>
              <td><%= $ENV{$key} %></td>
            </tr><%
        } %>
      </tbody>
    </table>
END_OF_HTML

cmpthese( 10000, {
    Original => sub { $HTML =~ s{ (?<= %> )
        (?! <% ) (.+?) (?= <% )
    }{$1}gxms; },

    111 => sub { $HTML =~ s{ (?<= %> )
        ( (?: [^<]+ | (?: < (?! % ) ) )+ )
    }{$1}gxms; },

    112 => sub { $HTML =~ s{ (?<= %> )
        ( (?: (?: < (?! % ) | [^<]+ ) )+ )
    }{$1}gxms; },

    121 => sub { $HTML =~ s{ (?<= %> )
        ( (?: [^<]+ | (?: < (?! % ) [^<]* ) )+ )
    }{$1}gxms; },

    122 => sub { $HTML =~ s{ (?<= %> )
        ( (?: (?: < (?! % ) [^<]* | [^<]+ ) )+ )
    }{$1}gxms; },

    211 => sub { $HTML =~ s{ (?<= %> )
        ( (?: [^<]+ | < (?! % ) ) (?: < (?! % ) [^<]* )* )
    }{$1}gxms; },

    212 => sub { $HTML =~ s{ (?<= %> )
        ( (?: < (?! % ) | [^<]+ ) (?: < (?! % ) [^<]* )* )
    }{$1}gxms; },

    221 => sub { $HTML =~ s{ (?<= %> )
        ( (?: [^<]+ | < (?! % ) [^<]* ) (?: < (?! % ) [^<]* )* )
    }{$1}gxms; },

    222 => sub { $HTML =~ s{ (?<= %> )
        ( (?: < (?! % ) [^<]* | [^<]+ ) (?: < (?! % ) [^<]* )* )
    }{$1}gxms; },
} );

221と222はOriginalより圧倒的に速い、と思ったのですが。

結果

Originalが最も高速でした。

           Rate 211 212 112 111 121 122 221 222 Original
211      2323/s  -- -1% -7% -8%-12%-14%-18%-18%     -27%
212      2357/s  1%  -- -5% -6%-10%-13%-17%-17%     -26%
112      2484/s  7%  5%  -- -1% -5% -9%-12%-13%     -22%
111      2514/s  8%  7%  1%  -- -4% -7%-11%-12%     -21%
121      2627/s 13% 11%  6%  4%  -- -3% -7% -8%     -17%
122      2716/s 17% 15%  9%  8%  3%  -- -4% -5%     -14%
221      2824/s 22% 20% 14% 12%  8%  4%  -- -1%     -11%
222      2848/s 23% 21% 15% 13%  8%  5%  1%  --     -10%
Original 3174/s 37% 35% 28% 26% 21% 17% 12% 11%       --

ループ展開のパターンの中では予想通り22○が最も速く、また、○○1と○○2のどちらが良いかはHTMLの書き方に依りそうですが、いずれにしてもOriginalが速いのであれば難しく考える必要はありませんね。

[^<]*および[^<]+にマッチする部分が長い場合はループ展開の方が速いかな、と、タグ文字が無い部分を増やしたHTMLでも試してみましたが、結果は同じどころかOriginalがより速くなりました。もうよく分かりません。。

正規表現の先読みと後読みを使いこなす

Perlにはルックアラウンドアサーション(lookaround assertion)という4つの正規表現拡張があります。肯定の先読み・否定の先読み・肯定の後読み・否定の後読みの4つです。

(?=...) : 肯定の先読み
(?!...) : 否定の先読み
(?<=...): 肯定の後読み
(?<!...): 否定の後読み

これらの使い方を紹介します。

例えば、HTMLのタグとタグの間の空白文字をs///演算子で全て取り除きます。

ルックアラウンドを使わない場合は、

$html =~ s/>\s+</></g;                    # ルックアラウンドを使わない

と書けます。少し読みにくくなるので、Perlベストプラクティスで書きます。

$html =~ s{ > \s+ < }{><}gxms;            # ルックアラウンドを使わない。Perlベストプラクティスの書き方

となります。

ですが、置き換える必要のない山カッコまで置き換えるのはスマートではないですよね?
そこでルックアラウンドを使います。

直前に左山カッコが現れる位置を肯定の後読みでマッチさせて、直後に右山カッコが現れる位置を肯定の先読みでマッチさせる事で、山カッコを置き換えず、空白文字だけを置き換える(ここでは取り除く)対象にできます。

$html =~ s{ (?<= > ) \s+ (?= < ) }{}gxms; # ルックアラウンドを使う

ただ、これではファイル先頭もしくは末尾に空白文字がある場合にそれを取り除く事ができません。
それも取り除くには次のように、先頭および末尾にもマッチする以下のパターンでも良いですが、

$html =~ s{ (?: \A | (?<= > ) ) \s+ (?: (?= < ) | \z ) }{}gxms;

と長くなってしまいます。

否定の後読みおよび否定の先読みと文字クラスの否定を使うと、以下のようにもっとシンプルに表現できます。

$html =~ s{ (?<! [^>] ) \s+ (?! [^<] ) }{}gxms;

これは、

(?<![^>]): 直前に右山カッコ以外の文字は現れない
(?![^<]) : 直後に左山カッコ以外の文字は現れない

という表現になり、つまり、

(?<![^>]): 直前に右山カッコが現れる、もしくは文字が無い
(?![^<]) : 直後に左山カッコが現れる、もしくは文字が無い

という意味になるためです。おもしろいですね!