以下のような正規表現を使ってマッチングを行うと時間がものすごくかかります。.*?以降を取り除くとすぐに結果が出るようになるのでこれが問題なのではないかと思いますが、どうしてこれではダメなのでしょうか?


<a\shref='(report\.jsp\?reportId=.+?)'>
<span\sclass='reportitem'>([^<>]+?)</span></a>
.*?
<span\sclass='reportitem'>([^<>]+?)</span>
.*?
<a\shref='(sendAudio.jsp\?reportAudioFileId=\d+?)'><span class='reportitem'>MP3</span></a>

回答の条件
  • 1人2回まで
  • 登録:2006/07/03 02:34:33
  • 終了:2006/07/08 00:26:00

ベストアンサー

id:kitsuneudon No.1

kitsuneudon回答回数35ベストアンサー獲得回数22006/07/03 08:45:52

ポイント60pt

私の環境ではそれほど遅くはならなかったですが、おそらくバックトラッキングが発生しているからだと思われます。

.*?にマッチさせる部分が長すぎてはいませんでしょうか。

.*?は最短マッチなので、まず最初に一番短い文字列''(0文字幅)にマッチします。しかし、そのあとに<span\sclass='reportitem'>がないので.*?の幅をちょっとずつ広げていってうしろに<span\sclass='reportitem'>がくるまで探し続けます。

一般に、長い文字列を正規表現にあてるのはよくないと思います。別のアルゴリズムを考えた方がいいかもしれません。

ここが参考になるかもしれません。

http://www.kt.rim.or.jp/~kbk/perl-5.8/perlretut.html

id:westfish

なるほど、二つめの.*?以降を削った場合は1ミリ秒程度で処理が終わるので二つ.*?があることが問題なのかとも思ったのですが、それだけが原因とは考えにくいようです。

試しに"<.*?>.*?<.*?>.*?<.*?>"という正規表現に「不等号で囲われた100文字の文字列の間を100000文字の文字列でうめた文字列を100回繰り返した文字列」を入力してみても1秒程度かかるかかからないかでした。

ちなみに質問文であげた正規表現は以下のサイトを入力として与えた場合に数秒では済まない時間がかかりました。

http://www.bootcamp.com/archives.jsp

2006/07/03 15:48:18

コメントはまだありません

この質問への反応(ブックマークコメント)

「あの人に答えてほしい」「この質問はあの人が答えられそう」というときに、回答リクエストを送ってみてましょう。

これ以上回答リクエストを送信することはできません。制限について

絞り込み :
はてなココの「ともだち」を表示します。
回答リクエストを送信したユーザーはいません