1

我在 Visual Studio 2010 C++ 上实现

我有两个二进制数组。例如，

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计算其参数中设置的位数。您只传入一个元素，看起来它保证为 0 或 1，因此结果（也是 0 或 1）没有用。这样做会稍微快一些：

popcnt_result += array3[i];

根据阵列的布局方式，您可能会也可能不会以__popcnt更聪明的方式使用。具体来说，如果您的数组由单字节元素组成（例如 、char、bool或int8_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

如果您的数组仅包含两个值（0或1），则汉明距离只是对应值不同的位置数。这可以使用std::inner_product标准库一次性完成。

#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 回答