正規表現

特定の文字列を含まない正規表現のベンチマーク

環境

OS: Windows 10 Professional 1709 (.NET Framework 4.7.1を含む)
CPU: Core i7-7500U
メモリ: 8GB
正規表現エンジン:.NET準拠(PowerShell上でベンチマーク)

以下の内容は、処理系(正規表現エンジンの違いなど)により結果が変わってくる可能性があります。

特定の文字列を含まない行の正規表現(昔:POSIX拡張正規表現)

特定の文字列(たとえば「ABCD」)を含まない行にマッチする正規表現は、否定先読み (?!…) が使えなかった頃は例えば下記のように複雑な形でした。

:one: ^([^A]+|A+(BC?A+)*([^BA]|B([^CA]|C([^DA]|$)|$)|$))*$

従来型NFAと呼ばれる正規表現エンジンでは、同じパターンを表す正規表現でも書き方により速度が異なります。例えば、上記の正規表現を少し書き換えて下記の形にすると少し速くなります。

:two: ^[^A]*(A+(BC?A+)*([^BA]|B([^CA]|C([^DA]|$)|$)|$)[^A]*)*$

長くなりますが、下記の形はさらに少し速くなります。

:three: ^[^A]*(A+(BC?A+)*([^BA]|B([^CA]|C([^DA])))[^A]*)*(A+(BC?A+)*(BC?)?)?$

上記 :one::three:は、マッチする場合(対象にABCDが含まれない場合)には否定先読みを使用した^(?!.*ABCD).*$^(?:(?!ABCD).)*$ よりも高速です。

特定の文字列を含まない行の正規表現(今:.NET、PCREなど)

上記の :one::three: に、PCRE(Perl Compatible Regular Expressions: Perl5互換正規表現ライブラリ)や .NET などの新しい正規表現エンジンで利用可能となっている「否定先読み (?!…)」、「キャプチャ抑止 (?:…)」、「バックトラック抑止 (?>…)」なども活用した以下の5つのバリエーションを加えてベンチマークしてみました。

:four: ^(?!.*ABCD).*$  
:five: ^(?:(?!ABCD).)*$
:six: ^(?>[^A]+|A(?!BCD))*$
:seven: ^(?>[^A]*(?:A(?!BCD)[^A]*)*)$
:eight: ^(?>[^A]*(?:A+(?:BC?A+)*(?:[^BA]|B(?:[^CA]|C(?:[^DA])))[^A]*)*(A+(BC?A+)*(BC?)?)?)$

※ 最後の:eight: のみ否定先読みを利用していません(上記 :three: に対してグループのキャプチャ抑止、バックトラックの抑止を適用)。

ベンチマークの方法

以下の PowerShell関数で各正規表現の検索に要する時間(1000回の試行の平均値、単位:ミリ秒)を求めます。

$io = gc "(WikipediaのHTMLソースファイルのパス)" -Raw

Function Test($Regex) {
    $num = 1000
    $pat = '(?s)' + $Regex
    $tot = 0
    for($i=0; $i -lt $num; $i++) {
        $res = Measure-Command {
            $r=@(Select-String -Pattern $pat -InputObject $io)
        }
        $tot += $res.TotalMilliSeconds
    }
    Write-Output $($tot/$num)
    Write-Output $($r.Matches.Length)
}

パフォーマンスの差異を際立たせるために検索対象の文字列(行)を長めに設定しました。具体的には、シングルラインモード(各正規表現の先頭に (?s) を付加し、ピリオド (.) を改行 (\n) にもマッチさせる)で、日本語版Wikipediaの正規表現のページのHTMLソース全体を1つの行として扱います。

ベンチマーク結果(マッチする場合)

日本語版Wikipediaの正規表現のページのHTMLソースファイルには、「ABCD」という文字列は含まれません。したがって、上記 :one::seven: の正規表現でこのファイルを検索するとマッチします。その検索に要した時間の平均値は下記の通りです。

正規表現 所要時間 [msec]
:one: 14
:two: 12
:three: 11
:four: 27
:five: 38
:six: 8.7
:seven: 7.4
:eight: 8.7

上記の結果より、ABCDという文字列の最初の文字「A」をまず検索してマッチした場合に後続の文字が「BCD」でないことをテストする :seven: が最も速いという結果となりました。:seven: はよく利用される :four::five: より 3倍、5倍以上速いです。また、否定先読みを利用しない :eight: が健闘しているのが分かります。:three::eight: の結果の差に、グループのキャプチャがもたらすオーバヘッドが表れています。

ベンチマーク結果(マッチしない場合)

検索対象の文字列(行)の先頭部分に位置する「<htm」の文字列と末尾部分に位置する「</ht」の文字列について検索した結果を下記に示します。

正規表現 所要時間("ABCD" → "<htm")[msec] 所要時間("ABCD" → "</ht")[msec]
:one: 12 10分以上
:two: 0.06 43
:three: 0.07 82
:four: 19 8.4
:five: 0.05 53
:six: 0.05 5.7
:seven: 0.05 4.9
:eight: 0.06 5.5

やはり :six::eight: が速く、よく使われる :four::five: より10~100倍以上も早い場合があることが分かります。:three::eight: の結果を比較すると、(?>…)でバックトラックを抑止した効果が大きいことが分かります。

ベストパフォーマンス賞

複雑すぎず、どんなケースでも速いという意味で、今回調べた中での勝者は :seven: となりました。

開始・終了を示す文字列で囲まれた範囲にマッチする正規表現

「BEGIN」と「END」の2つの文字列で囲まれた(最も内側の)領域にマッチする正規表現を考えると、その2つの文字列の間には「BEGIN」や「END」の文字が含まれてはなりません。これを、よく使われる :five: に似た正規表現で表すと

BEGIN((?:(?!BEGIN|END).)*)END

となり、上のベンチマークで最速であった :seven: に似た正規表現で表すと

BEGIN([^BE]*(?:(B(?!EGIN)|E(?!ND))[^BE]*)*)END

となります。

HTMLタグのペアで囲まれた最も内側の範囲にマッチする正規表現は、開始と終了を示す文字列が似ているので少し形が変わります。<html…></html> のペアの場合は、 :five: に似た正規表現では

<html(?:".*?"|'.*?'|[^'"])*?>((?:(?!</?html).)*)</html>

ですが、:seven: に似た正規表現では

<html(?:".*?"|'.*?'|[^'"])*?>([^<]*(?:<(?!/?html)[^<]*)*)</html>

となり数倍速くなります。

注:正規表現全体を二重引用符で囲む場合は、上記の二重引用符は2個ずつ必要になります。

クリエイティブ・コモンズ 表示 - 継承 4.0 国際