将二维数组表示为一维数组[重复]

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

对于宽度w和高度h的二维数组,可以将其表示为长度w*h的一维数组,其中每个索引

 (x,y)

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

i=y*W + x

在一维数组中。同样,您可以使用反向映射:

y = i / W
x = i % W

.如果使w的幂为2(w=2^m),则可以使用hack

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

其中,该优化仅限于w为2的幂的情况。编译器很可能会错过这种微优化,因此您必须自己实现它。

模数是C/C++中的一个慢运算符,所以使其消失是有利的。

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

比确定这些映射的方法更重要的是如何访问数组。有两种方法可以做到这一点:列主要和行主要。你穿过的方式是 更重要 因为它决定了你是否使用 高速缓存 对你有利。请阅读 http://en.wikipedia.org/wiki/Row-major_order .

通常,二维数组实现为一维数组。有时,二维数组由指向一维数组的一维指针数组实现。与一维数组相比,第一种情况显然没有性能损失,因为它与一维数组相同。第二种情况可能会由于额外的间接性(以及其他一些细微的影响,如缓存位置的降低)而有轻微的性能损失。

对于每个系统,使用的是什么类型是不同的,因此如果没有关于您正在使用什么的信息,就没有办法确定。如果这对你真的很重要,我建议你只测试一下性能。如果表演不那么重要,那就不用担心了。

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

您没有提到与此相关的语言或如何实现二维数组。在C中,二维数组实际上实现为一维数组,其中C自动对索引执行算术运算,以访问正确的元素。所以它会像你朋友在幕后所做的那样。

在其他语言中,二维数组可能是指向内部数组的指针数组,在这种情况下,访问元素将是数组查找+指针取消引用+数组查找,这可能比索引算法慢,但除非您知道这是一个瓶颈,否则不值得优化。

oneD_index = 3 * y + x;

其中x是行中的位置,y是列中的位置。用列宽代替3。这样可以将二维坐标转换为一维坐标。