perl - 查找相同长度的两个字符串之间不匹配位置的最快方法

我有数百万对相同长度的字符串，我想进行比较和查找
不匹配的位置。

例如，对于每个$str1和$str2，我们要查找不匹配项
$str_source的位置：

$str_source = "ATTCCGGG";

$str1       = "ATTGCGGG"; # 1 mismatch with Str1 at position 3 (0-based)
$str2       = "ATACCGGC"; # 2 mismatches with source at position  2 and 7

有没有一种快速的方法来做到这一点。目前我有我循环的C样式方法
使用'substr'函数在两个字符串中的每个位置。但是这种方法太慢了。

my @mism_pos;
for $i (0 .. length($str_source)) {
   $source_base = substr($str_source,$i,1);
   $str_base    = substr($str2,$i,$1);

  if ($source_base ne $str_base) {
     push @mism_pos,$i;
  }

}

最佳答案

Inline::C


计算很容易，使用Inline::C
（有关文档，请阅读perldoc Inline::C-Cookbook和perldoc Inline::C）：

use Inline C => << '...';
  void find_diffs(char* x, char* y) {
    int i;
    Inline_Stack_Vars;
    Inline_Stack_Reset;
    for(i=0; x[i] && y[i]; ++i) {
      if(x[i] != y[i]) {
        Inline_Stack_Push(sv_2mortal(newSViv(i)));
      }
    }
    Inline_Stack_Done;
  }
...

@diffs= find_diffs("ATTCCGGG","ATTGCGGG");  print "@diffs\n";
@diffs= find_diffs("ATTCCGGG","ATACCGGC");  print "@diffs\n";

这是此脚本的输出：

> script.pl
3
2 7

PDL

如果要在Perl中快速处理大量数据，请学习PDL（Documentation）：

use PDL;
use PDL::Char;
$PDL::SHARE=$PDL::SHARE; # keep stray warning quiet

my $source=PDL::Char->new("ATTCCGGG");
for my $str ( "ATTGCGGG", "ATACCGGC") {
  my $match =PDL::Char->new($str);
  my @diff=which($match!=$source)->list;
  print "@diff\n";
}

（与第一个脚本输出相同。）

注意：我很高兴在基因组数据处理中使用了PDL。与内存映射访问存储在磁盘上的数据一起，可以快速处理大量数据：所有处理都在高度优化的C循环中完成。另外，您可以通过Inline::C轻松访问PDL中缺少的所有功能的相同数据。

但是请注意，创建一个PDL向量的速度非常慢（持续时间长，对于大型数据结构是可以接受的）。因此，您宁愿一次创建所有输入数据的大型PDL对象，而不是遍历单个数据元素。