Prehľad výkonu regulárnych výrazov v jazyku Java
1. Prehľad
V tomto rýchlom výučbe si ukážeme, ako funguje modul na porovnávanie vzorov. Predstavíme tiež rôzne spôsoby optimalizácie regulárne výrazy v Jave.
Pre úvod do používania regulárne výrazy, pozrite si prosím tento článok tu.
2. Engine-Matching Engine
The java.util.regex balík používa typ nástroja na porovnávanie vzorov s názvom a Nedeterministický konečný automat (NFA). Zvažuje sa to nedeterministické pretože pri pokuse o zhodu regulárneho výrazu s daným reťazcom môže byť každý znak vo vstupe niekoľkokrát skontrolovaný oproti rôznym častiam regulárneho výrazu.
Na pozadí využíva motor uvedený vyššie spätné sledovanie. Tento všeobecný algoritmus sa snaží vyčerpať všetky možnosti, kým nevyhlási zlyhanie. Zvážte nasledujúci príklad, aby ste lepšie pochopili NFA:
„tra (vel | ce | de) m“So vstupom String “cestovanie„, Motor bude najskôr hľadať“tra”A okamžite to nájdite.
Potom sa to pokúsi priradiť “vel”Počnúc štvrtým znakom. Toto sa bude zhodovať, takže to pôjde vpred a pokúsi sa to zhodovať “m“.
To sa nebude zhodovať, a preto sa vráti k štvrtému znaku a vyhľadá výraz „ce„. Opäť sa to nebude zhodovať, takže sa vrátite späť na štvrtú pozíciu a vyskúšajte „de„. Ani tento reťazec sa nezhoduje, a tak sa vráti späť na druhý znak vo vstupnom reťazci a pokúsi sa vyhľadať ďalší “tra“.
Pri poslednom zlyhaní algoritmus vráti zlyhanie.
S jednoduchým posledným príkladom musel motor niekoľkokrát cúvať, kým sa snažil zhodovať so vstupom String k regulárnemu výrazu. Z dôvodu, že, je dôležité minimalizovať mieru spätného sledovania, ktoré robí.
3. Spôsoby optimalizácie Regulárne výrazy
3.1. Zabráňte prekompilovaniu
Regulárne výrazy v Jave sú kompilované do internej dátovej štruktúry. Táto kompilácia je časovo náročný proces.
Zakaždým, keď vyvoláme String.matches (String regex) metóda, zadaný regulárny výraz sa prekompiluje:
if (input.matches (regexPattern)) {// niečo urobiť}Ako vidíme, zakaždým, keď sa vyhodnotí podmienka, zostaví sa výraz regulárneho výrazu.
Pre optimalizáciu je možné najskôr zostaviť vzor a až potom vytvoriť a Matcher nájsť zhody v hodnote:
Pattern pattern = Pattern.compile (regexPattern); pre (Reťazcová hodnota: hodnoty) {Matcher matcher = pattern.matcher (value); if (matcher.matches ()) {// urob niečo}}Alternatívou k vyššie uvedenej optimalizácii je rovnaké použitie Matcher napríklad s jeho reset () metóda:
Pattern pattern = Pattern.compile (regexPattern); Matcher matcher = pattern.matcher (""); pre (Reťazcová hodnota: hodnoty) {matcher.reset (hodnota); if (matcher.matches ()) {// urob niečo}}Vzhľadom na skutočnosť Matcher nie je bezpečný pre vlákna, musíme byť pri používaní tejto variácie opatrní. V scenároch s viacerými vláknami by to mohlo byť pravdepodobne nebezpečné.
Ak to zhrnieme, v každej situácii, keď sme si istí, že používateľ je iba jeden Matcher kedykoľvek je v poriadku ich opätovné použitie resetovať. Na zvyšok stačí opätovné použitie predkompilovanej verzie.
3.2. Práca s alternáciou
Ako sme práve skontrolovali v poslednej časti, nedostatočné použitie alternácií by mohlo byť pre výkon škodlivé. Je dôležité umiestniť možnosti, ktoré sa pravdepodobnejšie vyskytnú vpredu, aby sa dali rýchlejšie porovnávať.
Musíme tiež extrahovať spoločné vzorce medzi nimi. Nie je to to isté, čo:
(cestovanie | obchod | stopa)Než:
tra (vel | de | ce)Druhá je rýchlejšia, pretože NFA pokúsi sa zhodovať “tra”A nevyskúša žiadnu z alternatív, ak ju nenájde.
3.3. Zachytávanie skupín
Zakaždým, keď chytíme skupiny, hrozí nám malý trest.
Ak nepotrebujeme zachytiť text vo vnútri skupiny, mali by sme zvážiť použitie skupín, ktoré nezachytávajú. Namiesto použitia „(M)", prosím použite "(?: M)“.
4. Záver
V tomto rýchlom článku sme sa v krátkosti zmienili o tom, ako NFA Tvorba. Potom sme pokračovali v preskúmaní, ako optimalizovať výkonnosť našich regulárnych výrazov predbežnou kompiláciou našich vzorov a opätovným použitím a Matcher.
Na záver sme poukázali na niekoľko úvah, na ktoré treba pamätať pri práci s alternáciami a skupinami.
Celý zdrojový kód nájdete ako obvykle na GitHub.
