[ruby-list:47310] Re: マッチしない正規表現「.*?」が遅い?

成瀬です。

(2010/08/17 11:44), SATOH Fumiyasu wrote:
> さとうふみやす @ OSSTech です。
> 
> At Tue, 17 Aug 2010 08:43:44 +0900,
> [e-mail] wrote:
>> rubyの実装に詳しいわけでも、正規表現に強いわけでもないですが。。。
> 
> 同じく…。
> 
>> 変数　t　の中に9999回現れる "<X" が/<X(?:\s[^>]*)?>.*?<\/Y>/の
>> 頭にマッチします。ですから　9999回 変数tの最後まで評価します。
>> だから遅いのでは。
> 
> ("<X\n><Y\n>"*9999).lenth はたったの 79992 ですから、それを 9999回
> だとしても、CPU にとっては大したことはないんじゃないでしょうか。
> ちなみに CPU は Intel Core 2 Duo T7100 (1.8GHz) を使っています。

/<X(?:\s[^>]*)?>.*?<\/Y>/ という正規表現は、
A: /<X(?:\s[^>]*)?>.*?
B: <\/Y>/
という3つの部分に分けられます。
Aがマッチしうるヶ所は文字列全体で9999ヶ所あり、その位置をn番目とすると、
Bがマッチしうるヶ所は9999-nヶ所あります。
ので、O(n^2)になるのでなかなか大変な処理ということになります。

> 先のメールの実行例にあるように、Perl や Python では一瞬で
> 終わるので、Ruby の実装に特徴か問題があるんじゃないかと思っているのですが。
> Ruby 1.9 でも同じく遅いので、正規表現エンジンの問題ではなさそうです。

Python については知りませんが、Perl や PCRE では一定回数ループすると
探索を打ち切るような仕組みを入れていると聞きます。
Ruby の場合は 1.8 と 1.9 でエンジンが違いますが、どちらもそのような仕組みを
入れていない (有効にしていない) のです。
このような仕組みを入れても組み合わせが爆発するパターンは残ること、
カウンタを入れることによって速度的にペナルティがあることが理由です

>> /<X(?:\s[^>]*)?>.*?<\/Y>/　ですと文字列最後まで評価するのは　一ヶ所だけだったのが
>> /<X(?:\s.*?)?>.*?<\/Y>/ ですと、二ヶ所になるのでさらに遅くなる。
>>
>> "<X" の出現回数 9999回文字列最後まで評価していたのが
>> 8万*9999回（8万の方はだんだん少なくなるけれど）文字列の最後まで評価することになりますから。

こちらは O(n^3)ですね。

-- 
NARUSE, Yui  <[e-mail]>