Help us understand the problem. What is going on with this article?

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

More than 5 years have passed since last update.

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]
}
aya_eiya
主要な開発言語は軒並み扱えるオールラウンドプログラマです。サーバーサイドの仕事が多いですが、最近はFlutterとかやってます。
http://aya-eiya.hateblo.jp/
Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away