ちょっとしたことがGroovy「めちゃくちゃ重い正規表現をどうにかする確認」

Javaの正規表現のせいでCPU死んでいたのを調査、修正の検討の際のテストをGroovyでやってみました。

実際の正規表現は、(ABCD)のところがもっと複雑なマッチになっているので後戻り発生すると本当に死ぬ。

なお、(ABCD)の部分によっては完全に一致する検索ではないです。

完全に一致する結果を返したい場合は、もうちょっと工夫する必要があります。

問題となっていた部分ではこの程度の一致で十分でした。

fast_30.groovy

import java.util.regex.Matcher
import java.util.regex.Pattern

def stopWatch = {c->
    s = System.nanoTime()
    c()
    def w = System.nanoTime() - s
    if(w <      1000000)
        "${w /  1000} [microsec]"
    else if(w < 1000000000)
        "${w /  1000000} [millsec]"
    else
        "${w /  1000000000} [sec]"
}

def slowMatch = {target ->
  def r 
  def m = Pattern.compile(/[^.,;]{30,}(ABCD)/).matcher(target) // <- 後ろから読み直しちゃうよ。。。O(n^2)
  println "slow=" + stopWatch {
    r = m.find()
  }
  (r)?m.group().length():r
}

def fastMatch = {target ->
  def r = false
  def p = Pattern.compile(/[^.,;]{30}(ABCD)/)
  def m = p.matcher(target)
  def l = []
  def ret
  println "fast=" + stopWatch {
    if(m.find())
    for(def s:target.split(/[.,;]/)){
        if(s.length() >= 34){
            def m2 = p.matcher(s)
            r = m2.find()
            if(r) {
              ret = s
              break
            }
        }
    }
  }
  (r)?ret.length():r
}

[
case01:"0123456789",
case02:"0123456789"*2,
case03:"0123456789"*3,
case04:"0123456789"*3+".",
case05:"0123456789"*2.9+".",
case06:"0123456789"*2.9+".ABCD.",
case07:"0123456789"*3+".ABCD.",
case08:"0123456789"*3+":ABCD.",
case09:"0123456789"*3+".ABCD.ABCD.",
case10:"0123456789"*3+":ABCD.ABCD.",
case11:"0123456789"*2000+".ABCD.", // <- このときにslowが遅い死ぬほど重い。なぜかってぇと後ろから読み直して結局見つからないから
case12:"0123456789"*2000+":ABCD.", // <- このときだけfastのが遅い、なぜかってぇと一致が最後方にあるから
case13:"0123456789.ABCD."*500,
case14:"0123456789.ABCD."*500+"0123456789"*3+"ABCD.",
cale15:""
].collect { k,v ->
  println k
  def result = slowMatch(v)
  assert result == fastMatch(v)
  ["$k":result]
}