[ruby-dev:2987] Re: Regexp の実行が遅い気がします

まつもと ゆきひろです

In message "[ruby-dev:2973] Re: Regexp の実行が遅い気がします"
    on 98/06/23, Kazunori NISHI <[e-mail]> writes:

|西＠九大です。
|
|From: [e-mail] (Yukihiro Matsumoto)
|> に変えてexact stringを伸ばすだけで劇的に速くなりますが…．
|> # 具体的にはhttpからgoo.ne.jpになってます．
|
|おぉ、速くなりました！(0.02秒)
|「.」のクォートし忘れが、ここまで影響するとは思いませんでした、失礼。

結局長い文字列に対して複雑なパターンを1文字ずつずらしながら
マッチを繰り返すことが原因のようです．今の正規表現ルーチンは
アンカーが無い複雑なパターンに弱いですね．

具体的に弱いのは

  * exact stringで絞り込めないパターンで

      パターン中の最長のexact stringを含まない文字列に対して
      はマッチを行いません．

  * 先頭にexact stringがなく(fastmapが効かない)

      パターンの先頭にマッチしうる文字でマッチの刈り込みを行
      います．\Sのような多くの文字にマッチするパターンが先頭
      だとこの刈り込みがほとんど行われません．

  * ^, \Aなどのアンカーがない

      アンカーがあると繰り返しマッチを行いません

  * 複雑なパターンで対象文字列が長い

      上記のような「最適化」が行えないパターンでは，結局一文
      字ずつずらしてマッチを繰り返す事になりますが，こういう
      場合でパターンが複雑で文字列が長いと悲しい事になります．

です．高速化のアイディアがあればぜひお聞かせ下さい．

|「パターンが複雑になっても、マッチング回数が少ない方が速い」という先入
|観があったのですが、こういうものなんでしょうか？

プログラム上のマッチング回数が減ってても，内部のマッチング回
数が増えれば一緒です．効率を考えるなら上のような条件で絞り込
みが効くパターンを使うのが良いでしょう．

|ruby-4.0 くらいまでには、お願いします。

考えてみます．なかなか難しそう．

|> |「Regexp 関係にバグがある」事を期待しつつ、とりあえず御報告まで。
|> 
|> とくにこれというバグではなく，ちょっとずつまずい点が重なって
|> の現象のようです．いやな感じ．^^;;;
|
|そうですね、これだと「バグの存在」を期待してる厭味な人みたいですね。
|失礼しました。「Regexp 関係のバグの露呈」を期待しつつ、C-cC-c

あ，「いやな感じ」なのはregex.cの具合の方です．西さんはイヤ
じゃないです，全然．おヒマでしたら，遊びに来て下さい．
# いや，マジで．^^;;;
                                まつもと ゆきひろ /:|)