Mahina ang pagganap ng mga regular na expression?

Nai-post ni Eyal Schneider noong Mayo 21, 2009 Ang java.util.regex package ay idinagdag sa Java sa bersyon 1.4. Ito ay isang napakalakas na tool at ang isa ay kailangang maging isang master upang magamit ito ng tama. Kahit na totoo ang isang regular na expression , maaari itong maging napakabagal kung hindi isinulat nang matalino. Magpatuloy sa pagbabasa kung gusto mong maunawaan ang sanhi ng mga problema, o mag-scroll sa dulo ng pahina kung saan makakahanap ka ng 10 kapaki-pakinabang na tip para sa pagpapabuti ng pagganap ng mga regular na expression sa Java.

Ganun ba talaga kabagal?

Sabihin nating gusto nating pumili lamang ng mga linya na naglalaman ng pagkakasunod-sunod ng mga character na "a" at "b". Ang tamang solusyon ay maaaring: (a*b*)* Gayunpaman, kung patakbuhin mo ang expression na may, halimbawa, ang string na “aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaax” , aabutin ng ilang minuto bago ito matapos at mag-ulat ng walang tugma! Siyempre, ang pinakamahusay na regex sa kasong ito ay: (a|b)* Ito ay tumatagal ng mas mababa sa isang millisecond sa aking makina na may parehong string. Malinaw na mayroong isyu sa pagganap dito.

Bakit ito nangyayari?

Tulad ng karamihan sa mga regexp engine, ang Java ay gumagamit ng NFA (Non-Deterministic Finite Automata) na diskarte. Ini-scan ng makina ang mga bahagi ng regex nang paisa-isa at sumusulong sa input string nang naaayon. At maaari siyang bumalik sa simula upang makahanap ng mga naaangkop na alternatibo kung umabot siya sa isang "dead end". Ang mga alternatibong resulta ay nakukuha sa pamamagitan ng paggamit ng mga regular na istruktura tulad ng mga quantifier ( *, +, ? ) at mga alternatibo (hal. a|b|c|d ). Ang pamamaraan ng pananaliksik na ito ay tinatawag na backtracking. Sa kakila-kilabot na halimbawa sa itaas, ang makina ay talagang titingnan ang LAHAT ng serye ng mga decomposition ng simbolo na "a" sa mas maliit na serye hanggang sa mapagtanto nitong walang mga tugma. Ipinapakita ng halimbawang ito kung paano maaaring magresulta ang backtracking algorithm sa isang exponential time estimate (depende sa haba ng input string). Nagpapakita rin ito ng mahalagang katangian ng NFA: palaging magkakaroon ng pinakamasamang kaso na halos tumutugma sa pattern. Kung may nakitang tugma, hihinto ang paghahanap. Ang iba pang pangunahing diskarte para sa paggamit sa regex ay ang DFA (Deterministic Finite Automaton). Sa diskarteng ito, ang regular na expression ay talagang bumubuo ng isang automat na ginagamit upang i-traverse ang input string ng character ayon sa character nang walang backtracking. Nagbibigay ito ng linear na oras sa buong input, anuman ang pagiging kumplikado ng regular na expression. Sa halip na sunud-sunod na i-scan ang isang string para sa mga tugma (tulad ng sa NFA), ginagaya ng DFA ang parallel scanning. Kaya bakit ginagamit ng Java (at .NET, Perl, Python, Ruby, PHP, atbp.) ang NKA at hindi ang DKA na may mas mahusay na pag-uugali? Ang dahilan ay ang NKA ay may isang bilang ng mga makabuluhang pakinabang:

Nag-compile nang mas mabilis at nangangailangan ng mas kaunting memorya
Nagbibigay-daan sa ilang kapaki-pakinabang na feature (tingnan ang tutorial ng Sun para sa mga detalye ):

Group Capture at Mga Backlink
Positional check
Mga Extended Quantifiers (Sakim at Tamad)

Mahalagang tandaan na ang mga sikat na terminong NKA at DKA ay hindi tumpak kapag ginamit sa konteksto ng mga regular na expression. Sa teorya, ang dalawang modelong ito ay may parehong kapangyarihan sa pag-compute. Nangangahulugan ito na hindi ka makakasulat ng isang regular na expression sa isang modelo ng automata na imposibleng ipahayag sa isa pa. Sa pagsasagawa, may pangangailangan para sa higit pang mga kakayahan upang ang dalawang uri ng pagpapatupad ay magkaiba sa semantika. Ang mga NKA engine ay nagbibigay ng higit na kakayahang umangkop na ginagawang mas mataas ang mga ito kaysa sa DKA sa kapangyarihan ng pag-compute. Dahil sa bilis ng DFA at sa mga natatanging tampok ng NFA, may 2 pang "prefabricated" na paraan para ipatupad ang mga regular na expression. Ang ilang mga pagpapatupad ay gumagamit ng parehong uri (hal. GNU egrep, na pumipili ng isang partikular na engine sa runtime), at ang ilan ay nakapagpatupad ng isang tunay na hybrid na bersyon (hal. Tcl regexps) kasama ang lahat ng mga benepisyo.

Payo

Ang mga sumusunod ay ilang mga tip kung paano maiwasan ang mga problema sa kahusayan ng regex sa Java. Marami sa kanila ay naglalayong bawasan ang kita.

1) Pre-compilation

Trite, ngunit nagkakahalaga ng pagbanggit. Kung gagamitin mo ang regexp nang higit sa isang beses, siguraduhing i-compile ito nang maaga:

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

2) Lazy Quantifiers vs. Greedy Quantifiers

Bilang default, ang mga quantifier ( * + ? ) ay matakaw. Nangangahulugan ito na nagsisimula silang tumugma sa pinakamahabang posibleng pagkakasunud-sunod at pagkatapos ay unti-unting bumalik kung kinakailangan. Kung alam mo nang maaga na ang mga tugma ay karaniwang maikli, dapat kang gumamit ng mga tamad na quantifier. Nagsisimula sila sa pinakamaliit na tugma at lumipat pa kung kinakailangan. Sabihin nating gusto lang nating hanapin ang mga linyang tumutugma sa sequence na "hello". Gagawin ng regular na .*hello.* ang lahat nang tama, ngunit kung alam natin na ang "hello" ay karaniwang lumalabas na mas malapit sa simula ng text, kung gayon ang .*?hello.* ay gagana nang mas mabilis sa karaniwan.

3) Gumamit ng mga super-matakaw na quantifier kung posible

Hindi tulad ng mga tamad na quantifier, na nakakaapekto sa pagganap ngunit hindi nakakaapekto sa regular na pag-uugali, ang mga super-matakaw na quantifier ay maaaring aktwal na baguhin ang kahulugan ng isang regular na expression. Kapag *+ ang ginamit sa halip na * , ang unang tugma ay magiging gahaman (iyon ay, ang pinakamalaking posible na parang * lang), ngunit walang magiging fallback kung ito ay nabigo, kahit na ito ay nagiging sanhi ng pagkabigo sa buong paghahanap. Kailan ito maaaring maging kapaki-pakinabang? Sabihin nating kailangan nating maghanap ng teksto sa mga quote. Ang regular na \"[^\"]*\" ay gagana nang maayos. Gayunpaman, gagawa ito ng hindi kinakailangang indentasyon sa mga negatibong kaso (halimbawa, "bla bla bla). Ang paggamit ng \"[^\"]*+\" ay mag-aalis rollback nang hindi binabago ang kahulugan ng expression. Nakakamit ng independiyenteng pagpapangkat ang parehong epekto at nagbibigay ng higit pang kontrol (tingnan ang tutorial ng Sun ).

4) Iwasan ang pagkuha ng grupo

Ang anumang expression sa panaklong ay itinuturing na isang pangkat bilang default. Ito ay may maliit na epekto sa pagganap. Gawing "uncapturable" ang iyong mga grupo hangga't maaari sa pamamagitan ng pagsisimula sa kanila sa (?: sa halip na ( .

5) Gamitin ang interleaving nang matalino

Kapag ginamit ang interleaving (hal. Paul|Jane|Chris ), ang pagkakasunud-sunod kung saan sinusubukan ng makina na tumugma sa mga opsyon ay pareho sa pagkakasunud-sunod kung saan lumilitaw ang mga ito. Maaari mong samantalahin ang tampok na ito at ilagay ang pinakakaraniwang mga opsyon na mas malapit sa simula. Mapapabuti nito ang average na positibong oras ng pagtugon.

6) Iwasan ang kalabuan

Sumulat ng regexps sa paraang mabawasan ang bilang ng iba't ibang tugma sa input string. Halimbawa: ang regular na expression (a*b*)* na ibinigay sa simula ng artikulo ay nagbibigay-daan sa string na "aabb" na bigyang-kahulugan sa napakaraming paraan: (a2b2) (a1)(a1)(b1)(b1) (a2)(b2) (a1)(a1b2) etc… Regexp (a|b)*, sa kabilang banda, ay nagpapakahulugan lamang ng kakaiba positibong kumbinasyon. Napakahalaga nito upang mabawasan ang mga pagbabalik sa mga kaso ng malapit- tugma.

7) Silipin

Preview ay nagbibigay-daan sa iyo upang magdagdag ng mga paghihigpit sa mga sequence sa kaliwa/kanan ng kasalukuyang posisyon. Sa partikular, na may negatibong pagtingin, maaari kang maghanap ng mga linya na hindi naglalaman ng ilang pagkakasunud-sunod (ano ang gagawin natin kung wala ito!). Paano ito makatutulong sa pagtaas ng produktibidad? Sabihin nating gusto naming kunin ang URL mula sa tag ng link. Isaalang-alang ang sumusunod na regexp: a .* href=(\S*).*/ Para sa mga regular na tag, tutugma lang ang expression na ito sa address kung naglalaman ang text ng attribute na "href" (\S ay ginagamit para sa lahat ng character maliban sa mga delimiter) . Ngunit sa ilang hindi pangkaraniwang mga tag, halimbawa, magkakaroon ng rollback. Halimbawa: “a href= href=href=…. href=something.” Pipigilan ito ng sumusunod na regexp na mangyari kapag pinapalitan ang ".*" sa isang expression ng isang bagay na hindi tumutugma sa "href": a ((?!href).)* href=(\S*)((?!href).)*/

8) Tukuyin ang haba

Naglalaman ang Java ng regexp optimizer na sumusuri sa haba ng input string laban sa minimum at maximum na haba na nakuha mula sa regular na expression. Nagbibigay-daan ito sa iyo na ihinto kaagad ang paghahanap sa ilang mga kaso. Upang tulungan ang mekanismong ito, dapat na tukuyin ang bilang ng mga pag-uulit hangga't maaari (halimbawa, [01]{6} ay tumutugma sa lahat ng binary string na anim na character ang haba).

9) Pumili ng magkaparehong linya

Minsan ang mga string na pareho ay nakatago sa loob ng mga grupo o mga alternatibo: (hello|hell|heel) Ang expression na ito ay maaaring gawing simple upang: he(llo|ll|el) Sa paggawa nito, binibigyan namin ang regexp optimizer ng karagdagang impormasyon.

10) Subukan ang iyong regexp

Maaaring matalino na subukan muna ang regular na expression kapag ito ay gagamitin sa isang application na kritikal sa pagganap. Sumulat ng micro-benchmark na sumusubok sa iyong expression sa iba't ibang data ng input. Tiyaking subukan ang data na may iba't ibang haba, at pati na rin ang data na malapit na tumutugma sa iyong sample.

Mga link:

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 -of-Expression-Processing/