将二维数组表示为一维数组

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

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

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

它将表示为:

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

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

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

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

谢谢 :)

编辑语言是C

看看二维数组的性能与一维数组

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

  (x,y) 

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

 i=y*W + x 

在1-Darrays中。 类似地,您可以使用逆映射:

 y = i / W x = i % W 

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

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

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

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

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

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

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

对于每个系统来说,使用什么类型是不同的,因此如果没有关于您正在使用的信息的信息,那么实际上无法确定。 我建议只测试性能,如果它对你真的很重要的话。 如果表现不那么重要,那么不要担心。

对于C,2Darrays是具有语法糖的一维arrays,因此性能相同。

您没有提到这是关于哪种语言或如何实现2Darrays。 在C中,2D数组实际上是作为一维数组实现的,其中C自动对索引执行算术以访问正确的元素。 所以它会做你的朋友在幕后做的事情。

在其他语言中,2d数组可能是指向内部数组的指针数组,在这种情况下,访问元素将是数组查找+指针解除引用+数组查找,这可能比索引算法慢,尽管它不值得优化除非你知道这是一个瓶颈。

 oneD_index = 3 * y + x; 

其中x是行内的位置,y是列中的位置。 而不是3,你使用你的列宽。 这样,您可以将2D坐标转换为1D坐标。