È meglio usare un qualificatore non avido o un lookahead?

Question

Possiedo un blocco di testo possibilmente grande per cercare istanze di [[...]], dove lo ... può essere qualsiasi cosa, incluse altre parentesi (sebbene non possano essere nidificate; la prima istanza di ]] dopo [[ termina la corrispondenza).

Mi vengono in mente due modi per abbinare questo testo:

• Utilizzando un qualificatore non avido: /\[\[.+?\]\]/
• Utilizzando un lookahead: /\[\[(?:(?!\]\]).)+\]\]/

È uno scelta intrinsecamente migliore rispetto al altro, dal punto di vista delle prestazioni (direi che il primo è probabilmente più leggibile)? Ricordo di aver letto che è meglio non usare qualificatori non golosi, ma non riesco a trovare una fonte per questo ora.

Answer 1

In questo caso è meglio utilizzare un quantificatore non avido.

prendere questa stringa di esempio "[[a]b]]"

non avido quantificatore

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

1. Atom # 1 \[ partite
2. Atom # 2 \[ partite
3. Atom # 3 .+? corrisponde alla "a"
4. Atom # 4 \] partite
5. Atom # 5 \] non riesce, di nuovo a 3 #, ma mantenere la posizione stringa
6. Atom # 3 .+? corrisponda alla posizione della stringa "]"
7. Atom # 4 \] non riesce, di nuovo a 3 #, ma mantenere
8. Atom # 3 .+? corrisponde ai "b"
9. Atom # 4 \] partite
10. Atom # 5 \] partite
11. successo

look-ahead:

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

1. Atom # 1 \[ partite
2. Atom # 2 \[ partite
3. Atom # 4 (?!\]\]) riesce (vale a direnon-match) immediatamente "a", proseguire
4. Atomo # 5 . corrisponde alla "a", ripetere a # 3
5. Atomo # 4 (?!\]\]) raggiunge corrispondenza parziale in "]"
6. Atomo # 4 (?!\]\]) riesce (cioè non-partita) a "b", andare avanti
7. Atom # 5 . corrisponde alla "]", ripetere a # 3
8. Atom # 4 (?!\]\]) riesce (cioè non-match) subito a "b", andare avanti
9. Atom # 5 . corrisponde al "b", ripetere al # 3
10. Atom # 4 (?!\]\]) raggiunge corrispondenza parziale a "]"
11. Atom # 4 (?!\]\]) raggiunge la piena corrispondenza al "]", ergo: # 4 non riesce, l'uscita # 3
12. Atom # 6 \] partite
13. Atom # 7 \] partite
14. successo

Quindi sembra che il quantificatore non avido abbia meno lavoro da fare.

Disclaimer: Questo è un esempio artificiale e le prestazioni della vita reale potrebbero differire, a seconda dell'input, dell'espressione effettiva e dell'implementazione del motore regex. Sono sicuro solo al 98% che quello che ho delineato qui è ciò che sta realmente accadendo, quindi sono aperto alle correzioni. Inoltre, come con tutti i suggerimenti per le prestazioni, non prendere questo valore nominale, fare i propri confronti di riferimento se si vuole sapere con certezza.

Answer 2

Penso che sia preferibile utilizzare il qualificatore non ingordo. Sei sicuro che l'articolo che hai letto non stia dicendo "stai attento con lo avido di corrispondenza?"

Answer 3

Altra variante: /\[\[((?:\]?[^]])+)]]/

Esso utilizza né quantificatori non avidi né look-aheads. Consente un singolo ] prima di qualsiasi non- ]. Se ci fossero due ] in sequenza, la ripetizione interna si fermerebbe e la partita terminerebbe.

Questo modello sarebbe il migliore da utilizzare con i motori regex di compilazione FSA. Sui motori di back-tracking, potrebbe diventare più lento rispetto alla variante non avida.

Answer 4

Quale sapore di regex stai usando? Se si tratta di uno che supporta quantificatori possessivi, c'è un alternativa molto migliore:

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

[^\]]++ fagocita caratteri diversi da ] e non si preoccupa di salvare le informazioni sullo stato che renderebbe backtracking possibile. Se vede uno ], esegue un controllo per vedere se ce n'è un altro. Avvolgere il tutto in un altro quantificatore possessivo significa che fa una sola occhiata ogni volta che vede uno ], e torna indietro solo una volta: quando trova la chiusura ]].

I quantificatori possessivi sono supportati dagli strumenti Java, JGSoft, PCRE (PHP), Oniguruma (Ruby 1.9) e Perl 5.12.Tutti quei sapori anche gruppi di sostegno atomici, che possono essere utilizzati per ottenere lo stesso effetto:

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

Il sapore .NET supporta gruppi atomici, ma non quantificatori possessivi.