Dikirim dening Eyal Schneider tanggal 21 Mei 2009 Paket java.util.regex ditambahake menyang Jawa ing versi 1.4. Iki minangka alat sing kuat banget lan kudu dadi master supaya bisa digunakake kanthi bener. Sanajan
ekspresi reguler bener, bisa uga alon banget yen ora ditulis kanthi cerdas. Terus maca yen sampeyan pengin ngerti sabab saka masalah, utawa gulung menyang mburi kaca ngendi sampeyan bakal nemokake 10 tips migunani kanggo nambah kinerja saka ekspresi reguler ing Jawa.
Apa tenan sing alon?
Ayo kita milih mung baris sing ngemot urutan karakter "a" lan "b". Solusi sing bener bisa uga:
(a*b*)* Nanging, yen sampeyan mbukak ekspresi kasebut, contone, senar "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaax" , bakal njupuk sawetara menit sadurunge rampung lan laporan ora cocog! Mesthi, regex paling apik ing kasus iki bakal:
(a|b)* Iki njupuk kurang saka millisecond ing mesin karo senar padha. Cetha ana masalah kinerja ing kene.
Yagene iki kedadeyan?
Kaya umume mesin regexp, Jawa nggunakake pendekatan NFA (Non-Deterministic Finite Automata). Mesin mindhai komponen regex siji-siji lan maju liwat string input. Lan dheweke bisa bali menyang wiwitan kanggo nemokake alternatif sing cocog yen dheweke tekan "mati". Asil alternatif dipikolehi kanthi nggunakake struktur reguler kayata kuantifier (
*, +, ? ) lan gantian (contone
a|b|c|d ). Teknik panliten iki diarani backtracking. Ing conto elek ndhuwur, engine bener bakal katon liwat ALL seri decompositions saka simbol "a" menyang seri cilik nganti nyadari yen ora ana sing cocog. Conto iki nuduhake carane algoritma backtracking bisa ngasilake perkiraan wektu eksponensial (gumantung saka dawa string input). Iki uga nuduhake properti penting NFA: mesthi ana kasus paling awon sing meh cocog karo pola kasebut. Yen cocog ditemokake, panelusuran mandheg. Pendekatan utama liyane sing digunakake ing regex yaiku DFA (Deterministic Finite Automaton). Ing pendekatan iki, ekspresi reguler bener-bener nggawe otomatis sing digunakake kanggo ngliwati karakter string input kanthi karakter tanpa mundur. Iki menehi wektu linear kanggo kabeh input, preduli saka kerumitan saka expression biasa. Tinimbang sequentially mindhai senar kanggo cocog (kaya ing NFA), DFA simulates mindhai podo. Dadi apa Jawa (lan .NET, Perl, Python, Ruby, PHP, etc.) nggunakake NKA lan ora DKA kang wis prilaku luwih apik? Alasane yaiku NKA nduweni sawetara kaluwihan sing signifikan:
- Kompilasi luwih cepet lan mbutuhake memori sing luwih sithik
- Ngidini sawetara fitur migunani (ndeleng tutorial Sun kanggo rincian ):
- Group Capture lan Backlinks
- Priksa posisi
- Pangukuran sing Diperpanjang (Rakus lan Kesed)
Wigati dimangerteni manawa istilah populer NKA lan DKA ora tepat nalika digunakake ing konteks ekspresi reguler. Ing teori, loro model iki nduweni daya komputasi sing padha. Iki tegese sampeyan ora bisa nulis ekspresi reguler ing siji model automata sing ora bisa ditulis ing model liyane. Ing laku, perlu kanggo kapabilitas liyane supaya rong jinis implementasine beda ing semantik. Mesin NKA nyedhiyakake fleksibilitas sing luwih dhuwur tinimbang DKA ing daya komputasi. Amarga kacepetan DFA lan fitur unik saka NFA, ana 2 liyane "prefabricated" cara kanggo ngleksanakake ungkapan biasa. Sawetara implementasi nggunakake loro jinis (contone GNU egrep, sing milih mesin tartamtu nalika runtime), lan sawetara wis ngatur kanggo ngleksanakake versi hibrida tenan (contone Tcl regexps) karo kabeh keuntungan.
pitutur
Ing ngisor iki sawetara tips babagan carane supaya masalah efisiensi regex ing Jawa. Akeh wong sing ngarahake nyuda bali.
1) Pra-kompilasi
Trite, nanging worth mentioning. Yen sampeyan nggunakake regexp luwih saka sepisan, mesthine kanggo ngumpulake sadurunge:
// компиляция p = Pattern.compile(regex, flags); … // использование Matcher a = p.matcher(input);
2 ) Pengukuran Lazy vs
Kanthi gawan, quantifiers (
* + ? ) iku rakus. Iki tegese padha miwiti cocog karo urutan paling dawa lan banjur mboko sithik bisa maneh yen perlu. Yen sampeyan ngerti sadurunge sing cocog biasane bakal cendhak, sampeyan kudu nggunakake quantifiers puguh. Dheweke miwiti kanthi pertandhingan sing paling cilik lan luwih maju yen perlu. Contone, kita mung pengin golek baris sing cocog karo urutan "hello". Biasane
.*hello.* bakal nindakake kabeh kanthi bener, nanging yen kita ngerti yen "hello" biasane katon luwih cedhak karo wiwitan teks, banjur
.*?hello.* bakal luwih cepet rata-rata.
3) Gunakake quantifiers super rakus yen bisa
Ora kaya pengukur males, sing mengaruhi kinerja nanging ora mengaruhi prilaku biasa, pengukur super rakus bisa ngganti makna ekspresi reguler. Nalika
*+ digunakake tinimbang
* , pertandhingan pisanan bakal dadi rakus (yaiku, sing paling gedhe kaya mung *), nanging ora ana mundur yen gagal, sanajan iki nyebabake kabeh telusuran gagal. Kapan iki bisa migunani? Ayo kita kudu golek teks ing kuotasi.
\"[^\"]*\" biasa bakal bisa digunakake kanthi becik. Nanging, bakal nggawe indentasi sing ora perlu ing kasus negatif (contone, "bla bla bla). Nggunakake
\"[^\"]*+\" bakal ngilangi rollbacks tanpa ngganti makna ekspresi. Kelompok independen entuk efek sing padha lan menehi kontrol luwih akeh (ndeleng
tutorial Sun ).
4) Aja njupuk klompok
Sembarang ekspresi ing kurung dianggep minangka grup kanthi standar. Iki duwe pengaruh cilik ing kinerja. Gawe grup sampeyan "ora bisa dicekel" yen bisa kanthi miwiti nganggo
(?: tinimbang
( .
5) Gunakake interleaving wisely
Nalika interleaving digunakake (contone
Paul|Jane|Chris ), urutan mesin nyoba kanggo cocog pilihan padha karo urutan kang katon. Sampeyan bisa njupuk kauntungan saka fitur iki lan nyeleh opsi paling umum nyedhaki wiwitan. Iki bakal nambah wektu respon positif rata-rata.
6) Nyingkiri ambiguitas
Tulis regexps ing kuwi cara kanggo nyilikake nomer cocog beda ing senar input. Contone: ekspresi reguler
(a*b*)* sing diwenehake ing wiwitan artikel ngidini string "aabb" diinterpretasikake kanthi akeh cara:
(a2b2) (a1)(a1)(b1)(b1) (a2)(b2) (a1)(a1b2) etc… Regexp
(a|b)*, ing tangan liyane, mung napsirake unik. kombinasi positif. Iki penting banget kanggo nyuda pengembalian ing kasus
sing cedhak .
7) Pratinjau
Pratinjau ngidini sampeyan nambah watesan ing urutan ing sisih kiwa / tengen posisi saiki. Ing tartamtu, karo lookahead negatif, sampeyan bisa nelusuri baris sing ora ngemot sawetara urutan (apa sing bakal kita tindakake tanpa iki!). Kepiye carane bisa nambah produktivitas? Contone, kita pengin njupuk URL saka tag link. Coba regexp ing ngisor iki:
a .* href=(\S*).*/ Kanggo tag biasa, ekspresi iki mung cocog karo alamat yen teks ngemot atribut "href" (\S digunakake kanggo kabeh karakter kajaba pembatas). Nanging ing sawetara tag sing ora biasa, contone, rollback bakal kedadeyan. Contone: "a href= href= href=…. href=sesuatu.” Regexp ing ngisor iki bakal nyegah kedadeyan kasebut nalika ngganti ".*" ing ekspresi sing ora cocog karo "href":
a ((?!href).)* href=(\S*)((?!href).)*/
8) Nemtokake dawa
Jawa ngemot optimizer regexp sing mriksa dawa senar input marang dawa minimal lan maksimum dijupuk saka expression biasa. Iki ngidini sampeyan langsung mandheg nggoleki ing sawetara kasus. Kanggo mbantu mekanisme iki, jumlah repetisi kudu ditemtokake sawayah-wayah (contone,
[01]{6} cocog karo kabeh string biner sing dawane enem karakter).
9) Pilih garis sing padha
Kadang strings sing padha didhelikake nang kelompok utawa alternatif:
(hello|hell|heel) expression iki bisa simplified kanggo:
he(llo|ll|el) Kanthi mengkono kita menehi regexp optimizer informasi luwih lengkap.
10) Tes regexp sampeyan
Sampeyan bisa uga wicaksana kanggo nyoba ekspresi reguler dhisik nalika bakal digunakake ing aplikasi kritis kinerja. Tulis pathokan mikro sing nguji ekspresi sampeyan ing macem-macem data input. Priksa manawa sampeyan nyoba data kanthi dawa sing beda-beda, lan uga data sing cocog karo sampel sampeyan.
Pranala:
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/
GO TO FULL VERSION