Java регулярные выражения: производительность и альтернатива

Ответ 1

Регулярные выражения в Java скомпилированы во внутреннюю структуру данных. Эта компиляция является трудоемким процессом. Каждый раз, когда вы вызываете метод String.matches(String regex), указанное регулярное выражение скомпилируется снова.

Итак, вы должны скомпилировать свое регулярное выражение только один раз и повторно использовать его:

Pattern pattern = Pattern.compile(regexPattern);
for(String value : values) {
    Matcher matcher = pattern.matcher(value);
    if (matcher.matches()) {
        // your code here
    }
}

Ответ 2

Рассмотрим следующий (быстрый и грязный) тест:

import java.util.ArrayList;
import java.util.List;
import java.util.Random;
import java.util.regex.Matcher;
import java.util.regex.Pattern;

public class Test3 {

    // time that tick() was called
    static long tickTime;

    // called at start of operation, for timing
    static void tick () {
        tickTime = System.nanoTime();
    }

    // called at end of operation, prints message and time since tick().
    static void tock (String action) {
        long mstime = (System.nanoTime() - tickTime) / 1000000;
        System.out.println(action + ": " + mstime + "ms");
    }

    // generate random strings of form AAAABBBCCCCC; a random 
    // number of characters each randomly repeated.
    static List<String> generateData (int itemCount) {

        Random random = new Random();
        List<String> items = new ArrayList<String>();
        long mean = 0;

        for (int n = 0; n < itemCount; ++ n) {
            StringBuilder s = new StringBuilder();
            int characters = random.nextInt(7) + 1;
            for (int k = 0; k < characters; ++ k) {
                char c = (char)(random.nextInt('Z' - 'A') + 'A');
                int rep = random.nextInt(95) + 5;
                for (int j = 0; j < rep; ++ j)
                    s.append(c);
                mean += rep;
            }
            items.add(s.toString());
        }

        mean /= itemCount;
        System.out.println("generated data, average length: " + mean);

        return items;

    }

    // match all strings in items to regexStr, do not precompile.
    static void regexTestUncompiled (List<String> items, String regexStr) {

        tick();

        int matched = 0, unmatched = 0;

        for (String item:items) {
            if (item.matches(regexStr))
                ++ matched;
            else
                ++ unmatched;
        }

        tock("uncompiled: regex=" + regexStr + " matched=" + matched + 
             " unmatched=" + unmatched);

    }

    // match all strings in items to regexStr, precompile.
    static void regexTestCompiled (List<String> items, String regexStr) {

        tick();

        Matcher matcher = Pattern.compile(regexStr).matcher("");
        int matched = 0, unmatched = 0;

        for (String item:items) {
            if (matcher.reset(item).matches())
                ++ matched;
            else
                ++ unmatched;
        }

        tock("compiled: regex=" + regexStr + " matched=" + matched + 
             " unmatched=" + unmatched);

    }

    // test all strings in items against regexStr.
    static void regexTest (List<String> items, String regexStr) {

        regexTestUncompiled(items, regexStr);
        regexTestCompiled(items, regexStr);

    }

    // generate data and run some basic tests
    public static void main (String[] args) {

        List<String> items = generateData(1000000);
        regexTest(items, "A*");
        regexTest(items, "A*B*C*");
        regexTest(items, "E*C*W*F*");

    }

}

Строки представляют собой случайные последовательности из 1-8 символов с каждым символом, имеющим 5-100 раз подряд (например, "AAAAAAGGGGGGDDFFFFFF" ). Я догадался, основываясь на ваших выражениях.

Конечно, это может быть не репрезентативным для вашего набора данных, но временные оценки для применения этих регулярных выражений до 1 миллиона случайным образом генерируют строки средней длины 208 каждый на моем небольшом двуядерном i5 с частотой 2,3 ГГц:

Regex      Uncompiled    Precompiled
A*          0.564 sec     0.126 sec
A*B*C*      1.768 sec     0.238 sec
E*C*W*F*    0.795 sec     0.275 sec

Фактический выход:

generated data, average length: 208
uncompiled: regex=A* matched=6004 unmatched=993996: 564ms
compiled: regex=A* matched=6004 unmatched=993996: 126ms
uncompiled: regex=A*B*C* matched=18677 unmatched=981323: 1768ms
compiled: regex=A*B*C* matched=18677 unmatched=981323: 238ms
uncompiled: regex=E*C*W*F* matched=25495 unmatched=974505: 795ms
compiled: regex=E*C*W*F* matched=25495 unmatched=974505: 275ms

Даже без ускорения предварительно скомпилированных выражений и даже с учетом того, что результаты сильно варьируются в зависимости от набора данных и регулярного выражения (и даже учитывая, что я нарушил основное правило надлежащих тестов производительности Java и сначала забыл о первом HotSpot) это очень быстро, и я все еще задаюсь вопросом, действительно ли узкое место действительно так, как вы думаете.

После переключения на предварительно скомпилированные выражения, если вы все еще не отвечаете своим фактическим требованиям производительности, выполните некоторые профилирования. Если вы обнаружите, что ваше узкое место все еще находится в вашем поиске, подумайте о внедрении более оптимизированного алгоритма поиска.

Например, если ваш набор данных подобен моему тестовому набору выше: если ваш набор данных известен заранее, уменьшите каждый элемент в нем до меньшего строкового ключа, удалив повторяющиеся символы, например. для "AAAAAAABBBBCCCCCCC", сохраните его на карте, определенной под названием "ABC". Когда пользователь ищет "ABC *" (предполагая, что ваше регулярное выражение находится в этой конкретной форме), найдите элементы "ABC". Или что угодно. Это зависит от вашего сценария.