Perchè regex non si preoccupa della lunghezza della stringa

Question

Perché la lunghezza dell'ingresso su regex non influisce sulle prestazioni e come è possibile?

La stringa generata è la seguente: 128 caratteri casuali. quindi due numeri tra parentesi. e questo è ripetuto molte volte.

128 radnom characters....(-2435346|45436) 128 radnom characters....(-32525562|-325346) 

Il regex ottiene tutti i numeri tra parentesi. ecco il modello.

\(([-+]?\d+\|[-+]?\d+)\) 

Così le partite sarebbe come

-2435346|45436 
-32525562|-325346 
etc... 

Ecco il codice che fa il punto di riferimento. Avvio del cronometro dopo che l'input è stato generato perché voglio valutare solo il tempo di abbinamento.

Random rand = new Random(); 
Func<string> getRandString = // generates 128 random characters. 
    () => Enumerable.Range(0, 128).Select(x => (char) rand.Next()).Aggregate("", (a, b) => a + b); 
Func<int> getRandInteger =() => rand.Next(); // generates random number. 
string format = "{0}({1}|{2})"; 

// Generate the big string. 
StringBuilder bigstr = new StringBuilder(); 
for (int i = 0; i < 100; i++) // repeat 100 times. 
{ 
    bigstr.Append(string.Format(format, getRandString(), getRandInteger(), getRandInteger())); 
} 
string input = bigstr.ToString(); 

Stopwatch stopwatch = Stopwatch.StartNew(); 
var matches = Regex.Matches(input, @"\(([-+]?\d+\|[-+]?\d+)\)"); 
stopwatch.Stop(); 
Console.WriteLine("Time Elapsed :\t{0}\nInputLength :\t{1}\nMatches Count :\t{2}", stopwatch.Elapsed, input.Length, matches.Count); 

Questa è l'uscita della mia console se ripeto ciclo 10 volte.

Time Elapsed : 00:00:00.0004132 
InputLength : 1500 
Matches Count : 10 

Se ripeto il ciclo 1000 volte.

Time Elapsed : 00:00:00.0004373 // seriously? 
InputLength : 149937 
Matches Count : 1000 

Se ripeto il ciclo 1000000 volte.

Time Elapsed : 00:00:00.0004900 // wtf? 
InputLength : 149964452 
Matches Count : 1000000 

Schermata se non credono

E 'una specie di valutazione pigra? se è così allora come può mostrare il conteggio delle partite? come mai l'ho fatto con il debugger e ho potuto vedere le partite.

C'è qualcosa di particolare nel mio modello di regex che lo rende veloce? ma come la lunghezza della corda non influisce sulle prestazioni? Non capisco.

Answer 1

Uno dei motivi per cui questo accade è che matches.Count proprietà viene valutata pigramente. Quando interrompi il cronometro, il matcher è pronto a fare la corrispondenza, ma non ha trovato nulla. Solo quando chiami matches.Count inizia a funzionare, ma a quel punto hai interrotto i tempi.

Una soluzione semplice è spostare la chiamata matches.Count nella parte del codice che si desidera.

Un'altra ragione è che si include il tempo necessario per analizzare la regex in considerazione. Si tratta di un'operazione relativamente costoso, così si dovrebbe fare prima di accendere il cronometro per una migliore tempistica:

Regex testRegex = new Regex(@"\(([-+]?\d+\|[-+]?\d+)\)"); 
Stopwatch stopwatch = Stopwatch.StartNew(); 
var matches = testRegex.Matches(input); 
var matchesCount = matches.Count; 
stopwatch.Stop(); 
Console.WriteLine("Time Elapsed :\t{0}\nInputLength :\t{1}\nMatches Count :\t{2}", stopwatch.Elapsed, input.Length, matchesCount); 

Ora la crescita del tempo per 10 partite contro 10.000 partite diventa considerevole (00:00:00.0129844 vs. 00:00:00.0843982), anche se non così grande come ci si potrebbe aspettare per una differenza di mille volte nella lunghezza dell'input.