Perl: сортировка символов в строке

Question

У меня есть две строки, и я хотел бы проверить, являются ли они анаграммами друг друга.

Чтобы проверить, является ли строка A анаграммой строки B, символы A и B отсортированы.Если результирующие отсортированные строки точно совпадают, строка A и строка B являются анаграммами друг друга.

Я split выводю строки в символьные массивы, используя процедуру sort Perl, join используясимволы вместе, и проверка на равенство строк с eq:

sub anagram
{
  my ($s1, $s2) = @_;

  return (join '', sort { $a cmp $b } split(//, $s1)) eq
         (join '', sort { $a cmp $b } split(//, $s2));
}

Есть ли способ избежать необходимости конвертировать между скалярным типом и массивом (полагаясь на join и split)?И если да, то какой метод более эффективен?

Answer 1

Ну, я нашел способ, который более чем в 30 раз быстрее, хотя, возможно, это обман. Я включил код Benchmark.pm для его тестирования, так как вы, очевидно, не знакомы с ним.

Точка отсчета:

           Rate  Join Cheat
Join    83294/s    --  -97%
Cheat 2580687/s 2998%    --

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

use v5.14;
use Benchmark qw(cmpthese);
use Inline 'C';

sub an_join {
    my ($s1, $s2) = @_;
    return (join '', sort split(//, $s1)) eq
        (join '', sort split(//, $s2));
}

use constant {
    STR1 => 'abcdefghijklm',
    STR2 => 'abcdefghijkmm',
    STR3 => 'abcdefghijkml',
};

cmpthese(
    0,
    {
        'Join'  => 'an_join(STR1, STR2);  an_join(STR1, STR3)',
        'Cheat' => 'an_cheat(STR1, STR2); an_cheat(STR1, STR3)',
    });

__END__
__C__

int an_cheat(const char *a, const char *b) {
    unsigned char vec_a[26], vec_b[26];
    const char *p, *end;

    memset(vec_a, 0, sizeof(vec_a));
    memset(vec_b, 0, sizeof(vec_b));

    end = a+strlen(a);
    for (p = a; p < end; ++p)
        if (*p >= 'a' && *p <= 'z')
            ++vec_a[(*p)-'a'];
    end = b+strlen(b);
    for (p = b; p < end; ++p)
        if (*p >= 'a' && *p <= 'z')
            ++vec_b[(*p)-'a'];

    return 0 == memcmp(vec_a, vec_b, sizeof(vec_a));
}

Конечно, это обман, потому что он написан не на Perl, а на C. Кроме того, у него есть ограничения, которых нет у версии Perl (работает только с символами ASCII в нижнем регистре, которые являются наиболее значимыми - он просто игнорирует все остальное). Но если вам действительно нужна скорость, вы можете использовать обман таким образом.

редактирование:

Распространение на все Latin1 (ну, на самом деле, сырые 8-битные символы). Кроме того, я обнаружил, что компилятору удалось оптимизировать более простой цикл (без точечной арифметики), и его тоже легче читать, поэтому ... Бенчмарк говорит мне, что версия только для ASCII в нижнем регистре примерно на 10% быстрее:

int an_cheat_l1b(const char *a, const char *b) {
    unsigned char vec_a[UCHAR_MAX], vec_b[UCHAR_MAX];
    size_t len, i;

    memset(vec_a, 0, sizeof(vec_a));
    memset(vec_b, 0, sizeof(vec_b));

    len = strlen(a);
    for (i = 0; i < len; ++i)
        ++vec_a[((const unsigned char *)(a))[i]];
    len = strlen(b);
    for (i = 0; i < len; ++i)
        ++vec_b[((const unsigned char *)(b))[i]];

    return 0 == memcmp(vec_a, vec_b, sizeof(vec_a));
}

Обратите внимание, что преимущество версии C увеличивается по мере того, как строка становится длиннее - что ожидается, поскольку ее Θ (n) в отличие от версий Perl O (n · logn). Также уменьшается штраф за полную Latin1, что означает, что штраф, вероятно, является memcmp.

Answer 2

Я подумал, что использование умных совпадений для сравнения массивов без необходимости воссоздания строки будет иметь шанс превзойти метод OP

sub anagram_smatch {
    return [sort split//,$_[0]] ~~ [sort split//,$_[1]];
}

, но тесты не подтверждают это.

         Rate smatch   join
smatch 1.73/s     --   -54%
join   3.72/s   116%     --

Answer 3

Есть ли способ избежать преобразования между скалярным типом и массивом (полагаясь на join и split)?И если так, какой метод более эффективен?

Поскольку вы задаете их как два отдельных вопроса, я отвечу на оба.

Да, есть способы сделать это без созданиямассив @ или % хэш или еще много чего, и я обрисую некоторые из них;но ваш способ более эффективен, чем любой из них.

Один из способов - трактовать строку как массив символов, используя функцию substr ($c = substr $s, 4, 1 устанавливает $cк пятому элементу $s, а substr($s, 4, 1) = $c устанавливает пятый элемент $s в $c) и реализует на нем любой типичный алгоритм сортировки.

В качестве альтернативы, я уверен,мог бы реализовать сортировку по пузырям, используя только регулярные выражения с /e.

Наконец, если вы готовы отказаться от подхода сортировки и сравнения, вы можете написать:

sub anagram
{
    my ($s1, $s2) = @_;
    while($s1 =~ m/\G(.)/s)
      { $s2 =~ s/\Q$1// or return ''; }
    return $s2 eq '';
}

Но, опять же, split -по- join более эффективен, чем любой из них.

Answer 4

Если обе строки переменные, я не думаю, что вы можете сделать намного лучше. Один из вариантов - создать хеш, который сопоставляет символы с их количеством, а затем сравнить, что хеши имеют одинаковые ключи и значения. Я полагаю, что это O (n) вместо O (n log n) для вашего подхода, но это, вероятно, будет иметь худшую фактическую производительность, за исключением очень длинных строк.

Если вы хотите сравнить переменные строки с фиксированной ссылочной строкой, то, возможно, подход, основанный на хэше, может принести дивиденды раньше, поскольку вам нужно хешировать ссылку только один раз.