Сравните 2 массива строк для совпадений в C оптимизации

Question

У меня есть 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;
}

Если кто-то может помочь оптимизировать поиск, это может быть хорошо. Благодарю.

Примечание: добавлены комментарии, помогающие понять, что находится внутри каждой переменной.

Answer 1

Реализация, которую вы имеете, терпит неудачу во многих отношениях:

• Не для @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;

Например, если есть 1000 Ns и 1000 Hs, ваше решение выполняет до 1 000 000 сравнений, а мое - 1 000.

Обратите внимание, что 5.10+ необходимо для оптимизации регулярных выражений чередований в три. Regexp::List можно использовать в более старых версиях.

Правильная реализация на C будет немного быстрее, потому что вы можете выполнить поиск по три, используя функцию, которая делает это, а не используя механизм регулярных выражений.