人力検索はてな
モバイル版を表示しています。PC版はこちら
i-mobile

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

<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>

●質問者: westfish
●カテゴリ:コンピュータ
✍キーワード:MP3 ダメ マッチング 正規表現
○ 状態 :終了
└ 回答数 : 1/1件

▽最新の回答へ

1 ● kitsuneudon
●60ポイント ベストアンサー

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

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

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

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

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

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

◎質問者からの返答

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

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

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

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

関連質問


●質問をもっと探す●



0.人力検索はてなトップ
8.このページを友達に紹介
9.このページの先頭へ
対応機種一覧
お問い合わせ
ヘルプ/お知らせ
ログイン
無料ユーザー登録
はてなトップ