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

1. Обзор

В этом кратком руководстве мы покажем, как работает механизм сопоставления с образцом. Мы также представим различные способы оптимизации регулярных выражений в Java.

Для ознакомления с использованием регулярных выражений обратитесь к этой статье здесь .

2. Механизм сопоставления с образцом

Пакет java.util.regex использует механизм сопоставления с образцом, называемый недетерминированным конечным автоматом (NFA). Он считается недетерминированным , поскольку при попытке сопоставить регулярное выражение с заданной строкой каждый символ во входных данных может несколько раз сверяться с разными частями регулярного выражения.

В фоновом режиме упомянутый выше движок использует возврат . Этот общий алгоритм пытается исчерпать все возможности, пока не объявит об отказе. Рассмотрим следующий пример, чтобы лучше понять NFA :

"tra(vel|ce|de)m"

При вводе строки « путешествие » движок сначала будет искать « тра » и сразу же найдет его.

После этого он попытается сопоставить « vel », начиная с четвертого символа. Это совпадет, поэтому он пойдет вперед и попытается сопоставить « m ».

Это не совпадет, и по этой причине он вернется к четвертому символу и будет искать « ce ». Опять же, это не совпадет, поэтому он снова вернется на четвертую позицию и попытается с « де ». Эта строка также не будет совпадать, поэтому она вернется ко второму символу входной строки и попытается найти другой « tra ».

При последней ошибке алгоритм вернет ошибку.

В последнем простом примере движку пришлось несколько раз вернуться назад, пытаясь сопоставить входную строку с регулярным выражением. Из-за этого важно свести к минимуму количество возвратов, которые он делает.

3. Способы оптимизации регулярных выражений

3.1. Избегайте перекомпиляции

Регулярные выражения в Java компилируются во внутреннюю структуру данных. Эта компиляция является трудоемким процессом.

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

if (input.matches(regexPattern)) {
    // do something
}

Как мы видим, каждый раз, когда оценивается условие, компилируется регулярное выражение.

Для оптимизации можно сначала скомпилировать шаблон, а затем создать Matcher для поиска совпадений в значении:

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

Альтернативой приведенной выше оптимизации является использование того же экземпляра Matcher с его методом reset() :

Pattern pattern = Pattern.compile(regexPattern);
Matcher matcher = pattern.matcher("");
for(String value : values) {
    matcher.reset(value);
    if (matcher.matches()) {
      // do something
    }
}

Из-за того, что Matcher не является потокобезопасным, мы должны быть осторожны с использованием этого варианта. Вероятно, это может быть опасно в многопоточных сценариях.

Подводя итог, в каждой ситуации, когда мы уверены, что в любой момент времени есть только один пользователь Matcher , можно повторно использовать его с помощью reset . В остальном повторного использования предварительно скомпилированного достаточно.

3.2. Работа с чередованием

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

Кроме того, мы должны извлечь общие закономерности между ними. Это не то же самое, что поставить:

(travel | trade | trace)

Чем:

tra(vel | de | ce)

Последний быстрее, потому что NFA попытается сопоставить « tra » и не будет пробовать ни одну из альтернатив, если не найдет ее.

3.3. Захват групп

Каждый раз, когда мы захватываем группы, мы подвергаемся небольшому штрафу.

Если нам не нужно захватывать текст внутри группы, мы должны рассмотреть возможность использования групп без захвата. Вместо « (M) » используйте « (?:M) ».

4. Вывод

В этой быстрой статье мы кратко рассмотрели, как работает NFA . Затем мы приступили к изучению того, как оптимизировать производительность наших регулярных выражений путем предварительной компиляции наших шаблонов и повторного использования Matcher .

Наконец, мы указали на пару соображений, о которых следует помнить, когда мы работаем с чередованиями и группами.

Как обычно, полный исходный код можно найти на GitHub .