为什么正则表达式不关心字符串长度

Question

为什么正则表达式的输入长度不会影响性能,这怎么可能？

生成的字符串如下:128个随机字符.括号内有两个数字.这个重复了很多次.

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

正则表达式获取括号内的所有数字.这是模式.

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

所以比赛就像

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

以下是执行基准测试的代码.我在生成输入后启动秒表,因为我只想评估匹配时间.

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

如果我重复循环10次数,这是我的控制台中的输出.

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

如果我重复循环1000次数.

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

如果我重复循环1000000次数.

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

屏幕截图,如果你不相信

这是一种懒惰的评价吗？如果是,那么它如何显示比赛的数量？我怎么在调试器下做这个,我可以看到匹配.

在我的正则表达式模式中是否有特别的东西使它快速？但字符串长度如何不影响性能？我不明白.

Answer 1

发生这种情况的原因之一是matches.Count财产被懒惰地评估.当你停止你的秒表时,匹配器准备进行匹配,但它没有找到任何东西.只有当你打电话时matches.Count它才开始工作,但你已经停止了时间.

一个简单的解决方案是将matches.Count调用移动到您需要的代码部分.

另一个原因是你要考虑解析正则表达式所需的时间.这是一个相对昂贵的操作,所以你应该在打开秒表之前进行更好的计时:

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

现在,10场比赛与10,000场比赛的时间增长相当可观(00:00:00.0129844相对于00:00:00.0843982),尽管没有人们对输入长度的千倍差异所期望的那么大.