1

Visual Studio 2010C++に実装しています

2つのバイナリ配列があります。例えば、

array1[100] = {1,0,1,0,0,1,1, .... }
array2[100] = {0,0,1,1,1,0,1, .... }

との間のハミング距離を計算するには、との結果を格納 します。array1array2array3[100]xorarray1array2

1次に、のビット数を数える必要がありますarray3。これを行うために、私は__popcnt命令を使用できることを知っています。

今のところ、私は以下のようなことをしています：

popcnt_result = 0;
for (i=0; i<100; i++) {
    popcnt_result = popcnt_result + __popcnt(array3[i]);
}

良い結果を示していますが、遅いです。どうすれば速くできますか？

4

3 に答える 3

3

array3少し無駄に思えます。必要のない余分な 400 バイトのメモリ全体にアクセスしています。私はあなたが持っているものを次のものと比較してみます：

for (int i = 0; i < 100; ++i) {
    result += (array1[i] ^ array2[i]);   // could also try != in place of ^
}

それが少しでも役立つなら、この変更とダスクワフの両方をどのように適用するかは、読者の演習として残しておきます。

于 2012-07-05T02:02:02.597 に答える
2

実装されているように、__popcnt呼び出しは役に立ちません。それは実際にあなたを遅くしています。

__popcnt引数のセットビット数をカウントします。1つの要素のみを渡していますが、これは0または1であることが保証されているように見えるため、結果（0または1も）は役に立ちません。これを行うと少し速くなります：

popcnt_result += array3[i];

アレイのレイアウトによっては__popcnt、賢い方法で使用できる場合とできない場合があります。具体的にはchar、配列が1バイトの要素（たとえば、、、、など）で構成されている場合、一度に4つの要素に対して人口カウントを実行できます。boolint8_t

for(i = 0; i < 100; i += 4) {
    uint32_t *p = (uint32_t *) &array3[i];
    popcnt_result += __popcnt(*p);
}

（これは、100が4で均等に割り切れるという事実に依存することに注意してください。そうでない場合は、最後のいくつかの要素に特別な場合の処理​​を追加する必要があります。）

ただし、配列がなどのより大きな値で構成されている場合はint、運が悪く、これが上記の単純な実装よりも高速であるという保証はありません。

于 2012-07-05T01:13:24.310 に答える
1

配列に 2 つの値 (0または1) しか含まれていない場合、ハミング距離は、対応する値が異なる位置の数にすぎません。std::inner_productこれは、標準ライブラリを使用して 1 回のパスで実行できます。

#include <iostream>
#include <functional>
#include <numeric>

int main()
{
    int array1[100] = { 1,0,1,0,0,1,1, ... };
    int array2[100] = { 0,0,1,1,1,0,1, ... };

    int distance = std::inner_product(array1, array1 + 100, array2, 0, std::plus<int>(), std::not_equal_to<int>());

    std::cout << "distance=" << distance << '\n';

    return 0;
}
于 2012-07-05T12:10:41.520 に答える