优化正则表达式替换运行时

Question

我有一些代码可以进行大量的正则表达式替换。从本质上讲，它可以归结为这个regex，它在我的一个小示例测试用例中发生了大约50万次：

$string=~s/$pattern/$replacement/g ;

我已经通过qr//在所有模式中预编译了模式(在这个测试用例中大约有2.5K模式(。我已经用NYTProf对此进行了描述，并看到正则表达式引擎的子例程所用的时间如下：

# spent  39.7s making 49461026 calls to CORE:regcomp, avg 802ns/call
# spent  7.94s making 49461026 calls to CORE:subst, avg 161ns/call
# spent  6.61s making 49461026 calls to CORE:match, avg 134ns/call

然而，根据探查器的数据，这条线在大约50K个调用中所花费的时间大约为300秒。所以这本质上意味着正则表达式引擎使用了~53s，而有~250s的开销？？这笔开销包括什么？我想字符串在修改后需要在内存中动态重新分配，但实际上regex只匹配了很少几次，所以我不认为这是开销所在。

此外，我还能做些什么来减少运行时间？模式和替换都是简单的字符串，不使用正则表达式的任何功能(唯一使用的真正正则表达式字符是$pattern开头和结尾的单词边界-\b，否则只是固定单词字符的序列(

编辑：在我问了这个问题之后，我实际上意识到了一个解决方案。让我澄清一下最初的代码是什么样子的，然后解释一下解决方案，如果它将来能帮助到任何人的话。

简化原始代码：

foreach my $string (@strings) {
foreach my $pattern (@patterns) {
my $replacement = $pattern2replacement{$pattern} ;
my $compiled_pattern = $pattern2compiled{$pattern} ;
$string=~s/$compiled_pattern/$replacement/g ;
# do something with $string
}
}

在实际的代码中，内部foreach位于子例程中，在输入foreach之前进行其他检查/预处理。此外，外部foreach并不是一个真正的foreach，而是穿插在代码中的许多地方。

解决方案：

这里的关键点是$string只包含真实的子字符串($pattern(，这些子字符串需要用其他子字符串替换($replacement(。正则表达式可能有些过头了。虽然我确实有多个子字符串需要替换，但它们保证在单词边界上。另外需要注意的一点是，替换可能有一个子字符串，它是@patterns中的前一个模式。例如：

@patterns = ('small', 'blue') ; 
%pattern2replacement = ( 'small' => 'big and blue', 'blue' => 'black') ;

即我们期望字符串CCD_ 1被CCD_因此，以下替代方案提供了巨大的运行时改进：

#Step1: Build complete replacement hash:
my %oneshot_replacement ; 
foreach my $pattern (@patterns) {
my $replacement = $pattern2replacement{$pattern} ;
my @splits = split(/b/, $replacement) ;
@splits = map {exists $oneshot_replacement{$_} ? $oneshot_replacement{$_} : $_} @splits ;
$oneshot_replacement{$pattern} = join("", @splits) ; 
}
#Step2: do substitution without regex:
foreach my $string (@strings) {
my @splits = split(/b/, $string) ;
@splits = map {exists $oneshot_replacement{$_} ? $oneshot_replacement{$_} : $_} @splits ;
$string = join("", @splits) ;
# do something with $string
}

这有助于将运行时间从大约300秒减少到大约20秒。

Answer 1

关于剩下的300秒花在哪里的问题，答案可能是：在探查器中。

假设模式的数量"相对较低"，并且每个模式都是一个完整的单词，我猜这段代码比没有正则表达式的替换要快得多：

my $or = join("|",@patterns);
$string =~ s/b($or)b/$oneshot_replacement{$1}/g;
#print "$string";

无论如何，在上面的第一个代码部分(#Step1:Build complete replacement hash:(中，你犯了2个错误：

#my @splits = split(/b/, $pattern) ;
my @splits = split(/b/, $replacement) ;

如果只想对模式数组进行一次迭代，则必须按照正确的顺序进行(如果可能的话(。

一个适用于您的示例(允许某种扩展(的解决方案是

#@splits = map {exists $oneshot_replacement{$_} ? $oneshot_replacement{$_} : $_} @splits ;
@splits = map {exists $oneshot_replacement{$_} ? $oneshot_replacement{$_} : exists $pattern2replacement{$_} ? $pattern2replacement{$_} : $_} @splits ;