0

我有一个 perl 脚本，它有 2 个数组，1 个带有键，1 个带有子字符串。我需要检查 1 个数组的子字符串是否在键数组中匹配。记录的数量巨大，可以数以百万计，所以我使用 Inline:C 来加快搜索速度，但是处理记录仍然需要几个小时。

--Perl 部分

//%h contains {"AAAAA1" => 1, "BBBBBB" => 1, "BB1234" =>1, "C12345" => 1.... }
my @k=sort keys %h;
//@k contains ["AAAAA1", "BBBBBB", "BB1234", "C12345".... ]
my @nn;
//@n contains [ "AAAAA1999", "AAAAABBB134", "D123edae", "C12345CCSAER"]
// "AAAAA1" (from @k) can be found in "AAAAA1999" (in @n) = OK
foreach(@n) {
        my $res=array_search(\@k,$_);
        if($res) {
                $y++;
        } else {
                $z++;
                push @nn,$_;
        }
}

--C部分

int fastcmp ( char *p1, char *p2 ) {
  while( *p1 ){
    char *a = p1, *b = p2;    
    if (*b != *a) return 0;
    ++p1; ++b;
  }
  return 1;
}

int array_search(AV *a1, SV *s1){
        STRLEN bytes1;
        char *p1,*p2,*n;
        long a1_size,i,c;
        a1_size = av_len(a1);
        p1 = SvPV(s1,bytes1);        
        for(i=start;i<=a1_size;++i){
            SV** elem = av_fetch(a1, i, 0);
            SV** elem_next = (i<a1_size-1)?av_fetch(a1, i+1, 0):elem;
            p2 = SvPV_nolen (*elem);
            n = SvPV_nolen (*elem_next);
            if (p1[0] == p2[0]) {
                if (fastcmp(p1,p2)>0) {
                    return i; 
                }
            }
            if ((p1[0] == p2[0]) && (p2[0] != n[0])) { return -1; }
        }
        return -1;
}

如果有人可以帮助优化搜索，那就太好了。谢谢。

注意：添加了注释以帮助每个变量内部的内容。

4

1 回答 1

2

您的实现在很多方面都失败了：

  • 失败@a=chr(0xE9); utf8::upgrade($x=$a[0]); array_search(\@a, $x);
  • 失败"abc"=~/(.*)/; array_search(["abc"], $1);
  • 失败array_search(["a\0b"], "a\0c");

它还错误地假设字符串是以空结尾的，如果不是，这可能会导致 SEGFAULT。

您的方法会扫描@k的每个元素@n，但如果您构建一个 trie（如以下代码所做的那样），则可以扫描一次。

my $alt = join '|', map quotemeta, keys %h;
my $re = qr/^(?:$alt)/;

my @nn = sort grep !/$re/, @n;
my $z = @nn;
my $y = @n - @nn;

例如，如果有 1,000 个 N 和 1,000 个 H，您的解决方案最多可以进行 1,000,000 次比较，而我的解决方案可以进行 1,000 次比较。

请注意，将交替的正则表达式优化为 trie 需要 5.10+。Regexp::List 可用于旧版本。

正确的 C 实现会快一点，因为您可以使用执行此操作的函数进行 trie 搜索，而不是使用正则表达式引擎。

于 2014-02-21T05:45:18.550 回答