为什么添加另外一个选项使我的正则表达式比600倍慢?

前端之家收集整理的这篇文章主要介绍了为什么添加另外一个选项使我的正则表达式比600倍慢?前端之家小编觉得挺不错的,现在分享给大家,也给大家做个参考。
我在测试一个简单的Perl脚本时,注意到了 something weird,该脚本应该以某些前缀过滤掉文件名。

基本上,我正在构建一个这样的正则表达式:

  1. my $regex = join "|",map quoteMeta,@prefixes;
  2. $regex = qr/^($regex)/; # anchor the regex and precompile it

这里,在我最初测试的情况下,@prefixes由32个字符的十六进制字符串组成。我发现一切都运行良好,顺利达到6,552个前缀 – 但是一旦我尝试了6,553,the script的执行时间跳了25倍(从1.8秒到51秒)!

我玩弄了它,并构建了以下基准。我最初使用32字符的十六进制字符串,就像我原来的程序一样,但是发现如果我将字符串的长度减少到只有8个字符,阈值就会更高 – 到16,383,而减速因子显着更高:16,383个替代品的正则表达比只有16,382的速度慢几乎650倍!

  1. #!/usr/bin/perl
  2. use strict;
  3. use warnings;
  4. use Benchmark qw(timethese cmpthese);
  5.  
  6. my $count = shift || 10;
  7.  
  8. our @items = map unpack("H8",pack "V",$_),0..99999;
  9.  
  10. our $nA = 16382; our $reA = join "|",@items[1 .. $nA];
  11. our $nB = 16383; our $reB = join "|",@items[1 .. $nB];
  12.  
  13. $_ = qr/^($_)/ for $reA,$reB; # anchor and compile regex
  14.  
  15. my $results = timethese( $count,{
  16. $nA => q{ our (@items,$nA,$reA); $nA == grep /$reA/,@items or die; },$nB => q{ our (@items,$nB,$reB); $nB == grep /$reB/,} );
  17. cmpthese( $results );

以下是使用Perl(v5.18.2)在笔记本电脑上运行此基准测试的结果:

  1. Benchmark: timing 10 iterations of 16382,16383...
  2. 16382: 2 wallclock secs ( 1.79 usr + 0.00 sys = 1.79 cpu) @ 5.59/s (n=10)
  3. 16383: 1163 wallclock secs (1157.28 usr + 2.70 sys = 1159.98 cpu) @ 0.01/s (n=10)
  4. s/iter 16383 16382
  5. 16383 116 -- -100%
  6. 16382 0.179 64703% --

注意64,703%的速度差。

我的原始预感,基于6553和大约的数值巧合216/10,这可能在Perl正则表达式引擎中可能是一种任意限制,或者也许有一些10位结构的数组被限制为64 kB,或者​​是某种东西。但是,替代品的阈值数量取决于它们的长度这一事实使事情变得更加混乱。

(另一方面,它显然不仅仅是正则表达式的长度,原始的正则表达式具有6,553个32字节的替代方案是2 6,553×33 = 216,251字节长,而具有16,383个8字节的替代方案的正则表达式仅为2 16,383×9 = 147,450字节长)

什么是正则表达式匹配时间的这个奇怪的跳跃,为什么会发生在这个特定点?

长久以来,Perl的TRIE优化没有被应用到正则表达式的初始编译生成longjmp而不是jmp(我认为)指令(这取决于所涉及的字符串的交替数量和总长度,还有什么)更早?)在正则表达式中)。

看到区别:

  1. perl -we'use re "debug"; qr/@{[join"|","a".."afhd"]}/'

  1. perl -we'use re "debug"; qr/@{[join"|","a".."afhe"]}/'

您可以将您的交替分解成更小的块,并分别预编译它们。 (?? {$ RXA})|(?? {$ RXB})|(?? {$ RXC})。

猜你在找的正则表达式相关文章