Ist es besser, einen nicht gierigen Qualifier oder Lookahead zu verwenden?

Question

Ich habe einen möglicherweise großen Textblock nach Instanzen von [[...]] zu suchen, wo die ... alles sein kann, einschließlich anderer Klammern (obwohl sie nicht geschachtelt werden können; die erste Instanz von ]] nach [[ endet die Übereinstimmung).

Ich kann von zwei Möglichkeiten denken, diesen Text entsprechen:

• eine nicht gierige Qualifier Verwendung: /\[\[.+?\]\]/
• ein Look-Ahead-Verwendung: /\[\[(?:(?!\]\]).)+\]\]/

Ist eine Wahl von Natur aus besser als die andere, vom Standpunkt der Leistung (ich würde sagen, das erste ist wahrscheinlich lesbarer)? Ich erinnere mich, gelesen zu haben, dass es besser ist, nicht-gierige Qualifier zu verwenden, aber ich kann keine Quelle dafür finden.

Answer 1

Es ist besser, in diesem Fall einen nicht gierigen Quantifizierer zu verwenden.

Nehmen Sie dieses Beispiel Zeichenfolge "[[a]b]]"

Nicht gierig quantifier

 
     \[\[.+?\]\] 
Atom # 1 2 3 4 5 

1. Atom # 1 \[ Matches
2. Atom # 2 \[ Matches
3. Atom # 3 .+? die "a" Spiele
4. Atome # 4 \] Matches
5. Atome # 5 \] fehlschlägt, zurück zu # 3, aber String Position
6. Atome # 3 .+? entsprechen die "]"
7. Atome # 4 \] fehlschlägt, zurück zu # 3 halten, aber String Position halten
8. Atome # 3 .+? entsprechen die "b"
9. Atom # 4 \] Matches
10. Atom # 5 \] Streichhölzer
11. Erfolg

Look-Ahead:

 
     \[\[(?:(?!\]\]).)+\]\] 
Atom # 1 2 3 4  5 6 7 

1. Atom # 1 \[ Matches
2. Atom # 2 \[ Matches
3. Atom # 4 (?!\]\]) erfolgreich ist (das heißtNicht-Spiel) unmittelbar an "a", gehen auf
4. Atom # 5 . die "a" einstimmt, wiederholen Sie auf # 3
5. Atom # 4 (?!\]\]) erreicht teilweise Übereinstimmung bei "]"
6. Atom # 4 (?!\]\]) erfolgreich ist (dh nicht-Spiel bei "b"), gehen auf
7. Atom # 5 . die "]" einstimmt, wiederholen Sie auf # 3
8. Atom # 4 (?!\]\]) erfolgreich ist (dh nicht-Spiel) unmittelbar an "b", gehen auf
9. Atom # 5 . die "b" einstimmt, wiederholen Sie auf # 3
10. Atom # 4 (?!\]\]) erreicht teilweise Übereinstimmung bei "]"
11. Atom # 4 (?!\]\]) erreicht vollständige Übereinstimmung bei "]", ergo: # 4 ausfällt, Ausfahrt # 3
12. Atom # 6 \] Matches
13. Atom # 7 \] Matches
14. Erfolg

Es sieht also so aus, als hätte der nicht-gierige Quantifizierer weniger Arbeit.

Haftungsausschluss: Dies ist ein künstliches Beispiel und die tatsächliche Leistung kann abhängig von der Eingabe, dem tatsächlichen Ausdruck und der Implementierung der Regex-Engine variieren. Ich bin nur zu 98% sicher, dass das, was ich hier skizziert habe, tatsächlich passiert, also bin ich offen für Korrekturen. Wie bei allen Performance-Tipps sollten Sie dies nicht auf den ersten Blick erwägen, machen Sie Ihre eigenen Benchmark-Vergleiche, wenn Sie sicher sein wollen.

Answer 2

Ich denke, es ist besser, den nicht gierigen Qualifier zu verwenden. Sind Sie sicher, dass der Artikel, den Sie gelesen haben, nicht "vorsichtig sein mit gierig übereinstimmen?"

Answer 3

Eine andere Variante: /\[\[((?:\]?[^]])+)]]/

Es weder Nicht-gierige Quantoren verwendet noch Look-aheads. Es erlaubt eine einzige ] vor jeder nicht ]. Wenn es nacheinander zwei ] geben würde, würde die innere Wiederholung stoppen und die Übereinstimmung würde enden.

Dieses Muster würde am besten mit FSA-kompilierenden Regex-Engines verwendet werden. Bei Back-Tracking-Engines könnte es langsamer als die nicht-gierige Variante werden.

Answer 4

Welchen Regex-Geschmack verwenden Sie? Wenn es eine, die possessive Quantoren unterstützt, gibt es eine viel bessere Alternative:

\[\[(?:[^\]]++|\](?!\]))*+\]\] 

[^\]]++ up verschlingt alle anderen Zeichen als ] und stört nicht die Zustandsinformationen speichern, die ermöglichen würde Rückzieher. Wenn es einen ] sieht, führt es einen Lookahead durch, um zu sehen, ob es einen anderen gibt. Das Ganze in einen anderen Possessivquantifizierer zu packen bedeutet, dass es nur dann ein Lookahead macht, wenn es ein ] sieht, und es nur einmal zurückspult: wenn es das abschließende ]] findet.

Possessive-Quantoren werden von den Java-, JGSoft-, PCRE (PHP) -, Oniguruma (Ruby 1.9) - und Perl 5.12-Varianten unterstützt.All diese Aromen unterstützen auch Atomgruppen, die verwendet werden können, um den gleichen Effekt zu erreichen:

\[\[(?>(?:(?>[^\]]+)|\](?!\]))*)\]\] 

.NET Geschmack unterstützt Atomgruppen aber nicht besitzergreifend quantifiers.