arrays - 查找 2 个巨大数组之间的变化

Question

为了简单起见，我将一个非常大的二维空间映射到一个简单的位数组(实际上它大约有 20 万个成员)。

现在假设我运行一个小算法，该算法在给定中心点和半径的情况下绘制 1 的“圆”。

下面是一个示例，在左侧绘制了一个圆，在接下来的计算中，圆心向上移动了 1。

0000000        0001000
0001000        0011100
0011100    ->  0011100
0011100        0001000
0001000        0000000
0000000        0000000

现在我有这些贴图的很多层，在我计算它们之后，我需要“展平”它们(有点像 Photoshop 混合层选项)——目前我每次都在整个数组上迭代并组合整个数组- 尽管其中 95% 不会真正改变。

伪代码

for(int x = 0; x < width; x++)
   for(int y = 0; y < height; y++)
      int index = x + y * width
      result[index] = layer1[index] * layer2[index]

这是非常低效的，我需要提高我的表现。

更新:我们最终做了什么

稀疏矩阵正是我们所需要的，我们最终使用了最适合我们使用的键字典 (DOK)(动态构建每一层并“混合” “他们在一起)。

我们想到的解决方案是使用 3 个数组:

1. float 数组大小为我们可能拥有的最大成员数(值)
2. 位数组(大小相同)，标记值数组中哪个成员有效
3. int 数组(相同大小)，保存值数组中使用的索引(稍后迭代它)+ 增量 int，用作指向索引数组中成员数量的指针

由于我们的需求严重依赖于内存使用和 CPU，我们将每个稀疏矩阵包装在双缓冲区形式中，以免每次混合都生成新数组。

最终，这个解决方案在 CPU 方面(比我们以前的简单暴力方法)给了我们大约 x15-x20 更好的结果，在内存方面，我们将 RAM 使用率降低了大约 98%。

Answer 1

据我了解，并使用 photoshop 图层类比:

您有底层“图像”，存储为“密集”二维数组，当然，因为这是您的数据，所以每个“像素”都很重要。到目前为止一切顺利。

额外的层代表小变化:当表示为二维数组时，几乎所有其条目都将为零。

在这种情况下，您需要查看稀疏矩阵表示:您无需存储完整的二维数组，而只需存储元组列表[(i1,j1), (i1 , j2), ..., ] 记录非零单元格的坐标。

这样一来，任何对这些矩阵进行运算的算法都将按照非零元素的数量顺序运行，而不是基于矩阵的总条目数量。