HHeLiBeXの日記 正道編

日々の記憶の記録とメモ‥

文字列のマッチング方法によるパフォーマンスの違い

Javaで文字列のパターンマッチをしようと思ったら、以下の3通りに書ける。

String str = "Hello World";
if (str.matches("H.*W")) {
    ...
}
String str = "Hello World";
if (java.util.regex.Pattern.matches("H.*W", str)) {
    ...
}
String str = "Hello World";
java.util.regex.Pattern p = java.util.regex.Pattern.compile("H.*W");
java.util.regex.Matcher m = m.matcher(str);
if (m.matches()) {
    ...
}

まぁ、1番目は内部で2番目の処理を呼び出しているだけだが。

で、3番目のように正規表現コンパイルを事前に行っておく形とそうでない形とでパフォーマンスにどれだけの差が出るのだろうかとふと思ったので計ってみた。

計測に使用したプログラム

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

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String str = sc.nextLine();
        String regex = sc.nextLine();

        int delta = 100000;
        int max = 2000000;
        for (int i = delta; i <= max; i += delta) {
            System.out.printf("%8d,%8d,%8d,%8d%n",
                i,
                test1(i, str, regex),
                test2(i, str, regex),
                test3(i, str, regex));
        }
    }
    private static long test1(int count, String str, String regex) {
        long S = System.currentTimeMillis();
        for (int i = 0; i < count; ++i) {
            str.matches(regex);
        }
        long G = System.currentTimeMillis();
        return G - S;
    }
    private static long test2(int count, String str, String regex) {
        long S = System.currentTimeMillis();
        for (int i = 0; i < count; ++i) {
            Pattern.matches(regex, str);
        }
        long G = System.currentTimeMillis();
        return G - S;
    }
    private static long test3(int count, String str, String regex) {
        long S = System.currentTimeMillis();
        Pattern p = Pattern.compile(regex);
        for (int i = 0; i < count; ++i) {
            Matcher m = p.matcher(str);
            m.matches();
        }
        long G = System.currentTimeMillis();
        return G - S;
    }
}

入力

正規表現コンパイルにかかる時間に着目しているので、正規表現の複雑さの違いということで2種類の正規表現を試してみた。

  • a: [a-z]+
  • b: [A-Z][a-z]* [A-Z][a-z]*

計測結果

N test1-a test2-a test3-a
100000 191 64 20
200000 172 68 22
300000 79 64 26
400000 83 78 21
500000 100 99 25
600000 120 121 31
700000 138 140 36
800000 154 153 39
900000 176 177 45
1000000 205 197 50
1100000 217 217 54
1200000 235 239 61
1300000 258 259 65
1400000 279 274 71
1500000 306 292 76
1600000 331 326 86
1700000 340 348 89
1800000 364 362 91
1900000 390 383 97
2000000 410 392 100

f:id:hhelibex:20171126155414p:plain

正規表現 b

N test1-b test2-b test3-b
100000 313 92 19
200000 217 130 46
300000 164 161 42
400000 213 217 52
500000 273 271 66
600000 325 326 79
700000 379 389 89
800000 434 431 104
900000 482 490 117
1000000 540 539 131
1100000 584 588 143
1200000 646 641 156
1300000 694 703 173
1400000 745 752 187
1500000 808 816 195
1600000 883 873 211
1700000 932 927 226
1800000 992 984 241
1900000 1032 1020 254
2000000 1083 1088 271

f:id:hhelibex:20171126155536p:plain

まぁ予想通りだが、毎回コンパイルすることになるtest1、test2のケースは、test3に比べて断然遅いことが分かる。 また、正規表現の複雑さが増すと、コンパイルやマッチングに時間が掛かることも読み取れる。