量指定子(greedy,reluctant,possessive)による性能の違い

以前に正規表現における量指定子(greedy,reluctant,possessive)とはなにかというタイトルでブログを書きましたが、その時に調べた公式ドキュメントには量指定子によって性能差があると書いてありました。

具体的には、possessiveはgreedyに比べてバックトラックを行わないため実行速度が早い、とのことです。

試しにそれぞれの量指定子による正規表現マッチを1000万回行うコードを書いたところ、実行速度は次のようになりました。

greedy :7297 ms
reluctant :6125 ms
possessive :19624 ms

確かにpossessiveに比べてgreedyのほうが早いです。実行速度にして1/3から1/2程度。

性能にシビアなコードを書くときは意識した方が良さそうですね。

付録　測定に使ったコード(リンクしたgistと同じもの)

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

public class RegExpTest {

 private static String str = "xfooxxxxxxfoo";
 private static int max = 10000000;
 public static void main(String args[]){

  runGreedy();
  runReluctant();
  runPossessive();
 }
 
 public static void runGreedy(){
  long before = System.currentTimeMillis();
  String regex = ".*foo";

  for(int i = 0; i < max ; i++){
   Pattern p = Pattern.compile(regex);
   Matcher m = p.matcher(str);
   m.find();
  }
  
  long after = System.currentTimeMillis();
  
  System.out.println("greedy :" + (after - before));
 }
 
 public static void runReluctant(){
  long before = System.currentTimeMillis();
  String regex = ".*?foo";

  for(int i = 0; i < max ; i++){ 
   Pattern p = Pattern.compile(regex);
   Matcher m = p.matcher(str);

   m.find();
  }
  
  long after = System.currentTimeMillis();
  
  System.out.println("reluctant :" + (after - before));
 }

 public static void runPossessive(){
  long before = System.currentTimeMillis();
  String regex = ".*+foo";

  for(int i = 0; i < max ; i++){
   Pattern p = Pattern.compile(regex);
   Matcher m = p.matcher(str);
   m.find();
  }
  
  long after = System.currentTimeMillis();
  
  System.out.println("possessive :" + (after - before));
 }
}