使用阵列数组(2D)或一维数组实现更高效的矩阵？

Question

使用数组实现Matrix构造时,效率会更高吗？使用1D数组还是数组数组(2D)？

我认为2D更有效,因为您已经拥有元素的X和Y坐标,在1D实现中您必须计算索引.

编辑:它是使用Java实现的

Answer 1

"高效"并不是一个包罗万象的术语.

阵列阵列解决方案在存储方面更有效,其中阵列可能是稀疏的(即,您可以使用空指针来表示全零的矩阵线).这将是(在C中):

int *x[9];

每个人"int *"将分别分配.

2D数组(不一定是数组的数组)通常会更快(在速度方面有效),因为它可以使用数学计算出内存位置,而无需取消引用内存位置.我在谈论这个结构:

int x[9][9];

形式的一维数组:

int x[81];

因为你仍然需要在某些时候进行计算以找到正确的单元格(在代码中手动而不是让编译器这样做),因此不太可能比等效的2D版本更快.

在编辑之后添加Java作为要求:

我相信Java 2D数组具有多种数组(这将需要两次内存访问,而不是一维数组所需的内存访问),因此具有手动索引计算的一维数组可能会更快.所以,而不是声明和使用:

int x[width][height];
x[a][b] = 2;

你可以获得更快的速度:

int x[width*height];
x[a*height+b] = 2;

你只需要小心,不要让公式在任何地方混淆(即,不要无意中交换4和7).

这种速度差异是基于我认为Java在封面下的编码方式所以我可能是错的(但我怀疑它:-).我的建议是,一如既往的优化问题,衡量,不要猜!