实现矩阵更有效-使用数组数组（2D）还是一维数组？

Question

使用数组实现Matrix构造时，哪一种效率更高？使用1D阵列还是2D阵列？

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

编辑：正在使用Java实现

Answer 1

“高效”不是万能的。

就存储可能稀疏的数组而言，数组数组解决方案效率更高（即，您可以使用空指针表示全零的矩阵行）。这将是（在C中）：

int *x[9];

每个都"int *"将单独分配。

2D数组（不一定是数组的数组）通常会更快（就速度而言是有效的），因为它可以用数学方法计算出存储位置，而不必取消对存储位置的引用。我说的是构造：

int x[9][9];

一维数组的形式为：

int x[81];

它不可能比等效的2D版本快，因为您仍然必须在某个时候进行计算才能找到正确的单元格（通常在代码中手动进行，而不是让编译器来完成）。

编辑后添加Java的要求：

我相信Java 2D数组属于各种数组数组（与1D数组相比，将需要两次内存访问），因此带有手动索引计算的1D数组可能会更快。因此，与其声明和使用：

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

您可能会提高速度：

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

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

这种速度差异是基于我认为Java是如何编码的，所以我可能是错的（但我对此表示怀疑：-）。我的建议是，一如既往地对优化问题进行 衡量，不要猜测！