なぜ\s*
(またはさらに\s\s*
)を\s+
と置き換えると、この入力が高速化されるのでしょうか?このPerl正規表現の ` s s *`より ` s s *`の方がずっと速いのはなぜですか?
use Benchmark qw(:all);
$x=(" " x 100000) . "_\n";
$count = 100;
timethese($count, {
'/\s\s*\n/' => sub { $x =~ /\s\s*\n/ },
'/\s+\n/' => sub { $x =~ /\s+\n/ },
});
私は私のコードでは遅い正規表現s/\s*\n\s*/\n/g
に気づいた - 最後にここにあるいくつかの非スペースでスペースがたくさんからなる450キロバイトの入力ファイル、および最後の改行を与えられたとき、正規表現は掛かっており、決して終わらない。
私は直感的に正規表現をs/\s+\n/\n/g; s/\n\s+/\n/g;
に置き換えました。すべて正常でした。
なぜそれがずっと速いのですか?
Matching REx "\s*\n" against " _%n"
Matching stclass ANYOF{i}[\x09\x0a\x0c\x0d ][{non-utf8-latin1-all}{unicode_all}] against " _%n" (9 bytes)
0 <> < _%n> | 1:STAR(3)
SPACE can match 7 times out of 2147483647...
failed...
1 < > < _%n> | 1:STAR(3)
SPACE can match 6 times out of 2147483647...
failed...
2 < > < _%n> | 1:STAR(3)
SPACE can match 5 times out of 2147483647...
failed...
3 < > < _%n> | 1:STAR(3)
SPACE can match 4 times out of 2147483647...
failed...
4 < > < _%n> | 1:STAR(3)
SPACE can match 3 times out of 2147483647...
failed...
5 < > < _%n> | 1:STAR(3)
SPACE can match 2 times out of 2147483647...
failed...
6 < > < _%n> | 1:STAR(3)
SPACE can match 1 times out of 2147483647...
failed...
8 < _> <%n> | 1:STAR(3)
SPACE can match 1 times out of 2147483647...
8 < _> <%n> | 3: EXACT <\n>(5)
9 < _%n> <> | 5: END(0)
Match successful!
Matching REx "\s+\n" against " _%n"
Matching stclass SPACE against " _" (8 bytes)
0 <> < _%n> | 1:PLUS(3)
SPACE can match 7 times out of 2147483647...
failed...
は、私はPerlの5.10+はすぐに改行が存在しない場合(これを実行せずに)正規表現を失敗します知っている:
re Debug => "EXECUTE"
を使用した後、私は
\s+
バージョンは何とか一つだけの繰り返しで実行するように最適化されて気づきました。私はそれがしている検索の量を減らすために改行の場所を使用していると思われる。上記のすべての場合、それは巧妙に関連するバックトラッキングを減らすようです(通常、
/\s*\n/
はスペース文字列に対して指数関数的な時間を要します)。誰でも
\s+
のバージョンがそれほど高速である理由を知ることができますか?
また、\s*?
はスピードアップを提供していません。
'\ s'も' \ n'にマッチするのに役立ちません。改行ではない空白文字は '[^ \ S \ n]'です。あるいは、 "水平空白" '\ h'を使うこともできます。 – Borodin
'/ \ s * \ n /'と '/ \ s + \ n /' [ライブ参照](http://rextester.com/DSXF83795)との比較を絞り込むことができます。また、文字列が一致しない場合は高速になることに注意してください。試合の場合、同じ時間がかかるようです –
@ThomasAyoub私はそれが比較を狭めているとは思わない。 '\ s \ s *'は '\ s +'と同じでなければなりませんが、投稿された2つの正規表現は異なる正規表現です。しかし、あなたが投稿した2人の間でさえパフォーマンスの違いが驚くべきことであることに私は同意します! – rjh