streamalism.org

1. Pregled

U ovom brzom vodiču pokazat ćemo kako radi mehanizam za podudaranje uzoraka. Također ćemo predstaviti različite načine za optimizaciju regularni izrazi na Javi.

Za uvod u upotrebu regularni izrazi, pogledajte ovaj članak ovdje.

2. Motor za podudaranje uzoraka

The java.util.regex paket koristi vrstu mehanizma za podudaranje uzoraka koji se naziva a Nedeterministički konačni automat (NFA). Smatra se nedeterministički jer dok se pokušava upariti regularni izraz na zadanom nizu, svaki znak u ulazu može se provjeriti nekoliko puta u odnosu na različite dijelove regularnog izraza.

U pozadini se koristi gore spomenuti motor vraćanje unatrag. Ovaj opći algoritam pokušava iscrpiti sve mogućnosti dok ne proglasi neuspjeh. Razmotrite sljedeći primjer da biste bolje razumjeli NFA:

"tra (vel | ce | de) m"

S ulazom Niz “putovati", Motor će prvo tražiti"tra”I odmah ga pronađite.

Nakon toga pokušat će se podudarati s “vel”Počevši od četvrtog znaka. Ovo će se podudarati, pa će ići naprijed i pokušati se podudarati “m“.

To se neće podudarati, pa će se iz tog razloga vratiti na četvrti znak i tražiti "ce“. Opet, ovo se neće podudarati, pa će se opet vratiti na četvrtu poziciju i pokušati s "de“. Ni taj se niz neće podudarati, pa će se vratiti na drugi znak u ulaznom nizu i pokušati potražiti drugi "tra“.

S posljednjim neuspjehom, algoritam će vratiti neuspjeh.

S jednostavnim posljednjim primjerom, motor se nekoliko puta morao vratiti unatrag dok je pokušavao uskladiti ulaz Niz regularnom izrazu. Zbog toga, važno je smanjiti količinu vraćanja unatrag koja to čini.

3. Načini optimizacije Regularni izrazi

3.1. Izbjegavajte ponovnu kompilaciju

Regularni izrazi u Javi sastavljaju se u unutarnju strukturu podataka. Ova je kompilacija dugotrajan proces.

Svaki put kad zazovemo String.matches (String regex) metodom, navedeni se regularni izraz ponovno sastavlja:

if (input.matches (regexPattern)) {// učini nešto}

Kao što možemo vidjeti, svaki put kada se stanje procjenjuje, sastav se izraza regularnih izraza.

Da biste optimizirali, moguće je prvo sastaviti obrazac, a zatim stvoriti Podudaranje pronaći koincidencije u vrijednosti:

Uzorak uzorka = obrazac.compile (regexPattern); for (String value: values) {Matcher matcher = pattern.matcher (vrijednost); if (matcher.matches ()) {// učini nešto}}

Alternativa gornjoj optimizaciji je korištenje iste Podudaranje primjer sa svojim resetirati () metoda:

Uzorak uzorka = obrazac.compile (regexPattern); Podudaranje podudaranje = pattern.matcher (""); za (vrijednost niza: vrijednosti) {matcher.reset (vrijednost); if (matcher.matches ()) {// učini nešto}}

Zbog činjenice Podudaranje nije siguran za nit, moramo biti oprezni s upotrebom ove varijacije. To bi moglo biti opasno u scenarijima s više niti.

Da rezimiramo, u svakoj situaciji u kojoj smo sigurni da postoji samo jedan korisnik Podudaranje u bilo kojem trenutku, u redu je ponovno ga koristiti resetirati. Za ostalo je dovoljno ponovna upotreba prekompajliranog.

3.2. Rad s alternacijom

Kao što smo upravo provjerili u posljednjem odjeljku, neadekvatna upotreba izmjena može biti štetna za izvedbu. Važno je postaviti opcije za koje je vjerojatnije da će se dogoditi sprijeda kako bi se mogle brže podudarati.

Također, moramo izvući uobičajene obrasce između njih. Nije isto staviti:

(putovanje | trgovina | trag)

Od:

tra (vel | de | ce)

Ovo potonje je brže jer NFA pokušat će se podudarati “tra”I neće isprobati nijednu od alternativa ako je ne pronađe.

3.3. Hvatanje grupa

Svaki put kad zarobljavamo grupe, nailazimo na malu kaznu.

Ako ne trebamo hvatati tekst unutar grupe, trebali bismo razmotriti upotrebu grupa koje nisu zarobile. Umjesto korištenja(M)“, Koristite“(?: M)“.

4. Zaključak

U ovom kratkom članku kratko smo pregledali kako NFA djela. Zatim smo nastavili istraživati ​​kako optimizirati izvedbu naših regularnih izraza prethodno sastavljanjem naših obrazaca i ponovnom upotrebom a Podudaranje.

Na kraju smo istaknuli nekoliko razmatranja koja treba imati na umu dok radimo s alternacijama i grupama.

Kao i obično, puni izvorni kod možete pronaći na GitHubu.