Perl:对字符串中的字符进行排序

Question

我有两个字符串,我想测试它们是否是彼此的字谜.

为了测试字符串A是否是字符串B的字谜,A和B的字符都被排序.如果生成的排序字符串完全匹配,则字符串A和字符串B是彼此的字谜.

我split将字符串放入字符数组中,使用Perl的sort例程,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位字符,真的).另外,我发现编译器设法优化了更简单的循环(没有点算术),并且更容易阅读,所以...... Benchmark告诉我,小写-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的惩罚也会减少,这意味着惩罚可能就是记忆.

Answer 2

如果两个字符串都是可变的，我认为你不能做得更好。一种替代方法是构建一个将字符映射到其计数的哈希，然后比较哈希是否具有相同的键和值。我相信对于您的方法来说，这是 O(n) 而不是 O(n log n)，但除了非常长的字符串之外，它的实际性能可能会更差。

如果您想将变量字符串与固定引用字符串进行比较，那么基于散列的方法可能会更早获得好处，因为您只需要对引用进行散列一次。