Pencocokan performan terbanyak dari "any char"

8

Di https://www.emacswiki.org/emacs/MultilineRegexp kita menemukan petunjuk untuk digunakan

[\ 0- \ 377 [: nonascii:]] * \ n

bukannya standar

. * \ n

untuk mencocokkan karakter apa pun hingga baris baru untuk menghindari stack overflow untuk teks besar (37 KB). Apakah overflow menjadi perhatian di sini, atau apakah pencocokan berjalan untuk mantan juga lebih berkinerja daripada yang kedua?

regular-expressions Vroomfondel
sumber

Jawaban:

9

Di regexps Emacs, .tidak cocok dengan semua karakter. Ini adalah sinonim dari [^\n]. Jadi alasan penggunaannya [\0-\377[:nonascii:]]adalah ketika Anda ingin mencocokkan "karakter apa pun, bahkan baris baru".

Jika meluap tumpukan, .*\nharus ditangani dengan sangat efisien, yaitu tanpa mundur dan tanpa memakan tumpukan. Sebaliknya [\0-\377[:nonascii:]]*\nditangani agak tidak efisien oleh mesin regexp Emacs karena akan memakan sedikit tumpukan untuk setiap karakter yang cocok, sehingga pada teks "besar" itu akan cenderung meluap tumpukan.

Perhatikan bahwa emacswiki menyarankan [\0-\377[:nonascii:]]*dan tidak [\0-\377[:nonascii:]]*\n.

Stefan
sumber
Terimakasih atas klarifikasinya. Namun, untuk stack overflow, apakah Anda yakin bahwa [\ 0- \ 377 [: nonascii:]] * \ n akan menyebabkan overflow? Ini bertentangan dengan apa yang diklaim wiki. Apakah ini bcs dari \ n di akhir? Apa gunanya pola seperti [\ 0- \ 377 [: nonascii:]] * tanpa karakter akhir?
Vroomfondel
Setiap regexp yang cocok dengan "apa saja" akan memakan ruang stack (dengan mesin regexp Emacs, maksud saya), dan saya tidak melihat mengapa [\0-\377[:nonascii:]]*melakukannya lebih sedikit \\(.\\|\n\\)*. Jadi saya pikir emacswiki salah dalam hal ini.
Stefan
Adakah cara (atau siapa pun) untuk memperjelas masalah ini secara otoritatif?
Vroomfondel
@Vroomfondel mengujinya dan lihat. Saya bisa membayangkan bahwa regexp dengan |mungkin perlu lebih banyak mundur, tetapi apakah itu benar-benar tergantung pada bagaimana ia dikompilasi.
npostavs
3
Itu benar hanya jika regexp berakhir dengan [\0-\377[:nonascii:]]*(yang agak tidak biasa, karena Anda mungkin lebih baik menggunakan point-maxdaripada mencarinya melalui regexp seperti itu) (untuk yang penasaran: inti masalahnya adalah apakah serangkaian karakter yang dapat cocok setelah * dipisahkan dari set char yang dapat cocok dengan *. Jika disjoint, maka mesin regexp akan melewatkan rekaman langkah-langkah perantara, dan karenanya menghindari memakan ruang stack. Jadi .*\ndan [^a]*ajangan mengkonsumsi stack, sedangkan .*atidak).
Stefan