Быстрый способ найти строку, ограниченную двумя словами


Мотивируется этот вопрос, я создал простой тест для выяснения того, что это самый быстрый способ, чтобы извлечь подстроку, дали два ограничительных слова:

#! /usr/bin/env perl
use feature qw(say);
use strict;
use warnings;

use Benchmark qw(cmpthese);
use Inline C => './find_c.c';

my %methods = (
    find_quick   => \&find_quick,
    find_substr  => \&find_substr,
    find_index   => \&find_index,
    find_regex1  => \&find_regex,
    find_regex2  => \&find_regex,
    find_c       => \&find_c,
);

my %test_types = (
    short  => 2,
    medium => 20,
    long   => 200,
);

my $num_tests = ( scalar keys %test_types ) ** 3;
my $i = 1;
for my $delim_type (qw( short medium long )) {
    for my $substr_type (qw( short medium long )) {
        for my $prefix_type (qw( short medium long )) {
            run_test( $delim_type, $substr_type, $prefix_type, $i++, $num_tests );
        }
    }
}

sub run_test {
    my ( $delim_type, $substr_type, $prefix_type, $i, $N ) = @_;

    my $delim_len = $test_types{$delim_type};
    my $substr_len = $test_types{$substr_type};
    my $prefix_len = $test_types{$prefix_type};
    say "";
    say "----------------------------------";
    say "Running case: ($i/$N) delim=$delim_type,"
      . " substr=$substr_type, prefix=$prefix_type";
    say "----------------------------------";
    say "";
    my $delim1 = '<' x $delim_len;
    my $delim2 = '>' x $delim_len;
    my $substr = '1' x $substr_len;
    my $prefix = '2' x $prefix_len;
    my $postfix = '3' x 12; # some arbitrary trailing string

    my $regex1 = qr/\Q$delim1\E((?:(?!\Q$delim2\E).)*+)\Q$delim2\E/;
    my $regex2 = qr/\Q$delim1\E(.*?)\Q$delim2\E/;

    my $str = $prefix . $delim1 . $substr . $delim2 . $postfix;


    my %cmphash;
    # Before running the benchmark, check that all methods give correct output..
    for my $key (keys %methods) {
        my $method;
        if ( $key =~ /regex1/ ) {
            $method = sub { return $methods{$key}->( $str, $regex1 ) };
        }
        elsif ( $key =~ /regex2/ ) {
            $method = sub { return $methods{$key}->( $str, $regex2 ) };
        }
        elsif ( $key =~ /quick/ ) {
            $method = sub { return $methods{$key}->( $str, $substr ) };
        }
        else {
            $method = sub { return $methods{$key}->( $str, $delim1, $delim2 ) };
        }
        my $chk = $method->();
        if ( $chk ne $substr ) {
            die "Method: '$key' did not return correct result.\n";
        }
        $cmphash{$key} = $method;
    }
    cmpthese( -1, \%cmphash );
}

# Dummy method, to provide an lower limit on the run time
sub find_quick {
    my ($str, $substr) = @_;

    return $substr;
}

sub find_regex {
    my ($str, $regex) = @_;

    if ( $str =~ $regex) {
        return $1;
    }
    else {
        return "";
    }
}

sub find_index {
    my ($str, $delim1, $delim2) = @_;

    my $offset = (index $str, $delim1) + length $delim1;
    my $len = (index $str, $delim2, $offset) - $offset;
    return substr $str, $offset, $len; 
}

sub find_substr {
    my ($str, $delim1, $delim2) = @_;

    my $tmp = substr $str,
      (index $str, $delim1) + length $delim1;
    return substr $tmp, 0, index $tmp, $delim2;
}

И C исходный файл find_c.c это:

/* checks if the current position in str matches string delim
 *
 * Input arguments:
 *   i    : current position in str,
 *   len1 : length of str
 *   len2 : length of delim
 */ 
int check_delim( char *str, int i, char *delim, STRLEN len1, STRLEN len2 ) {
    int j = 0;
    while ( i < len1 ) {
        if ( str[i++] != delim[j++] ) {
            break;
        }
        if ( j >= len2 ) return 1;
    }
    return 0;
}

/* finds a substring of str delimited by strings delim1 at the left,
 * and delim2 at the right. 
 * Assumes neither of str, delim1, or delim2 are empty.
 */
SV *find_c(SV* str_sv, SV *delim1_sv, SV *delim2_sv) {
    STRLEN len, len1, len2;
    char *str = SvPVbyte(str_sv, len);
    char *delim1 = SvPVbyte(delim1_sv, len1);
    char *delim2 = SvPVbyte(delim2_sv, len2);
    if (len == 0 || len1 == 0 || len2 == 0) {
        croak( "Illegal input. Strings cannot be empty." );
    }
    SV* result = newSV(len);
    char *buf = SvPVX(result);
    int start = -1;
    int end = -1;
    // scan str from left for delim1
    for (int i = 0; i < (len - len1); i++) {
        if ( str[i] == delim1[0] ) {
            if ( check_delim( str, i, delim1, len, len1 ) ) {
                start = i + len1;
                break;
            }
        }
    }
    int j = 0; // index into result buffer
    // did we find delim1, if so continue scan for delim2
    if (start >= 0) {
        for (int i = start; i < (len - len2 + 1); i++) {
            if ( str[i] == delim2[0] ) {
                if ( check_delim( str, i, delim2, len, len2 ) ) {
                    end = i;
                    break;
                }
            }
            buf[j++] = str[i]; // copy to result buffer
        }
    }
    if ( end < 0 ) { // we did not find delim2..
        j = 0; // reset result index (meaning: erase everything, and put empty string)
    }
    buf[j] = '\0';  // null terminate result string
    SvPOK_on(result); // Make the result SV a string (i.e. a PV)
    SvCUR_set(result, j); // Set the length of the string in the result SV.
    return result;
}

Замечания:

На основе работает 27 тестов на моем ноутбуке (см. Вывод), я вижу, что:

  • regex1 всегда медленнее, чем regex2
  • index и substr примерно одинаковая скорость для всех случаев
  • substr/index обычно быстрее, чем regex2но не для некоторых случаях, когда разделители длинные, см. примеры 19, 21, 25
  • find_c обычно быстрее, чем другие методы, но не для случая 9, где разделитель короткий и подстрока долго.
  • В некоторых простых случаях find_c быстрее, чем верхний предел, предоставленной find_quickсм. случаи 1 и 2.


Комментарии
1 ответ


Быстрый способ найти строку, ограниченную двумя словами

check_delim() могут быть линейно быстрее, воспользовавшись, что строка заканчивается с первым нулевым символом.

Нет необходимости 2 проверка длины на каждой итерации цикла. Код можно получить с 1 Проверить и часто 0 продолжительность проверок.

Использовать const чтобы разрешить дополнительные оптимизации.

Имена изменить для ясности.

int check_delim(const char *str, int i, const char *delim, 
STRLEN len_str, STRLEN len_delim ) {
if (i >= len_str) { // This test might be able to be omitted.
return 0;
}
len_str -= i;
str += i;
if (len_str == len_delim) {
// same length - check offset and look for any mis-match
while (--len_str > 0 && str[len_str] == delim[len_str]) {
;
}
return str[len_str] == delim[len_str];
}
i = 0;
// Different lengths - look for any mis-match - no need to check `i`.
// Null character of one string will not match the non-null character of the other.
while (str[i] == delim[i]) {
i++;
}
// Did str[] match all the delimiter?
return delim[i] == '\0';
}

Примечание: Я ожидала int i к тому же типу, что STRLEN len_str.

2
ответ дан 16 февраля 2018 в 06:02 Источник Поделиться