java - 实现更有效的矩阵 - 使用数组数组(二维)或一维数组？

Question

当使用数组实现 Matrix 结构时，哪个更有效？使用一维数组还是数组数组 (2D)？

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

编辑:它正在使用 Java 实现

Answer 1

“高效”并不是一个包罗万象的术语。

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

int *x[9];

其中每个 "int *" 将单独分配。

二维数组(不一定是数组的数组)通常会更快(在速度方面有效)，因为它使用数学计算内存位置，而不必取消引用内存位置。我说的是结构:

int x[9][9];

形式的一维数组:

int x[81];

不太可能比等效的 2D 版本更快，因为您仍然必须在某些时候进行计算以找到正确的单元格(在您的代码中手动执行，而不是让编译器执行)。

编辑后将 Java 作为要求添加:

我相信 Java 二维数组属于数组的数组(这需要两次内存访问，而不是一维数组所需的访问)，因此具有手动索引计算的一维数组可能会更快。因此，与其声明和使用:

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

您可以通过以下方式获得更快的速度:

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

您只需要注意不要在任何地方混淆公式(即，不要无意中交换 4 和 7)。

这种速度差异是基于我认为 Java 的编码方式，所以我可能是错的(但我对此表示怀疑 :-)。对于优化问题，我的建议是，测量，不要猜测!