| ■76065 / inTopicNo.5) |
Re[1]: 正規表現でフリーズ |
□投稿者/ 魔界の仮面弁士 (351回)-(2015/05/28(Thu) 15:59:04)
|
■No76054 (化學兄弟 さん) に返信
> フリーズが発生する時のテキストの内容はお伝えできないのですが、
そのものズバリでなくても、状況を再現できるダミーデータを提供できませんか?
> あまり正規表現に慣れていないので、
私も正規表現は得意なほうでは無いので、あくまで 一般論 として書きますが、
たとえ単純な短い正規表現であっても、その内容次第では、
対象文字列が長くなるほど、加速度的に遅くなってしまうことがあります。
遅くなる要因は幾つかありますが、例を挙げるとすれば OR 分岐や繰り返し表現などです。
繰り返し処理は特に顕著です。極端な例を挙げれば、
Const TAG_PTN As String = "(.*)*^" '探索結果は「^」と同じ
の場合、常に行頭の 0 文字にマッチすることが自明ですが、
そこに至るまでにはすべての組み合わせが試されることになるため、
文字数が長くなるにつれ、速度低下が顕著となります。
実際、相手が 30 文字程度であっても、相当に長い時間がかかっていました。
Const TAG_PTN As String = "(.*)*^"
For n As Integer = 0 To 40
Dim sw As Stopwatch = Stopwatch.StartNew()
Dim htmlPart As String = StrDup(n, "@"c)
Dim isMatch As Boolean = Regex.IsMatch(htmlPart, TAG_PTN, RegexOptions.IgnoreCase)
sw.Stop()
Console.WriteLine("{0}, {1:F4}", n, sw.Elapsed.TotalMilliseconds)
Next
当方環境での例ですが、上記のコードで
18文字 => 約64ミリ秒
19文字 => 約128ミリ秒
20文字 => 約256ミリ秒
21文字 => 約512ミリ秒
22文字 => 約1秒
23文字 => 約2秒
24文字 => 約4秒
25文字 => 約8秒
26文字 => 約16秒
のように、文字数に応じてほぼ倍々の時間がかかっていました。
このまま続けていれば、40 文字で 4 分以上かかる見込みですね。
正規表現を "((.*)*)*^" にすれば、繰り返し回数がさらに伸びることでしょう。
そして、もう一つ例に挙げた OR 分岐 ですが…今回の場合、
> Const TAG_PTN As String = "^<font(.|\s)+</font>$"
の「(.|\s)」ですが、\s というのは空白文字で、. は任意文字ですよね。
. には \s の意味も含まれるので、OR 探索は不要に見えるのですが、
自らが改善案として提示された "(.|\s)+" → ".+" ではマズイのでしょうか?
「空白文字」に合致した場合の検索パターンが、
(.|\s) の場合、. の倍になってしまい、無駄に見えます。
それ自体は僅かな差だと思いますが、「+」による繰り返し処理の内側にあるため、
マッチングする文字数が長くなるほど、その差は累積されてしまうでしょう。
それでなくとも、OR 分岐は比較的低速となりがちです。
[abc] で済む処理を (a|b|c) と書いた場合、意味は同じでも
後者の方がパフォーマンス面では劣ります。
実際、
Const TAG_PTN1 As String = "(a|b|c|d|e)*"
Const TAG_PTN2 As String = "[abcde]*"
という 2 パターンを、探索回数が極端に多くなるような文字列
Dim htmlPart As String = StrDup(1000, "b"c)
に対して比較してみたところ、当方環境では
TAG_PTN1 => 平均 0.168 ミリ秒
TAG_PTN2 => 平均 0.068 ミリ秒
のように、やはり OR 分岐の方が倍以上遅い結果となっていました。
正規表現のパフォーマンスに関して、下記も参照してみてください。
https://msdn.microsoft.com/ja-jp/library/dsy130b4.aspx
https://msdn.microsoft.com/ja-jp/library/gg578045.aspx
|
|