4

同じ長さの 2 つの文字列が何文字異なるかを調べたいと思います。xoring アルゴリズムが最も高速であると考えられていることがわかりましたが、それらはビットで表された距離を返します。結果を文字で表現したい。"pet" と "pit" の距離は 1 文字で表現されているが、'e' と 'i' は 2 つの異なるビットを持つ可能性があるため、xoring は 2 を返すとします。

私が書いた関数は次のとおりです。

// na = length of both strings
unsigned int HammingDistance(const char* a, unsigned int na, const char* b) {

    unsigned int num_mismatches = 0;
    while (na) {
        if (*a != *b)
            ++num_mismatches;

        --na;
        ++a;
        ++b;
    }

    return num_mismatches;
}

それはもっと速くなるでしょうか？低レベルのコマンドを使用したり、別のアルゴリズムを実装したりするのでしょうか?

システム: Intel Xeon X5650 上の Gcc 4.7.2

ありがとうございました

4

4 に答える 4

1

それ以外の

if (*a != *b)
    ++num_mismatches;

これは、分岐を回避するため、一部のアーキテクチャ (8 ビット バイト) では高速になります。

int bits = *a ^ *b;
bits |= bits >> 4;
bits |= bits >> 2;
bits |= bits >> 1;
num_mismatches += bits & 1;
于 2013-04-13T12:56:29.293 に答える
1

ネイティブの整数サイズに対してビット単位の演算子を実行することで、一度により多くのバイトを比較することができます。

コードでは、一度に 1 バイトの等価性を比較していますが、CPU は 1 サイクルで少なくとも 1 ワード、x86-64 の場合は 8 バイトを比較できます。もちろん、正確なパフォーマンス能力は CPU アーキテクチャに依存します。

ただし、ストライド サイズ 8 で 2 つのポインターを通過する場合は、シナリオによっては確実に高速になる可能性があります。メインメモリから文字列を読み取る必要がある場合、実際にはメモリのロード時間がパフォーマンスを支配します。ただし、文字列が CPU キャッシュにある場合は、XOR を実行し、64 ビット値のどこでビットが変更されたかをテストすることで結果を解釈できる場合があります。

0 ではないバケットのカウントは、0x55555555 の代わりに 0x33333333 から始まる SWAR アルゴリズムのバリアントを使用して実行できます。

アルゴリズムは、適切なメモリ配置を持つ uint64_t ポインターを使用する必要があるため、操作が難しくなります。残りのバイトをカバーするプリアンブルとポストスクリプトが必要です。コードでより複雑なことを試す前に、コンパイラが出力するアセンブリを読んで、より巧妙なことをしていないかどうかを確認する必要があります。

于 2013-04-13T12:30:14.253 に答える
1

文字列が常に 32 バイトになるようにゼロでパディングされ、それらのアドレスが 16 桁で整列されている場合、次のようにすることができます: (テストもプロファイルもされていないコード)

movdqa xmm0, [a]
movdqa xmm1, [a + 16]
pcmpeqb xmm0, [b]
pcmpeqb xmm1, [b + 16]
pxor xmm2, xmm2
psadbw xmm0, xmm2
psadbw xmm1, xmm2
pextrw ax, xmm0, 0
pextrw dx, xmm1, 0
add ax, dx
movsx eax, ax
neg eax

しかし、文字列が通常小さい場合、多くの不必要な作業が行われ、速度が低下する可能性があります。ただし、文字列が通常 (ほぼ) 32 バイトの場合は、より高速になるはずです。

編集:更新されたコメントを見る前にこの回答を書きました-通常、文字列が非常に小さい場合、これはおそらくあまり良くありません. ただし、16 バイト バージョンは (おそらく) 役立つ可能性があります (条件付きで 2 回目の反復を実行します。そのための分岐は、めったに行われないため、適切に予測する必要があります)。しかし、このような短い文字列では、通常のコードに勝るものはありません。

movdqa xmm0, [a]
pxor xmm1, xmm1
pcmpeqb xmm0, [b]
psadbw xmm0, xmm1
pextrw ax, xmm0, 0
movsx eax, ax
neg eax
于 2013-04-13T15:27:35.197 に答える