Das performanteste Matching von "any char"

8

Auf https://www.emacswiki.org/emacs/MultilineRegexp findet man den zu verwendenden Hinweis

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

anstelle des Standards

. * \ n

um ein beliebiges Zeichen einer neuen Zeile zuzuordnen, um einen Stapelüberlauf für große Texte (37 KB) zu vermeiden. Ist der Überlauf hier das Problem, oder ist ein Matching-Lauf für den ersteren auch performanter als für den letzteren?

regular-expressions Vroomfondel
quelle

Antworten:

9

Stimmt in Emacs 'regulären Ausdrücken .nicht mit allen Zeichen überein. Es ist ein Synonym für [^\n]. Der Grund für die Verwendung [\0-\377[:nonascii:]]ist also, wenn Sie "ein beliebiges Zeichen, sogar eine neue Zeile" finden möchten.

Wenn der Stapel überläuft, .*\nsollte er sehr effizient gehandhabt werden, dh ohne Rückverfolgung und ohne den Stapel zu verschlingen. Im Gegenteil, [\0-\377[:nonascii:]]*\ndie Regexp-Engine von Emacs wird ziemlich ineffizient gehandhabt, da sie für jedes übereinstimmende Zeichen einen Teil des Stapels verschlingt, sodass bei "großen" Texten der Stapel tendenziell überläuft.

Beachten Sie, dass das Emacswiki vorschlägt [\0-\377[:nonascii:]]*und nicht [\0-\377[:nonascii:]]*\n.

Stefan
quelle
Danke für die Klarstellung. Sind Sie jedoch sicher, dass [\ 0- \ 377 [: nonascii:]] * \ n für den Stapelüberlauf einen Überlauf verursacht? Dies ist das Gegenteil von dem, was das Wiki behauptet. Ist das bcs von \ n am Ende? Welchen Nutzen hätte dann ein Muster wie [\ 0- \ 377 [: nonascii:]] * ohne Endzeichen?
Vroomfondel
Jeder reguläre Ausdruck, der mit "irgendetwas" übereinstimmt, verbraucht Stapelspeicherplatz (mit der regulären Ausdrucks-Engine von Emacs, meine ich), und ich verstehe nicht, warum er [\0-\377[:nonascii:]]*dann weniger tun würde \\(.\\|\n\\)*. Ich denke, das Emacswiki ist in diesem Fall falsch.
Stefan
Gibt es eine Möglichkeit (oder jemanden), dieses Problem autoritativ zu klären?
Vroomfondel
@ Vroomfondel testen und sehen. Ich kann mir vorstellen, dass der reguläre Ausdruck mit |möglicherweise mehr Backtracking benötigt, aber ob dies tatsächlich der Fall ist, hängt davon ab, wie er kompiliert wird.
npostavs
3
Dies gilt nur, wenn der reguläre Ausdruck mit endet [\0-\377[:nonascii:]]*(was eher ungewöhnlich ist, da Sie ihn genauso gut verwenden point-maxund nicht über einen solchen regulären Ausdruck suchen können) (für Neugierige: Der springende Punkt ist, ob die Zeichensätze übereinstimmen können nach dem * ist dijunkt von dem Satz von Zeichen , die innerhalb der * mithalten können. Wenn es disjunkt ist, dann überspringt der regexp Motor Zwischenschritte aufzeichnen und somit vermeidet Stapelspeicherplatz auffressen. So .*\nund [^a]*anicht verbraucht den Stapel, während .*atut).
Stefan