Perl：文字列内の文字を並べ替える

Question

私は2つの文字列を持っており、それらが互いにアナグラムであるかどうかテストしたいと思います。

文字列Aが文字列Bのアナグラムであるかどうかをテストするには、AとBの文字を両方ともソートします。結果のソートされた文字列が正確に一致する場合、文字列Aと文字列Bはお互いのアナグラムです。

私はsplitjoinが戻って一緒に文字をINGの、Perlのsortルーチンを使用して、アップ文字配列に文字列をするのです、と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

両方の文字列が可変であれば、私はあなたがもっとうまくいくとは思わない。 1つの方法は、文字をカウントにマップするハッシュを作成し、ハッシュが同じキーと値を持つことを比較することです。私はあなたのアプローチではO（n log n）の代わりにこれがO（n）だと信じていますが、非常に長い文字列を除いて実際のパフォーマンスは悪くなるでしょう。

可変文字列を固定参照文字列と比較したい場合は、ハッシュベースのアプローチでは、参照を一度ハッシュするだけで済むため、より早く配当を支払う可能性があります。

Answer 2

（joinとsplitに依存して）スカラー型と配列型の間の変換を避ける方法はありますか？もしそうなら、どの方法がより効率的ですか？

あなたはこれらを2つの別々の質問として尋ねるので、私は両方に答えます。

はい、@アレイを作成せずに、または%ハッシュまたはその他のものを作成せずにこれを行う方法があります。あなたの方法はこれらのどれよりも効率的です。

一つの方法は、the substr function用いて文字の配列として文字列を扱うことである（$sの第5要素に$c = substr $s, 4, 1セット$c、およびsubstr($s, 4, 1) = $cは$s$cへの5番目の要素を設定し）、その上の任意の典型的なソートアルゴリズムを実装します。

また、/eの正規表現置換を使用してバブルソートを実装できることは間違いありません。

最後に、あなたはソート当時の比較アプローチを省くために喜んでいる場合は、あなたが書くことができる：

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

しかし、再び、split -then- joinは、これらのいずれかよりも効率的です。

Answer 3

私は、文字列は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 4

私は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文字でのみ動作し、他のすべての文字は無視されます）。しかし、本当にスピードが必要な場合は、このような不正行為を使用することができます。

編集：

は（本当に、よく、生の8ビット文字）のLatin1のすべてに拡張します。また、コンパイラが単純なループ（ポイント演算なし）を最適化し、読みやすくすることができたことがわかりました。ベンチマークでは、小文字の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バージョンの利点は、PerlバージョンO（n・logn）とは対照的に、Θ（n）以降の文字列が長くなるにつれて長くなることに注意してください。また、完全なLatin1のペナルティは減少します。ペナルティはおそらくmemcmpです。