在 Perl 中，如何加速正则表达式来修改一个非常大的字符串

Question

我有一个由 3 亿个碱基组成的字符串;

$str = "ATCGTAGCTAGXCTAGCTAGCTGATXXXXATCGTAGCTAGCTGXTGCTAGCXXXXA...A";

我想将字符串中不是 [ATGC] 的字符替换为其他字符，比如说"A"，同时获取已替换字符的位置;

我试过这个：

while ($str=~/[^ATGC]/ig)
{
  $pos = pos($str);
  substr($str, $pos-1,1) = "A";
}

但是速度不好。

有谁知道更好的方法可以做到这一点？

Answer 1

正

则表达式也可以替换和匹配。

$str =~ s/X/A/g;

如果你只做一个角色，你甚至可以使用tr运算符。

$str =~ tr/X/A/g;

这甚至可能更快。

Answer 2

您可以使用搜索和替换直接使用正则表达式执行替换：

$str =~ s/X/A/ig;

Answer 3

如有疑问，基准测试

use strict;
use warnings;
use v5.14;
use Benchmark qw(cmpthese);
my @l = qw(A T G C X);
my $BAR;
$BAR .= $l[rand(@l)] for 1..10000;
cmpthese(-1, {
    substr          => sub { my $str = $BAR; 
                         while ($str=~/X/ig) {
                             my $pos = pos($str);
                             substr($str, $pos-1,1) = "A";
                         } return $str; },
    substitution    => sub { my $str = $BAR; $str =~ s/X/A/ig;  return $str; },
    transliteration => sub { my $str = $BAR; $str =~ tr/xX/aA/; return $str; }});

结果：

                   Rate          substr    substitution transliteration
substr           55.1/s              --            -98%           -100%
substitution     2496/s           4433%              --            -93%
transliteration 35134/s          63719%           1308%              --

正如我们从结果中看到的那样，对于这个特定的字符串和正则表达式，substr 方法确实非常慢，每秒 55 个。使用替换的速度大约快 45 倍，但这与音译快 600 倍相形见绌。

因此，在这种情况下，音译似乎是最快的。这是有道理的，因为它是迄今为止最简单的潜艇。

Answer 4

如果您只想替换输入字符串中的"X"字符，音译是要走的路，它将大大提高您的速度。

记录替换字符的位置有点增加皱纹。 我会建议如下：

my $huge_string = "GATTACAXX.......";
my $length = length($huge_string);
my $i = 0;
my $output_string;
my @x_positions;
while ($i < $length) {
    my $curr_char = substr($huge_string, $i, 1);
    if ($curr_char eq "X") {
        push (@x_positions, $i);
        $output_string .= "A"; # or G, C, T, etc.
    } else {
        $output_string .= $curr_char;
    }
    $i++;
}
# do something with $output_string and @x_positions...

我在>1,000,000 个字符的测试字符串上运行了它，它在不到一秒钟的时间内完成，而原始代码片段的运行时间约为 3 分钟。

希望有帮助。

Answer 5

如果您只是用另一个字符替换一个字符（而不是逐个字符串或逐个字符串!!），音译会更快： $str =~ tr/X/A/;如果你需要复杂的正则表达式模式，请考虑使用 re：：engine：：RE2，这是 Google RE2 引擎的 Perl 绑定。请注意，它只对复杂的正则表达式更快。