Dlaczego regex nie dba o długość ciągu znaków

Question

Dlaczego długość wejścia w wyrażeniu regularnym nie ma wpływu na wydajność i jak to jest możliwe?

Wygenerowany ciąg jest następujący: 128 losowych znaków. następnie dwie liczby w nawiasach. i to się powtarza wiele razy.

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

Wyliczenie pobiera wszystkie liczby wewnątrz nawiasów. tutaj jest wzór.

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

Więc mecze będzie jak

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

Oto kod, który ma punkt odniesienia. Zaczynam stop stop po wygenerowaniu wejścia, ponieważ chcę tylko ocenić czas dopasowania.

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); 

Jest to wyjście w mojej konsoli, jeśli powtarzam pętli 10 razy.

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

Jeśli powtórzę pętlę 1000 razy.

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

Jeśli powtórzę pętlę 1000000 razy.

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

ekranu, jeśli nie wierzą

Czy to jakiś rodzaj oceny leniwy? jeśli tak, to w jaki sposób może pokazywać liczbę dopasowań? jak to zrobiłem podczas debuggera i mogłem zobaczyć mecze.

Czy jest coś szczególnego w moim schemacie regex, który czyni go szybkim? ale jak długość ciągu nie wpływa na wydajność? Nie mogę zrozumieć.

Answer 1

Jednym z powodów jest to, że właściwość matches.Count jest oceniana jako leniwie. Kiedy zatrzymasz stoper, matcher jest przygotowany do dopasowania, ale niczego nie znalazł. Tylko wtedy, gdy zadzwonisz pod numer matches.Count, zacznie działać, ale zatrzymałeś już czas.

Prostym rozwiązaniem jest przeniesienie wywołania matches.Count do fragmentu kodu, który zajmuje czas.

Innym powodem jest to, że wliczasz czas potrzebny na przeanalizowanie regex. Jest to stosunkowo kosztowna operacja, więc należy to zrobić przed włączeniem stopera dla lepszego czasu:

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); 

Teraz wzrost raz na 10 meczów vs 10.000 meczów staje się znaczna (00:00:00.0129844 vs. 00:00:00.0843982), choć nie tak duże, jak można by się spodziewać po tysiąckroć różnej długości wejściowej.