什么是计算大型连续数组中零值字节数的快速方法？ (或者相反,非零字节的数量.)大,我的意思是216字节或更大.数组的位置和长度可以包含任何字节对齐.
天真的方式：
int countZeroBytes(byte[] values,int length)
{
int zeroCount = 0;
for (int i = 0; i < length; ++i)
if (!values[i])
++zeroCount;
return zeroCount;
}
对于我的问题,我通常只维护zeroCount并根据值的特定更改来更新它.但是,我希望在对值进行任意批量更改之后,有一种快速,通用的方法来重新计算zeroCount.我确信有一种比较快速的方法可以更快地实现这一点,但是,唉,我只是一个新手twiddler.
编辑：有些人询问数据的性质是零检查,所以我将描述它. (不过,如果解决方案仍然普遍,那就太好了.)
基本上,设想由voxels(例如Minecraft)组成的世界,其中程序生成的地形被分隔成立方块,或者有效地将页面索引为三维阵列.每个体素被飞加权作为对应于独特材料(空气,石头,水等)的唯一字节.许多块仅包含空气或水,而其他块包含大量2-4种体素(污垢,沙子等)的不同组合,有效地2-10％的体素是随机异常值.大量存在的体素往往沿着每个轴高度聚集.
解决方法
我已经使用了这个OpenMP实现,它可以利用每个处理器的本地缓存中的数组实际并行读取它.
nzeros_total = 0;
#pragma omp parallel for reduction(+:nzeros_total)
for (i=0;i<NDATA;i++)
{
if (v[i]==0)
nzeros_total++;
}
一个快速的基准测试,包括运行1000次for循环和一个朴素的实现(与问题中写的OP相同)与OpenMP实现相比,运行1000次,两个方法的最佳时间,数组为65536具有零值元素概率为50％的整数,在QuadCore cpu上使用Windows 7,并使用VStudio 2012 Ultimate编译,产生以下数字：
DEBUG RELEASE Naive method: 580 microseconds. 341 microseconds. OpenMP method: 159 microseconds. 99 microseconds.
注意：我已经尝试了#pragma循环(hint_parallel(4))但是显然,这并没有导致天真版本执行得更好所以我的猜测是编译器已经应用了这个优化,或者它不能适用.此外,#pragma loop(no_vector)并没有导致天真版本的性能更差.
