0

私は2つの配列を持つperlスクリプトを持っています.1つはキーで、もう1つは部分文字列です。1 つの配列の部分文字列がキー配列に一致するかどうかを確認する必要があります。レコードの量は膨大で、数百万単位で数えることができるので、検索を高速化するために Inline:C を使用していますが、レコードの処理にはまだ数時間かかります。

--パール部分

//%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");

また、文字列が null で終了していると誤って想定しているため、そうでない場合でも SEGFAULT が発生する可能性があります。

あなたのアプローチ@kは の各要素をスキャンします@nが、(次のコードのように) トライを構築すると、1 回スキャンできます。

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 回行います。

トライへの代替の正規表現最適化には 5.10+ が必要であることに注意してください。Regexp::List は古いバージョンで使用できます。

正規表現エンジンを使用するのではなく、まさにそれを行う関数を使用してトライ検索を実行できるため、適切な C 実装は少し高速になります。

于 2014-02-21T05:45:18.550 に答える