- 677 名前：デフォルトの名無しさん (ﾜｯﾁｮｲ eb5b-BJNc) mailto:sage [2017/03/03(金) 23:56:21.24 ID:ljnBJEQ70.net]
- >>668-669
否定先読みも知らなかった。ありがとう。
ただ、俺が言うのもおかしいが、
> non-greedy は最長一致させてからバックトラック(前に戻る)して最短一致させている (>>669)
これは多分違う。明らかに実装依存だし、MDNはそちらの想定とは異なることを示唆している。
> x?
> *、+、?、{} といった量指定子の直後に使用した場合は、非欲張り (non-greedy)量指定子（最小回数にマッチ【訳注: スキップ優先】）となります。
> これはデフォルトのそれらとは逆であり、デフォルトのそれらは、貪欲 (greedy)量指定子（最大回数にマッチ【訳注: 繰り返し優先】）です。
> https://developer.mozilla.org/ja/docs/Web/JavaScript/Reference/Global_Objects/RegExp
greedyの結果は必ずnon-greedyの結果を内包する為、そちらの言うとおりの実装も可能だが、
それはあくまで既存のgreedy専用ルーチンにnon-greedyを後付した場合だ。
最初から両方とも実装する気なら、入力文字列/正規表現文字列での2重ループで、
内外を入れ替えられるように構成すればいいだけ。（実際は別に作ってif文だと思うが）
この場合、「スキップ」が正規表現文字列の進行、「繰り返し」が入力文字列の進行を表している。
「スキップ」が内側ならnon-greedy、「繰り返し」が内側ならgreedyになる。
実際にどうかはコード見るしかないが。
この仮定どおりだと、今回に関してはnon-greedyが一番効率がいい。
正規表現検索が遅くなる理由は、内部のマッチング候補が無限に膨らんでいくからだ。
str.match(/\*\*(.*?)\*\*/g,'@') だとまず終端**であるか確認し、
駄目なら一つ進めてまた終端かどうか試すわけで、内部候補は最小の状態で保てる。
理屈上は線形時間*2で済む。(この場合は*3になるのか？)
話を総合すると、PCREは669の言うとおり、JSは多分違って670の言うとおり、ということなのかな？
まあ今回の部分はパフォーマンスは必要ないところなので、どちらでもいいんだが。
なお余談だが.NETではバックトラッキングを制御するための構文もあるようだ。
> 非バックトラッキング部分式、後読みアサーション、および先読みアサーション
> https://msdn.microsoft.com/ja-jp/library/dsy130b4(v=vs.110).aspx
|
 |
