将2D阵列表示为1D阵列

Question

可能重复:
使用阵列数组(2D)或1D数组实现更高效的矩阵？
二维阵列与一维阵列的性能

前几天我正在查看我的伙伴的分子动力学代码库之一,他将一些2D数据表示为一维数组.因此,他不必使用两个索引,而只需要跟踪一个索引,但只需要进行一些数学计算就可以确定它是2D的位置.所以在这个2D数组的情况下:

two_D = [[0, 1, 2],
         [3, 4, 5]]

它将表示为:

one_D = [0, 1, 2, 3, 4, 5]

如果他需要知道2D阵列的位置(1,1),他会做一些简单的代数并得到4.

使用1D阵列而不是2D阵列是否有任何性能提升.在计算过程中,数组中的数据可以被调用数百万次.

我希望数据结构的解释清楚......如果不让我知道,我会尝试更好地解释它.

谢谢 :)

编辑语言是C

Answer 1

对于宽度为W且高度为H的二维数组,您可以将其表示为长度为W*H的一维数组,其中每个索引

 (x,y)

其中x是列,y是行,2-d数组映射到索引

i=y*W + x

在1-D阵列中.类似地,您可以使用逆映射:

y = i / W
x = i % W

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

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

这种优化仅限于W是2的幂的情况.编译器很可能会错过这种微优化,因此您必须自己实现它.

模数是C/C++中的慢运算符,因此使其消失是有利的.

此外,对于大型2-d阵列,请记住,计算机将它们作为1-d阵列存储在内存中,并且基本上使用上面列出的映射来计算索引.

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

Answer 2