読んだ。この日記で以前書いたようなこと(20080116p01, 20080111p01)は全て書いてあった。もちろんそれ以上に知らないこと(NFAのマッチングのしかた、NFA型正規表現エンジンに適用できる正規表現のチューニングの具体例、Unicodeサポート、Perl, .NET, Java, PHPの正規表現、\Gの使い方などなど)が書かれていた。
非常に読みやすい文章で書かれているし、必要なところでは必ず前後のページへの参照先が書かれている。章の始めには Overviewがあり、その章から読み始めた読者への配慮も忘れない。当たり前のことだけど、徹底されている。「まずこの本を読め。正規表現について話すのはそれからだ。」と言い切れる良い本。正規表現を初めて学ぶ人にも、効率について考える余地ができてくるほど既に正規表現を使っている人にも役に立つ。
すごく実用的なテクニックで、でも全く想像が及ばなかったものがある。168ページの「4.5.8.1 肯定の先読みを使ったアトミックグループの模倣」がそれ。
/(?>pattern)/ // アトミックグループを使ったパターン /(?=(pattern))\1/ // 先読みでアトミックグループを模倣したパターン
高機能化する他の実装にくらべて、昔のままの JavaScriptの正規表現はバックトラックを抑制する構文を持っていない。JavaScriptでは非常に有用。
20080116p01でも書いたが、次の終わらない正規表現
/"(?:[^\\"]+|\\.)*"/ // マッチに失敗するとき死ぬほど遅い
はアトミックグループや絶対最大量指定子が使えるなら次のように書けるが JavaScriptは両方ともサポートしていない。
/"(?:[^\\"]+|\\.)*+"/ // JavaScriptでは使えない /"(?>(?:[^\\"]+|\\.)*)"/g // JavaScriptでは使えない /"(?:[^\\"]++|\\.)*"/ // JavaScriptでは使えない。※上2つとは少し意味が違う
次のように先読みでアトミックグループを模倣すると組み合わせの爆発を避けることができる。
/"(?=((?:[^\\"]+|\\.)*))\1"/ /"\1"/ // 上のパターンから先読み部分を取り除いたもの。
先読みを取り除いたパターンを見ると一目瞭然だが、引用符がペアになっていなくて \1 の後ろの " のマッチに失敗したとしても戻る場所がない。あるのは " と \1 にマッチしたという結果で、どちらもオプションではないので取り消すことはできず、繰り返しでもないのでマッチした部分を少しずつ手放させることもできない。なので、ちょっとずつ後じさりしながら延々とあらゆる組み合わせのマッチを試行することなしに、マッチが失敗に終わったことが即座に判断できるようになるというわけ。本物のアトミックグループよりは劣るが効率も悪くない。同じ働きをする次の二つのパターンとかかる時間を比較してみた。
/"[^\\"]*(?:\\.[^\\"]*)*"/ /"(?:[^\\"]|\\.)*"/
バックトラックによる組み合わせの爆発が起きない 3つのパターンでかかる時間を比較。3回実行した。(3回繰り返しても一回一回の中の試行順が固定されていたら傾向は同じになるわな。無意味。あてみやむいみ)
var re = [
/"(?:[^\\"]|\\.)*"/,
/"(?=((?:[^\\"]+|\\.)*))\1"/,
/"[^\\"]*(?:\\.[^\\"]*)*"/
];
var s = [
'"'+ new Array(5000+1).join('\\"'), // 1/100
'"'+ new Array(500000+1).join('\\"') +'"',
'"'+ new Array(500000+1).join("\\'"),
'"'+ new Array(500000+1).join("\\'") +'"',
'"'+ new Array(500000+1).join('a'),
'"'+ new Array(500000+1).join('a') +'"'
];
var results = [];
for(var j = 0; j !== s.length; ++j) {
var result = [];
for(var i = 0; i !== re.length; ++i) {
var t0 = new Date();
var m = re[i].exec(s[j]);
result[i] = new Date() - t0;
}
results[j] = result;
}
WScript.Echo(results.join("\n"));
数の単位は msec。
| パターン1 | パターン2 | パターン3 | |||
| 工夫なし | アトミックグループの模倣 | ループ展開 | |||
| /"(?:[^\\"]|\\.)*"/ | /"(?=((?:[^\\"]+|\\.)*))\1"/ | /"[^\\"]*(?:\\.[^\\"]*)*"/ | |||
|---|---|---|---|---|---|
| 文字列1 | マッチしない(F) | "\"\"......\"\" | 2910×100, 2928×100, 2914×100 | 2551×100, 2581×100, 2595×100 | 2372×100, 2387×100, 2377×100 |
| マッチする(T) | "\"\"......\"\"" | 124, 124, 124 | 138, 137, 134 | 108, 107, 108 | |
| 文字列2 | マッチしない(F) | "\'\'......\'\' | 138, 140, 151 | 125, 127, 125 | 122, 118, 118 |
| マッチする(T) | "\'\'......\'\'" | 138, 126, 126 | 140, 128, 133 | 135, 105, 106 | |
| 文字列3 | マッチしない(F) | "aa..........aa | 174, 172, 166 | 14, 11, 13 | 96, 90, 92 |
| マッチする(T) | "aa..........aa" | 155, 119, 126 | 32, 15, 14 | 15, 12, 11 | |
ところで、文字列1Fがどのパターンでも一様に遅いのは文字列長に比例したバックトラックが行われているからなんだろうが、パターン2(先読みによるアトミックグループの模倣)でもそれを抑制できていないのは、なんとかできないものか。それでこそ若干のオーバーヘッドをのんででもアトミックグループの模倣を採用する理由になるのだが。
/\/(?:\\.|[^\n\\\/])+\/[gim]*(?!\w)/g /\/(?:\\.|[^\n\\\/]+)+\/[gim]*(?!\w)/g // 死ぬほど遅い
どちらも同じく /regexp/i みたいな正規表現リテラルにマッチするのだが、下の方がブラウザが固まるほど遅い*。バックトラックの影響だろうか、これまで気にしてこなかったが……。原因が推測できない(無能)のがイタイ。(この日記、SHJSによるソースコードハイライトを多用していると読み込み完了直前にブラウザの反応がいっとき消えている。正規表現を最適化する余地があるならしたい)
昨日 rubyco（るびこ）の日記 (2007-06-20 正規表現の選択) 経由でウィッシュリストに入れた『詳説 正規表現 第2版』⁑がタイムリーすぎる。
reg = /.*x|a/ s = "a" * 11_000_000 m = reg.match(s)
最終更新: 2016-11-12T11:41+0900
Rubyの、括弧を使った %記法だって。
irb19> re = /%[Qq]?(?<brace>\{[^\{}]*(?:\g<brace>[^\{}]*)*})/
irb19> strings = %w(%{z}a %{a{b}z}c %{a{b}c{d{e}f}z}g %{{{{}}}z}a %{a{b}c %{z}a}b)
irb19> strings.each{|str| p str[re] }
"%{z}"
"%{a{b}z}"
"%{a{b}c{d{e}f}z}"
"%{{{{}}}z}"
nil
"%{z}"
=> ["%{z}a", "%{a{b}z}c", "%{a{b}c{d{e}f}z}g", "%{{{{}}}z}a", "%{a{b}c", "%{z}a}b"]
どの例も正しい範囲( %{ から z} まで)を切り取っているのがわかる。
/%[Qq]?(?<brace>\{(?:[^\{}]++|\g<brace>)*})/
若干速い。同じパターン( [^\{}] )の繰り返しも存在しない。http://fleur.hio.jp/perldoc/perl/5.10.0/pod/perl5100delta.mix.html#Regular_expressions を参考にした。
/%[Qq]?(?<brace>\{(?:[^\{}]+|\g<brace>)*})/
上のものの + が一つ落ちたもの。開き括弧が余分にある文字列を食わせると待てども待てども返ってこない。 http://mlog.euqset.org/archives/ruby-list/42232.html で既に書かれている。それに対する返答が http://blade.nagaokaut.ac.jp/cgi-bin/scat.rb/ruby/ruby-list/42233 。