Преглед на ефективността на регулярните изрази в Java

1. Общ преглед

В този бърз урок ще покажем как работи механизмът за съвпадение на шаблоните. Ще представим и различни начини за оптимизиране на регулярни изрази в Java.

За въведение в използването на регулярни изрази , моля, вижте тази статия тук.

2. Двигателят за съвпадение на шаблоните

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

Във фонов режим двигателят, споменат по-горе, използва обратното проследяване . Този общ алгоритъм се опитва да изчерпи всички възможности, докато не обяви провал. Помислете за следния пример, за да разберете по-добре NFA :

"tra(vel|ce|de)m"

С входния низпътуване “ двигателят първо ще потърси „ tra “ и ще го намери веднага.

След това ще се опита да съответства на „ vel “, започвайки от четвъртия символ. Това ще съвпадне, така че ще продължи напред и ще се опита да съответства на „ m “.

Това няма да съвпадне и поради тази причина ще се върне към четвъртия знак и ще търси „ ce “. Отново това няма да съвпадне, така че ще се върне отново на четвъртата позиция и ще опита с „ de “. Този низ също няма да съвпада и така ще се върне към втория знак във входния низ и ще се опита да търси друго „ tra “.

С последния отказ алгоритъмът ще върне отказ.

С последния прост пример, двигателят трябваше да се върне няколко пъти, докато се опитваше да съпостави входния String с регулярния израз. Поради това е важно да се сведе до минимум количеството проследяване, което прави.

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 , е добре да го използвате повторно с нулиране . За останалото е достатъчно повторното използване на предварително компилираното.

3.2. Работа с редуване

Както току-що проверихме в последния раздел, неадекватното използване на редувания може да навреди на производителността. Важно е да поставите опции, които е по-вероятно да се случат отпред, за да могат да се съчетаят по-бързо.

Също така трябва да извлечем общи модели между тях. Не е същото да се постави:

(travel | trade | trace)

От:

tra(vel | de | ce)

Последното е по-бързо, защото NFA ще се опита да съвпадне с „ tra “ и няма да опита нито една от алтернативите, ако не го намери.

3.3. Улавяне на групи

Всеки път, когато залавяме групи, ние нанасяме наказание за малко време.

Ако не е необходимо да заснемаме текста в група, трябва да помислим за използването на групи, които не улавят. Вместо да използвате „ (M) “, моля, използвайте „ (?: M) “.

4. Заключение

В тази кратка статия прегледахме накратко как работи NFA . След това продължихме да проучваме как да оптимизираме работата на нашите регулярни изрази чрез предварително съставяне на нашите модели и повторно използване на съвпадение .

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

Както обикновено, пълният изходен код може да бъде намерен в GitHub.