位映射算法

Question

该数据集是一个2维网格。从实时源更新网格的频率非常高，但处理这些数据需要很长时间。

定时器对固定时间的网格进行采样，以标记脏的单元格并需要处理。

开始处理的开销，调用它的函数P（）需要很长时间来引导。 P可以采用1维阵列，例如水平或垂直扫描线。

问题是如何设计一个高效的算法，可以将2D网格上的任意脏位比特集合成扫描线，以最小化P（）被调用的次数？

Answer 1

您可以查看prefix sum算法的变体，以快速扫描并行位图，隔离脏块，并将指向那些脏块的指针打包成新数组或可以传递给的“扫描行”您的P()功能。

例如，使用并行线程，在脏数据块的值为1且非脏数据块的值为0的二维数组上执行前缀求和。在完成前缀总和后，所有脏块将从1....N开始向上计数。现在，使用一组并行线程，将编号为脏数据块的指针复制或创建到新的“扫描线”数组中......来自前缀和的值将成为扫描行数组中每个脏数据块的基本散列值块应该从中引用。