问将2D数组表示为一维数组

EN

看看Performance of 2-dimensional array vs 1-dimensional array

对于宽W和高度H的二维数组，可以将其表示为长度为W*H的一维数组，其中每个索引都可以表示。

 (x,y)

其中x是列，y是行，其中二维数组映射到索引。

i=y*W + x

在一维数组中。类似地，您可以使用逆映射：

y = i / W
x = i % W

。如果你使W的幂为2 (W=2^m)，你可以使用这个黑客

y = i >> m;
x = (i & (W-1))

如果这个优化只限于W是2的幂，编译器很可能会错过这个微优化，所以你必须自己实现它。

模在C/C++中是一个慢算子，因此使它消失是有利的。

此外，对于大型的二维数组，请记住，计算机将它们作为一维数组存储在内存中，并且基本上使用上面列出的映射来计算索引。

比确定这些映射的方式更重要的是如何访问数组。有两种方法可以做到这一点:列专业和行专业。您遍历的方式是，它比任何其他因素都更重要，因为它决定了您是否使用缓存对您有利。请阅读http://en.wikipedia.org/wiki/Row-major_order。

通常，2D数组被实现为一维数组。有时2D数组是由指向一维数组的指针组成的一维数组实现的。与一维数组相比，第一种情况显然没有性能损失，因为它与一维数组相同。第二种情况可能会有轻微的性能损失，这是由于额外的间接影响(以及其他一些微妙的影响，比如缓存局部性降低)。

对于不同的系统，使用的是哪种，所以如果没有关于您正在使用的信息，就无法确定。如果对你来说真的很重要的话，我建议你测试一下它的性能。如果表演没那么重要，那就别担心。

对于C，2D数组是具有语法糖的一维数组，因此性能是相同的。