Prestasi ungkapan biasa yang lemah?

Dicatat oleh Eyal Schneider pada 21 Mei 2009 Pakej java.util.regex telah ditambahkan pada Java dalam versi 1.4. Ia adalah alat yang sangat berkuasa dan seseorang itu perlu menjadi pakar untuk menggunakannya dengan betul. Walaupun ungkapan biasa adalah benar, ia boleh menjadi sangat perlahan jika tidak ditulis dengan bijak. Teruskan membaca jika anda ingin memahami punca masalah, atau tatal ke hujung halaman di mana anda akan menemui 10 petua berguna untuk meningkatkan prestasi ungkapan biasa di Jawa.

Adakah ia benar-benar lambat?

Katakan kita mahu memilih hanya baris yang mengandungi jujukan aksara "a" dan "b". Penyelesaian yang betul mungkin: (a*b*)* Walau bagaimanapun, jika anda menjalankan ungkapan dengan, sebagai contoh, rentetan “aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaax” , ia akan mengambil masa beberapa minit sebelum ia selesai dan tidak melaporkan padanan! Sudah tentu, regex terbaik dalam kes ini ialah: (a|b)* Ini mengambil masa kurang daripada satu milisaat pada mesin saya dengan rentetan yang sama. Jelas sekali terdapat isu prestasi di sini.

Kenapa ini terjadi?

Seperti kebanyakan enjin regexp, Java menggunakan pendekatan NFA (Non-Deterministic Finite Automata). Enjin mengimbas komponen regex satu demi satu dan memajukan melalui rentetan input dengan sewajarnya. Dan dia boleh kembali ke permulaan untuk mencari alternatif yang sesuai jika dia mencapai "jalan buntu". Keputusan alternatif diperoleh dengan menggunakan struktur biasa seperti pengkuantiti ( *, +, ? ) dan selang-seli (cth a|b|c|d ). Teknik penyelidikan ini dipanggil backtracking. Dalam contoh yang mengerikan di atas, enjin sebenarnya akan melihat melalui SEMUA siri penguraian simbol "a" kepada siri yang lebih kecil sehingga ia menyedari bahawa tiada padanan. Contoh ini menunjukkan cara algoritma penjejakan ke belakang boleh menghasilkan anggaran masa eksponen (bergantung pada panjang rentetan input). Ini juga menunjukkan sifat penting NFA: akan sentiasa ada kes terburuk yang hampir sepadan dengan corak. Jika padanan ditemui, pencarian dihentikan. Pendekatan utama lain untuk digunakan dalam regex ialah DFA (Deterministic Finite Automaton). Dalam pendekatan ini, ungkapan biasa sebenarnya membina automaton yang digunakan untuk melintasi rentetan input aksara mengikut aksara tanpa menjejak ke belakang. Ini memberikan masa linear kepada keseluruhan input, tanpa mengira kerumitan ungkapan biasa. Daripada mengimbas rentetan secara berurutan untuk padanan (seperti dalam NFA), DFA mensimulasikan pengimbasan selari. Jadi mengapa Java (dan .NET, Perl, Python, Ruby, PHP, dll.) menggunakan NKA dan bukan DKA yang mempunyai tingkah laku yang lebih baik? Sebabnya ialah NKA mempunyai beberapa kelebihan penting:

Menyusun lebih cepat dan memerlukan lebih sedikit memori
Membenarkan beberapa ciri berguna (lihat tutorial Sun untuk butiran ):

Tangkapan Kumpulan dan Pautan Balik
Semakan kedudukan
Pengkuantiti Lanjutan (Rakus dan Malas)

Adalah penting untuk ambil perhatian bahawa istilah popular NKA dan DKA adalah tidak tepat apabila digunakan dalam konteks ungkapan biasa. Secara teorinya, kedua-dua model ini mempunyai kuasa pengkomputeran yang sama. Ini bermakna anda tidak boleh menulis ungkapan biasa dalam satu model automata yang mustahil untuk dinyatakan dalam model lain. Dalam amalan, terdapat keperluan untuk lebih banyak keupayaan supaya kedua-dua jenis pelaksanaan berbeza dalam semantik. Enjin NKA memberikan lebih fleksibiliti menjadikannya lebih unggul daripada DKA dalam kuasa pengkomputeran. Disebabkan oleh kelajuan DFA dan ciri unik NFA, terdapat 2 lagi cara "pasangan" untuk melaksanakan ungkapan biasa. Sesetengah pelaksanaan menggunakan kedua-dua jenis (cth GNU egrep, yang memilih enjin tertentu pada masa jalan), dan sesetengahnya telah berjaya melaksanakan versi hibrid yang benar-benar (cth Tcl regexps) dengan semua faedah.

Nasihat

Berikut ialah beberapa petua tentang cara mengelakkan masalah kecekapan regex di Jawa. Kebanyakannya bertujuan untuk mengurangkan pulangan.

1) Pra-penyusunan

Biasa, tetapi patut disebut. Jika anda menggunakan regexp lebih daripada sekali, pastikan anda menyusunnya terlebih dahulu:

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

2) Pengkuantiti Malas vs Pengkuantiti Tamak

Secara lalai, pengkuantiti ( * + ? ) adalah tamak. Ini bermakna mereka mula memadankan dengan urutan terpanjang yang mungkin dan kemudian secara beransur-ansur bekerja semula jika perlu. Jika anda tahu terlebih dahulu bahawa padanan biasanya pendek, anda harus menggunakan pengkuantiti malas. Mereka bermula dengan perlawanan terkecil dan bergerak lebih jauh jika perlu. Katakan kita mahu mencari hanya baris yang sepadan dengan urutan "hello". .*hello.* biasa akan melakukan segala-galanya dengan betul, tetapi jika kita tahu bahawa "hello" biasanya muncul lebih dekat dengan permulaan teks, maka .*?hello.* akan berfungsi lebih cepat secara purata.

3) Gunakan pengkuantiti super tamak jika boleh

Tidak seperti pengkuantiti malas, yang menjejaskan prestasi tetapi tidak menjejaskan tingkah laku biasa, pengkuantiti super tamak sebenarnya boleh mengubah maksud ungkapan biasa. Apabila *+ digunakan dan bukannya * , padanan pertama akan menjadi tamak (iaitu, yang terbesar mungkin seolah-olah ia hanya *), tetapi tidak akan ada sandaran jika ia gagal, walaupun ini menyebabkan keseluruhan carian gagal. Bilakah ini mungkin berguna? Katakan kita perlu mencari teks dalam petikan. \"[^\"]*\" biasa akan berfungsi dengan baik. Walau bagaimanapun, ia akan membuat lekukan yang tidak perlu dalam kes negatif (contohnya, "bla bla bla). Menggunakan \"[^\"]*+\" akan menghapuskan rollback tanpa mengubah maksud ungkapan. Pengumpulan bebas mencapai kesan yang sama dan memberikan lebih banyak kawalan (lihat tutorial Sun ).

4) Elakkan tangkapan berkumpulan

Sebarang ungkapan dalam kurungan dianggap sebagai kumpulan secara lalai. Ini mempunyai kesan kecil terhadap prestasi. Jadikan kumpulan anda "tidak boleh ditangkap" apabila boleh dengan memulakannya dengan (?: bukannya ( .

5) Gunakan interleaving dengan bijak

Apabila interleaving digunakan (cth Paul|Jane|Chris ), susunan enjin cuba memadankan pilihan adalah sama dengan susunan ia muncul. Anda boleh memanfaatkan ciri ini dan meletakkan pilihan yang paling biasa lebih dekat dengan permulaan. Ini akan meningkatkan purata masa tindak balas positif.

6) Elakkan kesamaran

Tulis regexps sedemikian rupa untuk meminimumkan bilangan padanan berbeza dalam rentetan input. Contohnya: ungkapan biasa (a*b*)* yang diberikan pada permulaan artikel membenarkan rentetan "aabb" ditafsirkan dalam terlalu banyak cara: (a2b2) (a1)(a1)(b1)(b1) (a2)(b2) (a1)(a1b2) etc… Regexp (a|b)*, sebaliknya, hanya mentafsir unik kombinasi secara positif. Ini sangat penting untuk mengurangkan pulangan dalam kes hampir perlawanan.

7) Pratonton

Pratonton membolehkan anda menambah sekatan pada jujukan ke kiri/kanan kedudukan semasa. Khususnya, dengan pandangan negatif, anda boleh mencari baris yang tidak mengandungi beberapa urutan (apa yang akan kita lakukan tanpa ini!). Bagaimanakah ini boleh membantu meningkatkan produktiviti? Katakan kita mahu mengambil URL daripada teg pautan. Pertimbangkan regexp berikut: a .* href=(\S*).*/ Untuk teg biasa, ungkapan ini hanya akan sepadan dengan alamat jika teks mengandungi atribut "href" (\S digunakan untuk semua aksara kecuali pembatas) . Tetapi pada beberapa teg yang luar biasa, contohnya, pemulangan semula akan berlaku. Contohnya: “a href= href=href=…. href=sesuatu.” Regexp berikut akan menghalang perkara ini daripada berlaku apabila menggantikan ".*" dalam ungkapan dengan sesuatu yang tidak sepadan dengan "href": a ((?!href).)* href=(\S*)((?!href).)*/

8) Nyatakan panjang

Java mengandungi pengoptimum regexp yang menyemak panjang rentetan input terhadap panjang minimum dan maksimum yang diperoleh daripada ungkapan biasa. Ini membolehkan anda berhenti mencari serta-merta dalam beberapa kes. Untuk membantu mekanisme ini, bilangan ulangan hendaklah ditentukan apabila mungkin (contohnya, [01]{6} sepadan dengan semua rentetan binari enam aksara panjang).

9) Pilih garisan yang sama

Kadangkala rentetan yang sama disembunyikan di dalam kumpulan atau alternatif: (hello|hell|heel) Ungkapan ini boleh dipermudahkan kepada: he(llo|ll|el) Dengan melakukan ini, kami memberi pengoptimum regexp lebih banyak maklumat.

10) Uji regexp anda

Mungkin bijak untuk menguji ungkapan biasa dahulu apabila ia akan digunakan dalam aplikasi kritikal prestasi. Tulis penanda aras mikro yang menguji ekspresi anda pada pelbagai data input. Pastikan anda menguji data dengan panjang yang berbeza-beza, dan juga data yang hampir sepadan dengan sampel anda.

Pautan:

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/