原です。

> まつもと ゆきひろです

> |原です。あけましておめでとうございます。
> 
> |（３）次のコードで制御がかえらなくなる。
> 
> このケースはほぼワーストケースのようで(否定のor)，マッチする
> 文字が1文字長くなる度にほぼ倍々で実行時間がかかります．私の
> ノートでは
> 
>   "Server: httpd.rb/1.2\n" =~ /(\S|[^a])+b/
> 
> に20秒かかりました．これでは制御か返らなくなるように感じられ
> ると思います．しかし，これを直すのは結構大変なので(たとえば
> 上記のパターンは否定のorで . と同等で，通常は使われないパター
> ンのはずですし)，将来正規表現のルーチンを書き換えるまで(いつ
> になるんだろう)我慢してください．

そういうことですか。我慢します。:-)
もちろんこのコードを実際書いたわけではなくてあくまでサンプルです。

それで思い出したけど、もちろんご存知だと思いますが、ruby が使っ
ている正規表現ルーティンは結構遅くて、例えば、各行が

pizzicato - - [18/Nov/1996:14:17:05 +0900] "GET /news/fj.os.linux/index.shtml HTTP/1.0" 200 95191

みたいな３万行ある httpd のログを

-----^ test.rb
#!/usr/local/bin/ruby
while gets
  ~ /\S+ - - \[\d+\/\w+\/\d+:\d+:\d+:\d+ \S+\] ".*" \d+ \d+/
end
-----$

に食わせると、ここの機械では約５３秒かかりますが、jperl4 で

-----^ test.pl
#!/usr/local/bin/jperl
while (<>) {
    /\S+ - - \[\d+\/\w+\/\d+:\d+:\d+:\d+ \S+\] ".*" \d+ \d+/;
}
-----$

だと約９秒です。^^;
---===-=-=-=-=-=-=-=-=======--=-=-=-==-=-===-=-=-=-=-=-=--=-==-=--
                            Shin-ichro Hara(Nagaoka Univ.of Tech.)