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

Question

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

7

为什么在正则表达式中输入长度不影响性能，这是怎么实现的呢？

生成的字符串格式如下：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

如果你不信，请看截图。

这是一种懒惰求值的方式吗？如果是，那么它如何显示匹配项的数量？然而，在调试器中，我可以看到有匹配项。

我的正则表达式模式中是否有特殊的东西使其更快？但是为什么字符串长度不会影响性能呢？我无法理解。

- M.kazem Akhgary

这里没有什么特别的。您的正则表达式引擎将遍历字符串并保存与您的正则表达式匹配的所有状态，对于现代计算机来说，在一个比原来大1000倍的字符串上进行基准测试不是什么大问题。只需尝试更大的字符串。或者可能您的基准测试不公平。 - Mazdak

1

如果您想了解.NET正则表达式引擎使用的字符串搜索算法的详细信息，您可能会对我的这个答案感兴趣。 - Lucas Trzesniewski

1

适当的基准测试：https://andreyakinshin.gitbooks.io/performancebookdotnet/content/science/microbenchmarking.html - Dmitrii Dovgopolyi

@LucasTrzesniewski 谢谢。这很有帮助。我现在明白了，在调试器下它之所以快速显示部分结果，是因为只有字符串的一部分被评估了。 - M.kazem Akhgary

1

顺便提一下，在字符类“[-|+]”中去掉“|”，即“[-+]”。您当前的代码允许数字前面有“|”。此外，没有必要懒惰地匹配第二个数字“\d+？” ，只需使用“\d+”。 - nhahtdh

@nhahtdh 谢谢您提到这一点。是的，那是一个错误。我认为应该在字符类中使用OR，所以我使用了|。我也不知道为什么要用?使它变成非贪婪模式。当然，这是多余的。 - M.kazem Akhgary

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Sergey Kalinichenko · Accepted Answer

这种情况发生的原因之一是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），尽管输入长度相差一千倍，但增长速度并不像人们预想的那样快。