.NETの正規表現パフォーマンスとJavaの比較

Question

大きなテキストファイルの解析中に正規表現のパフォーマンスの問題が発生します。私は次のコードで.NET 4.0を使用しています
：

private static pattern = 
@"((\D|^)(19|20|)\d\d([- /.\\])(0[1-9]|1[012]|[1-9])\4(0[1-9]|[12][0-9]|3[01]|[0-9]) (\D|$))|" + 
@"((\D|^)(19|20|)\d\d([- /.\\])(0[1-9]|[12][0-9]|3[01]|[0-9])\11(0[1-9]|1[012]|[0-9]) (\D|$))|" + 
@"((\D|^)(0[1-9]|1[012]|[0-9])([- /.\\])(0[1-9]|[12][0-9]|3[01]|[0-9])\18(19|20|)\d\d(\D|$))|" + 
@"((\D|^)(0[1-9]|[12][0-9]|3[01]|[0-9])([- /.\\])(0[1-9]|1[012]|[0-9])\25(19|20|)\d\d(\D|$))|" + 
@"((\D|^)(19|20|)\d\d(0[1-9]|1[012])(0[1-9]|[12][0-9]|3[01])(\D|$))|" + 
@"((\D|^)(19|20|)\d\d(0[1-9]|[12][0-9]|3[01])(0[1-9]|1[012])(\D|$))|" + 
@"((\D|^)(0[1-9]|1[012])(0[1-9]|[12][0-9]|3[01])(19|20|)\d\d(\D|$))|" + 
@"((\D|^)(0[1-9]|[12][0-9]|3[01])(0[1-9]|1[012])(19|20|)\d\d(\D|$))|" + 
@"((^|(?<!(\d[- /.\\\d])|\d))(19|20|)\d\d([- /.\\])(0[1-9]|1[012]|[1-9])([^- /.\\\d\w]|$|\s))|" + 
@"((^|(?<!(\d[- /.\\\d])|\d))(0[1-9]|1[012]|[1-9])([- /.\\])(19|20|)\d\d([^- /.\\\d\w]|$|\s))|" + 
@"((^|(?<!(\d[- /.\\\d])|\d))(0[1-9]|1[012]|[1-9])([- /.\\])(0[1-9]|[12][0-9]|3[01])([^- /.\\\d\w]|$|\s))|" + 
@"((^|(?<!(\d[- /.\\\d])|\d))(0[1-9]|[12][0-9]|3[01])([- /.\\])(0[1-9]|1[012]|[1-9])([^- /.\\\d\w]|$|\s))"; 

private static Regex dateRegex = new new Regex(pattern, 
    RegexOptions.Compiled | RegexOptions.IgnoreCase | 
    RegexOptions.IgnorePatternWhitespace | RegexOptions.Multiline); 

public static void Extract(string text) 
{ 
    foreach (Match match in dateRegex.Matches(text)) 
       Console.Writeline("Match {0}",match.Value); 
} 

200試合を含み1MBのテキストファイルの処理時間が〜22secsです。
Javaで同じ正規表現を実行すると、〜13秒という非常に高速な結果が得られます。
正規表現をパーツに分割して実行を並列化することで、.NETコードの処理時間を短縮することができました。
なぜJavaがこの正規表現を処理する方が速いのですか？
この正規表現を処理する.NETのパフォーマンスを改善するにはどうすればよいですか？

乾杯、
ドロン

Answer 1

正規表現パーサのさまざまな味がありますし、Javaの方がパターンに適していますつかいます。しかし、あなたのパターンは、あなたが本当にこの1つを遅くする選択したオプション！

RegexOptions.IgnoreCaseは（この必要があるのでしょうか？）See Want faster regular expressions? Maybe you should think about that IgnoreCase option...

RegexOptions.IgnorePatternWhitespace：あなたはZEROパターンの空白を持っています。これは実際の正規表現解析を遅くするものではありません。これは、ユーザがパターンを文書化できるようにするためだけです。しかし、パターンの作成者（ここで実際には :-)）は、正規表現パーサが妥当な時間内に効果的にパターンを実行するために必要なことを理解していないことを示しているためです。 なぜそのゆっくりの次の声明を見てください。

あなたのパターンはです遅いパターンのあいまいさのためにバックトラックの問題が多すぎます。簡潔でシンプル。

その意味の詳細については、Backtrackingを参照してください。

HTH

Answer 2

私は今、私の分析を完了する時間がありませんが、私はこれまでのところ、私の進捗状況を提供します。あなたの正規表現は、あなたが実際に読むことができるように再フォーマットされています。私が作った唯一の変更は、空きスペースモードを可能にするために、文字クラスにいくつかのスペースをラップすることでした。 80個のキャプチャグループがあります（ほとんどが不要です）。この式は、Dateのさまざまな形式に一致しているようです。改善の余地がたくさんあります：

private static pattern = @" 
    # Match various forms of a Date. 
     (         # Begin $1: 
     (\D|^)        # $2: 
     (19|20|)\d\d      # $3: 
     ([- /.\\])       # $4: 
     (0[1-9]|1[012]|[1-9])    # $5: 
     \4 
     (0[1-9]|[12][0-9]|3[01]|[0-9])  # $6: 
     [ ][ ] 
     (\D|$)        # $7: 
    )          # End $1: 
    | (         # Begin $8: 
     (\D|^)        # $9: 
     (19|20|)\d\d      # $10: 
     ([- /.\\])       # $11: 
     (0[1-9]|[12][0-9]|3[01]|[0-9])  # $12: 
     \11 
     (0[1-9]|1[012]|[0-9])    # $13: 
     [ ][ ] 
     (\D|$)        # $14: 
    )          # End $8: 
    | (         # Begin $15: 
     (\D|^)        # $16: 
     (0[1-9]|1[012]|[0-9])    # $17: 
     ([- /.\\])       # $18: 
     (0[1-9]|[12][0-9]|3[01]|[0-9])  # $19: 
     \18 
     (19|20|)\d\d      # $20: 
     (\D|$)        # $21: 
    )          # End $15: 
    | (         # Begin $22: 
     (\D|^)        # $23: 
     (0[1-9]|[12][0-9]|3[01]|[0-9])  # $24: 
     ([- /.\\])       # $25: 
     (0[1-9]|1[012]|[0-9])    # $26: 
     \25 
     (19|20|)\d\d      # $27: 
     (\D|$)        # $28: 
    )          # End $22: 
    | (         # Begin $29: 
     (\D|^)        # $30: 
     (19|20|)\d\d      # $31: 
     (0[1-9]|1[012])      # $32: 
     (0[1-9]|[12][0-9]|3[01])   # $33: 
     (\D|$)        # $34: 
    )          # End $29: 
    | (         # Begin $35: 
     (\D|^)        # $36: 
     (19|20|)\d\d      # $37: 
     (0[1-9]|[12][0-9]|3[01])   # $38: 
     (0[1-9]|1[012])      # $39: 
     (\D|$)        # $40: 
    )          # End $35: 
    | (         # Begin $41: 
     (\D|^)        # $42: 
     (0[1-9]|1[012])      # $43: 
     (0[1-9]|[12][0-9]|3[01])   # $44: 
     (19|20|)\d\d      # $45: 
     (\D|$)        # $46: 
    )          # End $41: 
    | (         # Begin $47: 
     (\D|^)        # $48: 
     (0[1-9]|[12][0-9]|3[01])   # $49: 
     (0[1-9]|1[012])      # $50: 
     (19|20|)\d\d      # $51: 
     (\D|$)        # $52: 
    )          # End $47: 
    | (         # Begin $53: 
     (^         # Begin $54: 
     | (?<! 
      (\d[- /.\\\d])     # $55: 
      | \d 
     ) 
     )         # End $54: 
     (19|20|)\d\d      # $56: 
     ([- /.\\])       # $57: 
     (0[1-9]|1[012]|[1-9])    # $58: 
     ([^- /.\\\d\w]|$|\s)    # $59: 
    )          # End $53: 
    | (         # Begin $60: 
     (^         # Begin $61: 
     | (?<! 
      (\d[- /.\\\d])     # $62: 
      | \d 
     ) 
     )         # End $61: 
     (0[1-9]|1[012]|[1-9])    # $63: 
     ([- /.\\])       # $64: 
     (19|20|)\d\d      # $65: 
     ([^- /.\\\d\w]|$|\s)    # $66: 
    )          # End $60: 
    | (         # Begin $67: 
     (^         # Begin $68: 
     | (?<! 
      (\d[- /.\\\d])     # $69: 
      |\d 
     ) 
     )         # End $68: 
     (0[1-9]|1[012]|[1-9])    # $70: 
     ([- /.\\])       # $71: 
     (0[1-9]|[12][0-9]|3[01])   # $72: 
     ([^- /.\\\d\w]|$|\s))    # $73: 
    | (         # Begin $74: 
     (^         # Begin $75: 
     | (?<! 
      (\d[- /.\\\d])     # $76: 
      | \d 
     ) 
     )         # End $75: 
     (0[1-9]|[12][0-9]|3[01])   # $77: 
     ([- /.\\])       # $78: 
     (0[1-9]|1[012]|[1-9])    # $79: 
     ([^- /.\\\d\w]|$|\s)    # $80: 
    )          # End $74: 
    "; 

私はもう少し時間があれば、いくつかの推奨改善を加えてこの回答を更新します。その間、他の正規表現のエキスパートは、この改良された部分的にコメントされたバージョンをとり、それを使って自由に実行してください。