文字列検索の速さ比較

Listから条件を満たす文字列を検索する場合で、以下の状況を考えます。

• 完全一致
• 前方一致
• 後方一致
• 部分一致
• A or B
• A and B

それぞれについて、以下の2つの速さを比較しました。

• 正規表現でmatchesメソッドを使う
• matches以外の以下のメソッドを使う
  • equals
  • startsWith
  • endsWith
  • contains

実行環境は以下の通りです。

• DELL VOSTRO 1540
• Windows 10 Pro 32bit
• Intel Celelron 2.00 GHZ
• メモリ 2.0GB
• HDは約300GB

ソースと実行結果

2つの方法を3000回繰り返した結果を比較しました。結論から書くと、matches以外のメソッドを使った方が速いです。

以下、ソースと実行結果です。

完全一致

ソース

    private static List<String> words = new ArrayList<String>();
    static {
        words.add("ab11cd");
        words.add("ab12cd");
        words.add("ab13cd");
        words.add("ab21cd");
        words.add("ab22cd");
        words.add("ab23cd");
    }

    public static void main(String[] args) {

        String s = "ab13cd";
        String reg = String.format("^%s$", s);

        int count = 3000;

        long start, end;
        start = System.currentTimeMillis();
        for (int i = 0; i < count; i++) {
            test1(reg);
        }
        end = System.currentTimeMillis();
        System.out.println("test1: " + (end - start));

        start = System.currentTimeMillis();
        for (int i = 0; i < count; i++) {
            test2(s);
        }
        end = System.currentTimeMillis();
        System.out.println("test2: " + (end - start));


        System.out.println("確認");
        System.out.println("test1: " + test1(reg));
        System.out.println("test2: " + test2(s));

    }

    public static List<String> test1(String reg) {
        List<String> list = new ArrayList<>();
        for (String word : words) {
            if (word.matches(reg)) {
                list.add(word);
            }
        }
        return list;
    }

    public static List<String> test2(String searchWord) {
        List<String> list = new ArrayList<>();
        for (String word : words) {
            if (word.equals(searchWord)) {
                list.add(word);
            }
        }
        return list;
    }

結果

test1: 39
test2: 2
確認
test1: [ab13cd]
test2: [ab13cd]

前方一致

ソース

    private static List<String> words = new ArrayList<String>();
    static {
        words.add("ab11cd");
        words.add("ab12cd");
        words.add("ab13cd");
        words.add("ab21cd");
        words.add("ab22cd");
        words.add("ab23cd");
    }

    public static void main(String[] args) {

        String s = "ab2";
        String reg = String.format("^%s.*$", s);

        int count = 3000;

        long start, end;
        start = System.currentTimeMillis();
        for (int i = 0; i < count; i++) {
            test1(reg);
        }
        end = System.currentTimeMillis();
        System.out.println("test1: " + (end - start));

        start = System.currentTimeMillis();
        for (int i = 0; i < count; i++) {
            test2(s);
        }
        end = System.currentTimeMillis();
        System.out.println("test2: " + (end - start));


        System.out.println("確認");
        System.out.println("test1: " + test1(reg));
        System.out.println("test2: " + test2(s));

    }

    public static List<String> test1(String reg) {
        List<String> list = new ArrayList<>();
        for (String word : words) {
            if (word.matches(reg)) {
                list.add(word);
            }
        }
        return list;
    }

    public static List<String> test2(String searchWord) {
        List<String> list = new ArrayList<>();
        for (String word : words) {
            if (word.startsWith(searchWord)) {
                list.add(word);
            }
        }
        return list;
    }

結果

test1: 45
test2: 3
確認
test1: [ab21cd, ab22cd, ab23cd]
test2: [ab21cd, ab22cd, ab23cd]

後方一致

ソース

    private static List<String> words = new ArrayList<String>();
    static {
        words.add("ab11cd");
        words.add("ab12cd");
        words.add("ab13cd");
        words.add("ab21cd");
        words.add("ab22cd");
        words.add("ab23cd");
    }

    public static void main(String[] args) {

        String s = "1cd";
        String reg = String.format("^.*%s$", s);

        int count = 3000;

        long start, end;
        start = System.currentTimeMillis();
        for (int i = 0; i < count; i++) {
            test1(reg);
        }
        end = System.currentTimeMillis();
        System.out.println("test1: " + (end - start));

        start = System.currentTimeMillis();
        for (int i = 0; i < count; i++) {
            test2(s);
        }
        end = System.currentTimeMillis();
        System.out.println("test2: " + (end - start));


        System.out.println("確認");
        System.out.println("test1: " + test1(reg));
        System.out.println("test2: " + test2(s));

    }

    public static List<String> test1(String reg) {
        List<String> list = new ArrayList<>();
        for (String word : words) {
            if (word.matches(reg)) {
                list.add(word);
            }
        }
        return list;
    }

    public static List<String> test2(String searchWord) {
        List<String> list = new ArrayList<>();
        for (String word : words) {
            if (word.endsWith(searchWord)) {
                list.add(word);
            }
        }
        return list;
    }

結果

test1: 47
test2: 3
確認
test1: [ab11cd, ab21cd]
test2: [ab11cd, ab21cd]

部分一致

ソース

    private static List<String> words = new ArrayList<String>();
    static {
        words.add("ab11cd");
        words.add("ab12cd");
        words.add("ab13cd");
        words.add("ab21cd");
        words.add("ab22cd");
        words.add("ab23cd");
    }

    public static void main(String[] args) {

        String s = "2c";
        String reg = String.format("^.*%s.*$", s);

        int count = 3000;

        long start, end;
        start = System.currentTimeMillis();
        for (int i = 0; i < count; i++) {
            test1(reg);
        }
        end = System.currentTimeMillis();
        System.out.println("test1: " + (end - start));

        start = System.currentTimeMillis();
        for (int i = 0; i < count; i++) {
            test2(s);
        }
        end = System.currentTimeMillis();
        System.out.println("test2: " + (end - start));


        System.out.println("確認");
        System.out.println("test1: " + test1(reg));
        System.out.println("test2: " + test2(s));

    }

    public static List<String> test1(String reg) {
        List<String> list = new ArrayList<>();
        for (String word : words) {
            if (word.matches(reg)) {
                list.add(word);
            }
        }
        return list;
    }

    public static List<String> test2(String searchWord) {
        List<String> list = new ArrayList<>();
        for (String word : words) {
            if (word.contains(searchWord)) {
                list.add(word);
            }
        }
        return list;
    }

結果

test1: 48
test2: 3
確認
test1: [ab12cd, ab22cd]
test2: [ab12cd, ab22cd]

A or B

ソース

    private static List<String> words = new ArrayList<String>();
    static {
        words.add("ab11cd");
        words.add("ab12cd");
        words.add("ab13cd");
        words.add("ab21cd");
        words.add("ab22cd");
        words.add("ab23cd");
    }

    public static void main(String[] args) {

        String s1 = "12c";
        String s2 = "b22";
        String reg = String.format("^.*(%s|%s).*$", s1, s2);

        int count = 3000;

        long start, end;
        start = System.currentTimeMillis();
        for (int i = 0; i < count; i++) {
            test1(reg);
        }
        end = System.currentTimeMillis();
        System.out.println("test1: " + (end - start));

        start = System.currentTimeMillis();
        for (int i = 0; i < count; i++) {
            test2(s1, s2);
        }
        end = System.currentTimeMillis();
        System.out.println("test2: " + (end - start));


        System.out.println("確認");
        System.out.println("test1: " + test1(reg));
        System.out.println("test2: " + test2(s1, s2));

    }

    public static List<String> test1(String reg) {
        List<String> list = new ArrayList<>();
        for (String word : words) {
            if (word.matches(reg)) {
                list.add(word);
            }
        }
        return list;
    }

    public static List<String> test2(String s1, String s2) {

        List<String> list = new ArrayList<>();
        for (String word : words) {
            if (word.contains(s1) || word.contains(s2)) {
                list.add(word);
            }
        }
        return list;
    }

結果

test1: 70
test2: 5
確認
test1: [ab12cd, ab22cd]
test2: [ab12cd, ab22cd]

A and B

ソース

    private static List<String> words = new ArrayList<String>();
    static {
        words.add("ab11cd");
        words.add("ab12cd");
        words.add("ab13cd");
        words.add("ab21cd");
        words.add("ab22cd");
        words.add("ab23cd");
    }

    public static void main(String[] args) {

        String s1 = "b";
        String s2 = "3c";
        String reg = String.format("(?=.*%s)(?=.*%s).*$", s1, s2);

        int count = 3000;

        long start, end;
        start = System.currentTimeMillis();
        for (int i = 0; i < count; i++) {
            test1(reg);
        }
        end = System.currentTimeMillis();
        System.out.println("test1: " + (end - start));

        start = System.currentTimeMillis();
        for (int i = 0; i < count; i++) {
            test2(s1, s2);
        }
        end = System.currentTimeMillis();
        System.out.println("test2: " + (end - start));


        System.out.println("確認");
        System.out.println("test2: " + test1(reg));
        System.out.println("test1: " + test2(s1, s2));

    }

    public static List<String> test1(String reg) {
        List<String> list = new ArrayList<>();
        for (String word : words) {
            if (word.matches(reg)) {
                list.add(word);
            }
        }
        return list;
    }

    public static List<String> test2(String s1, String s2) {

        List<String> list = new ArrayList<>();
        for (String word : words) {
            if (word.contains(s1) && word.contains(s2)) {
                list.add(word);
            }
        }
        return list;
    }

結果

test1: 77
test2: 4
確認
test2: [ab13cd, ab23cd]
test1: [ab13cd, ab23cd]