En oversikt over ytelsen til regulære uttrykk i Java
1. Oversikt
I denne raske opplæringen viser vi hvordan motoren for mønstermatching fungerer. Vi presenterer også forskjellige måter å optimalisere på vanlig uttrykk i Java.
For en introduksjon til bruken av vanlig uttrykk, se denne artikkelen her.
2. Den mønstermatchende motoren
De java.util.regex pakken bruker en type mønster-matching motor kalt a Ikke-bestemt finitt automatisk (NFA). Det vurderes ikke-bestemt fordi mens du prøver å matche et vanlig uttrykk på en gitt streng, kan hvert tegn i inngangen sjekkes flere ganger mot forskjellige deler av det vanlige uttrykket.
I bakgrunnen bruker motoren nevnt ovenfor backtracking. Denne generelle algoritmen prøver å utnytte alle muligheter til den erklærer feil. Tenk på følgende eksempel for å bedre forstå NFA:
"tra (vel | ce | de) m"Med innspill String “reise“, Vil motoren først se etter“tra”Og finn det umiddelbart.
Etter det vil den prøve å matche “vel”Starter fra det fjerde tegnet. Dette vil matche, så det vil gå fremover og prøve å matche “m“.
Det samsvarer ikke, og av den grunn vil det gå tilbake til det fjerde tegnet og søke etter “ce“. Igjen, dette vil ikke matche, så det vil gå tilbake til fjerde posisjon og prøve med “de“. Den strengen vil heller ikke matche, og så vil den gå tilbake til det andre tegnet i inngangsstrengen og prøve å søke etter en annen “tra“.
Med den siste feilen vil algoritmen returnere feil.
Med det enkle siste eksemplet måtte motoren spore flere ganger mens han prøvde å matche inngangen String til det vanlige uttrykket. På grunn av det, det er viktig å minimere mengden tilbakesporing som den gjør.
3. Måter å optimalisere på Vanlig uttrykk
3.1. Unngå rekompilering
Regulære uttrykk i Java er samlet i en intern datastruktur. Denne samlingen er den tidkrevende prosessen.
Hver gang vi påkaller String.matches (String regex) Metoden blir det spesifiserte regulære uttrykket kompilert på nytt:
hvis (input.matches (regexPattern)) {// gjør noe}Som vi kan se, blir regex-uttrykket samlet hver gang tilstanden blir evaluert.
For å optimalisere er det mulig å kompilere mønsteret først og deretter lage et Matcher for å finne tilfeldighetene i verdien:
Mønster mønster = Mønster.kompilere (regexPattern); for (Strengverdi: verdier) {Matcher matcher = pattern.matcher (verdi); hvis (matcher.matches ()) {// gjør noe}}Et alternativ til ovennevnte optimalisering er å bruke det samme Matcher eksempel med sin nullstille() metode:
Mønster mønster = Mønster.kompilere (regexPattern); Matcher matcher = mønster.matcher (""); for (Strengverdi: verdier) {matcher.reset (verdi); hvis (matcher.matches ()) {// gjør noe}}På grunn av det faktum at Matcher ikke er trådsikker, må vi være forsiktige med bruken av denne varianten. Det kan være sannsynlig farlig i flertrådede scenarier.
For å oppsummere, i alle situasjoner der vi er sikre på at det bare er en bruker av Matcher når som helst, er det OK å bruke den på nytt nullstille. For resten er det nok å bruke det forhåndskompilerte.
3.2. Arbeide med alternativ
Som vi nettopp sjekket i forrige avsnitt, kan utilstrekkelig bruk av alternasjoner være skadelig for ytelsen. Det er viktig å plassere alternativer som er mer sannsynlig å skje foran, slik at de kan matches raskere.
Vi må også trekke ut vanlige mønstre mellom dem. Det er ikke det samme å si:
(reise | handel | spor)Enn:
tra (vel | de | ce)Sistnevnte er raskere fordi NFA vil prøve å matche “tra”Og vil ikke prøve noen av alternativene hvis den ikke finner den.
3.3. Fange grupper
Hver gang vi tar grupper, pådrar vi oss en liten straff.
Hvis vi ikke trenger å fange teksten i en gruppe, bør vi vurdere bruk av ikke-fangende grupper. I stedet for å bruke “(M)", Vennligst bruk "(?: M)“.
4. Konklusjon
I denne raske artikkelen tok vi en kort titt på hvordan NFA virker. Vi fortsatte deretter med å utforske hvordan vi kan optimalisere ytelsen til våre vanlige uttrykk ved å forhåndskompilere mønstrene våre og gjenbruke a Matcher.
Til slutt påpekte vi et par hensyn å huske på mens vi jobber med vekslinger og grupper.
Som vanlig finner du full kildekode på GitHub.
