Scarse prestazioni delle espressioni regolari?

Inserito da Eyal Schneider il 21 maggio 2009 Il pacchetto java.util.regex è stato aggiunto a Java nella versione 1.4. È uno strumento molto potente e bisogna diventare un maestro per usarlo correttamente. Anche quando un'espressione regolare è vera, può essere molto lenta se non scritta in modo intelligente. Continua a leggere se vuoi capire la causa dei problemi, oppure scorri fino alla fine della pagina dove troverai 10 consigli utili per migliorare le prestazioni delle espressioni regolari in Java.

È davvero così lento?

Diciamo di voler selezionare solo le righe contenenti la sequenza di caratteri "a" e "b". La soluzione corretta potrebbe essere: (a*b*)* Tuttavia, se esegui l'espressione con, ad esempio, la stringa "aaaaaaaaaaaaaaaaaaaaaaaaaaaaax" , ci vorranno diversi minuti prima che finisca e non riporti corrispondenze! Naturalmente, la migliore espressione regolare in questo caso sarebbe: (a|b)* Questo richiede meno di un millisecondo sulla mia macchina con la stessa stringa. Chiaramente c'è un problema di prestazioni qui.

Perché sta succedendo?

Come la maggior parte dei motori regexp, Java utilizza un approccio NFA (Non-Deterministic Finite Automata). Il motore esegue la scansione dei componenti regex uno per uno e avanza di conseguenza attraverso la stringa di input. E può tornare all’inizio per trovare alternative adeguate se raggiunge un “vicolo cieco”. Risultati alternativi si ottengono utilizzando strutture regolari come quantificatori ( *, +, ? ) e alternanze (ad esempio a|b|c|d ). Questa tecnica di ricerca è chiamata backtracking. Nel terribile esempio riportato sopra, il motore esaminerà effettivamente TUTTE le scomposizioni in serie del simbolo "a" in serie più piccole finché non si renderà conto che non ci sono corrispondenze. Questo esempio mostra come l'algoritmo di backtracking può produrre una stima temporale esponenziale (a seconda della lunghezza della stringa di input). Ciò mostra anche un'importante proprietà dell'NFA: ci saranno sempre casi peggiori che quasi corrispondono al modello. Se viene trovata una corrispondenza, la ricerca si interrompe. L'altro approccio principale da utilizzare nelle espressioni regolari è DFA (Deterministic Finite Automaton). In questo approccio, l'espressione regolare costruisce effettivamente un automa utilizzato per attraversare le stringhe di input carattere per carattere senza tornare indietro. Ciò fornisce tempo lineare all'intero input, indipendentemente dalla complessità dell'espressione regolare. Invece di scansionare in sequenza una stringa per trovare corrispondenze (come in NFA), DFA simula la scansione parallela. Allora perché Java (e .NET, Perl, Python, Ruby, PHP, ecc.) utilizzano NKA e non DKA che ha un comportamento molto migliore? Il motivo è che NKA presenta una serie di vantaggi significativi:

Si compila più velocemente e richiede molta meno memoria
Consente alcune funzionalità utili (vedere il tutorial di Sun per i dettagli ):

Acquisizione di gruppi e backlink
Controllo posizionale
Quantificatori estesi (Greedy e Lazy)

È importante notare che i termini popolari NKA e DKA sono imprecisi se utilizzati nel contesto delle espressioni regolari. In teoria, questi due modelli hanno la stessa potenza di calcolo. Ciò significa che non è possibile scrivere in un modello di automi un'espressione regolare che sarebbe impossibile esprimere in un altro. In pratica, sono necessarie più capacità in modo che i due tipi di implementazione divergano nella semantica. I motori NKA offrono maggiore flessibilità rendendoli superiori a DKA in termini di potenza di calcolo. A causa della velocità di DFA e delle caratteristiche uniche di NFA, esistono altri due modi “prefabbricati” per implementare le espressioni regolari. Alcune implementazioni utilizzano entrambi i tipi (ad esempio GNU egrep, che seleziona un motore specifico in fase di esecuzione), e alcune sono riuscite a implementare una versione veramente ibrida (ad esempio regexps Tcl) con tutti i vantaggi.

Consiglio

Di seguito sono riportati alcuni suggerimenti su come evitare problemi di efficienza delle espressioni regolari in Java. Molti di loro mirano a ridurre i rendimenti.

1) Precompilazione

Banale, ma degno di nota. Se usi l'espressione regolare più di una volta, assicurati di compilarla in anticipo:

// компиляция p = Pattern.compile(regex, flags); … // использование Matcher a = p.matcher(input);

2) Quantificatori pigri e quantificatori avidi

Per impostazione predefinita, i quantificatori ( * + ? ) sono avidi. Ciò significa che iniziano ad abbinarsi con la sequenza più lunga possibile e poi tornano gradualmente indietro se necessario. Se sai in anticipo che le corrispondenze saranno generalmente brevi, dovresti utilizzare quantificatori pigri. Iniziano con la corrispondenza più piccola e si spostano ulteriormente se necessario. Diciamo che vogliamo trovare solo le righe che corrispondono alla sequenza "ciao". Il normale .*hello.* farà tutto bene, ma se sappiamo che "ciao" di solito appare più vicino all'inizio del testo, allora .*?hello.* funzionerà in media più velocemente.

3) Utilizzare quantificatori super-avidi ove possibile

A differenza dei quantificatori pigri, che influenzano le prestazioni ma non influenzano il comportamento regolare, i quantificatori super-avidi possono effettivamente cambiare il significato di un'espressione regolare. Quando viene utilizzato *+ al posto di * , la prima corrispondenza sarà greedy (ovvero, la più grande possibile come se fosse solo *), ma non ci sarà alcun fallback se fallisce, anche se ciò causa il fallimento dell'intera ricerca. Quando potrebbe essere utile? Diciamo che dobbiamo trovare il testo tra virgolette. Il normale \"[^\"]*\" funzionerà bene. Tuttavia, creerà un rientro non necessario nei casi negativi (ad esempio, "bla bla bla). L'uso di \"[^\"]*+\" eliminerà rollback senza cambiare il significato dell'espressione. Il raggruppamento indipendente ottiene lo stesso effetto e offre un controllo ancora maggiore (vedi tutorial di Sun ).

4) Evitare la cattura di gruppo

Qualsiasi espressione tra parentesi è considerata un gruppo per impostazione predefinita. Ciò ha un piccolo impatto sulle prestazioni. Rendi i tuoi gruppi "non catturabili" quando possibile iniziandoli con (?: invece di ( .

5) Usa saggiamente l'interlacciamento

Quando viene utilizzato l'interleaving (ad esempio Paul|Jane|Chris ), l'ordine in cui il motore tenta di far corrispondere le opzioni è lo stesso dell'ordine in cui appaiono. Puoi sfruttare questa funzionalità e posizionare le opzioni più comuni più vicino all'inizio. Ciò migliorerà il tempo medio di risposta positiva.

6) Evitare ambiguità

Scrivi le espressioni regolari in modo tale da ridurre al minimo il numero di corrispondenze diverse nella stringa di input. Ad esempio: l'espressione regolare (a*b*)* riportata all'inizio dell'articolo permette di interpretare la stringa "aabb" in troppi modi: (a2b2) (a1)(a1)(b1)(b1) (a2)(b2) (a1)(a1b2) etc… Regexp (a|b)*, invece, interpreta solo combinazioni in modo positivo. Questo è molto importante per ridurre i rendimenti nei casi di quasi corrispondenza.

7) Anteprima

L'anteprima consente di aggiungere restrizioni alle sequenze a sinistra/destra della posizione corrente. In particolare, con un lookahead negativo, si possono cercare righe che non contengono qualche sequenza (cosa faremmo senza di questa!). Come può questo contribuire ad aumentare la produttività? Diciamo che vogliamo prendere l'URL dal tag link. Considera la seguente espressione regolare: a .* href=(\S*).*/ Per i tag regolari, questa espressione corrisponderà all'indirizzo solo se il testo contiene l'attributo "href" (\S viene utilizzato per tutti i caratteri tranne i delimitatori). Ma su alcuni tag insoliti, ad esempio, si verificherà un rollback. Ad esempio: “a href= href=href=…. href=qualcosa." La seguente espressione regolare impedirà che ciò accada quando si sostituisce ".*" in un'espressione con qualcosa che non corrisponde a "href": a ((?!href).)* href=(\S*)((?!href).)*/

8) Specificare la lunghezza

Java contiene un ottimizzatore regexp che controlla la lunghezza della stringa di input rispetto alla lunghezza minima e massima ottenuta dall'espressione regolare. Ciò consente in alcuni casi di interrompere immediatamente la ricerca. Per facilitare questo meccanismo, il numero di ripetizioni dovrebbe essere specificato quando possibile (ad esempio, [01]{6} corrisponde a tutte le stringhe binarie lunghe sei caratteri).

9) Seleziona linee identiche

A volte stringhe uguali sono nascoste all'interno di gruppi o alternative: (hello|hell|heel) questa espressione può essere semplificata in: he(llo|ll|el) In questo modo diamo all'ottimizzatore regexp maggiori informazioni.

10) Metti alla prova la tua espressione regolare

Potrebbe essere saggio testare prima l'espressione regolare quando verrà utilizzata in un'applicazione critica per le prestazioni. Scrivi un micro-benchmark che metta alla prova la tua espressione su vari dati di input. Assicurati di testare dati di diversa lunghezza e anche dati che corrispondono strettamente al tuo campione.

Collegamenti:

http://java.sun.com/docs/books/tutorial/essential/regex/index.html http://www.javaworld.com/javaworld/jw-09-2007/jw-09-optimizingregex.html?page =1 http://www.softec.st/en/OpenSource/DevelopersCorner/RegularExpressions/RegularExpressionEngines.html http://www.devarticles.com/c/a/Java/NFA-DFA-POSIX-and-the-Mechanics -Elaborazione-dell'espressione/