二进制数组的Fast Popcount指令或汉明距离？

我在Visual Studio 2010上实现C++二进制数组的Fast Popcount指令或汉明距离？

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

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

为了计算和的array1和array2的xor结果Hamming distance之间array1array2， array3[100]商店。

然后我必须计算array3中的1位的数量。要做到这一点，我知道我可以使用__popcnt指令。

现在，我在做类似如下：

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

它显示了一个很好的结果，但速度很慢。我怎样才能让它更快？

来源

2012-07-05 user1498253

是int'的'这些阵列？它们只包含的值'0'或'1'？ – Blastfurnace

是否可以用1位（而不是字节）表示每个“数组条目”？ – reuben

@Blastfurnace是的，我有二进制整数数组，所以只有0或1 – user1498253

在实施时，__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-05 01:13:24 duskwuff

建议的更改不会违反严格的别名？ – Voo

是的，它确实 - 它做的事情基本上是“icky”，所以我不相信它有任何方法。 – duskwuff

单程就是'uint32_t u; memcpy（＆u，array3 + i，sizeof u）;'，然后检查优化器是否足够聪明以消除'u'，并将数组中的4个字节加载到用于计费的寄存器中。我不知道MSVC是否是，但是因为你没有违反严格的别名，它不会做任何刺激的事情，就像在循环之前切换'array'一样，因为它认为它没有被使用，并且使用内存来寻找别的东西。请注意，我也不知道MSVC是否足够聪明，可以在违反严格别名的情况下做任何让人讨厌的事情...... –

array3看起来有点浪费，你正在访问你不需要的整个额外的400字节的内存。我想尝试比较你有以下几点：

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

有没有什么帮助的话，那么我把它作为一个练习留给读者如何应用这两种变化和 duskwuff的。

来源

2012-07-05 02:02:02

并让循环展开游戏开始真正挤出这个算法的最后一个表现:-) – TemplateRex

如果您的阵列只包含两个值（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-05 12:10:41 Blastfurnace

二进制数组的Fast Popcount指令或汉明距离？

回答

相关问题