Panoramica delle prestazioni delle espressioni regolari in Java

1. Panoramica

In questo breve tutorial, mostreremo come funziona il motore di corrispondenza dei modelli. Presenteremo anche diversi modi per ottimizzare le espressioni regolari in Java.

Per un'introduzione all'uso delle espressioni regolari , fare riferimento a questo articolo qui.

2. Il motore di corrispondenza dei modelli

Il pacchetto java.util.regex utilizza un tipo di motore di corrispondenza dei modelli chiamato Automa finito non deterministico (NFA). È considerato non deterministico perché durante il tentativo di trovare una corrispondenza con un'espressione regolare su una determinata stringa, ogni carattere nell'input potrebbe essere verificato più volte rispetto a parti diverse dell'espressione regolare.

In background, il motore sopra menzionato utilizza il backtracking . Questo algoritmo generale cerca di esaurire tutte le possibilità fino a quando non dichiara fallimento. Considera il seguente esempio per comprendere meglio l' NFA :

"tra(vel|ce|de)m"

Con la stringa di input " travel ", il motore prima cercherà " tra " e lo troverà immediatamente.

Dopodiché, proverà a far corrispondere " vel " a partire dal quarto carattere. Questo corrisponderà, quindi andrà avanti e cercherà di abbinare " m ".

Questo non corrisponderà, e per questo motivo, tornerà al quarto carattere e cercherà " ce ". Anche in questo caso, questo non corrisponderà, quindi tornerà in quarta posizione e proverà con " de ". Anche quella stringa non corrisponderà, quindi tornerà al secondo carattere nella stringa di input e proverà a cercare un altro " tra ".

Con l'ultimo errore, l'algoritmo restituirà l'errore.

Con il semplice ultimo esempio, il motore ha dovuto tornare indietro più volte durante il tentativo di abbinare la stringa di input all'espressione regolare. Per questo motivo, è importante ridurre al minimo la quantità di backtracking che esegue.

3. Modi per ottimizzare le espressioni regolari

3.1. Evita la ricompilazione

Le espressioni regolari in Java vengono compilate in una struttura dati interna. Questa compilazione è il processo che richiede tempo.

Ogni volta che invochiamo il metodo String.matches (String regex) , l'espressione regolare specificata viene ricompilata:

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

Come possiamo vedere, ogni volta che la condizione viene valutata, l'espressione regex viene compilata.

Per ottimizzare, è possibile compilare prima il pattern e poi creare un Matcher per trovare le coincidenze nel valore:

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

Un'alternativa all'ottimizzazione di cui sopra sta usando la stessa istanza Matcher con il suo metodo reset () :

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

Dato che Matcher non è thread-safe, dobbiamo essere cauti con l'uso di questa variazione. Potrebbe essere probabilmente pericoloso in scenari multi-thread.

Riassumendo, in ogni situazione in cui siamo sicuri che ci sia un solo utente di Matcher in qualsiasi momento, va bene riutilizzarlo con reset . Per il resto è sufficiente riutilizzare il precompilato.

3.2. Lavorare con l'alternanza

Come abbiamo appena verificato nell'ultima sezione, l'uso inadeguato delle alternanze potrebbe essere dannoso per le prestazioni. È importante posizionare le opzioni che hanno maggiori probabilità di verificarsi in primo piano in modo che possano essere abbinate più velocemente.

Inoltre, dobbiamo estrarre modelli comuni tra di loro. Non è la stessa cosa mettere:

(travel | trade | trace)

Di:

tra(vel | de | ce)

Quest'ultimo è più veloce perché l' NFA cercherà di abbinare " tra " e non proverà nessuna delle alternative se non lo trova.

3.3. Acquisizione di gruppi

Ogni volta che catturiamo gruppi, incorriamo in una piccola penalità.

Se non abbiamo bisogno di catturare il testo all'interno di un gruppo, dovremmo considerare l'uso di gruppi non di cattura. Invece di utilizzare " (M) ", utilizzare " (?: M) ".

4. Conclusione

In questo breve articolo, abbiamo rivisitato brevemente come funziona NFA . Abbiamo quindi proceduto a esplorare come ottimizzare le prestazioni delle nostre espressioni regolari precompilando i nostri modelli e riutilizzando un Matcher .

Infine, abbiamo evidenziato un paio di considerazioni da tenere a mente mentre lavoriamo con alternanze e gruppi.

Come al solito, il codice sorgente completo può essere trovato su GitHub.