c++ - 位图算法

Question

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

计时器在固定时间对网格进行采样，以查找标记为脏且需要处理的单元格。

启动处理的开销，称为函数 P() 需要很长时间来引导。P 可以采用一维数组，例如水平或垂直的扫描线。

问题是如何设计一种有效的算法，可以将二维网格上的任意一组脏位“分块”成扫描线，以最大限度地减少调用 P() 的次数？

Answer 1

您可以研究前缀和算法的变体，以并行快速扫描位图，隔离脏块，并将指向这些脏块的指针打包到可以传递给P()函数的新数组或“扫描线”中。

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