12

使用数组实现 Matrix 构造时，哪个更有效？使用一维数组还是数组数组（二维）？

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

编辑：它正在使用 Java 实现

4

6 回答 6

13

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

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

int *x[9];

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

二维数组（不一定是数组数组）通常会更快（在速度方面效率更高），因为它可以通过数学计算内存位置，而无需取消引用内存位置。我说的是构造：

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 在幕后编码的方式，所以我可能是错的（但我对此表示怀疑 :-)。我的建议是，一如既往地优化问题，衡量，不要猜测！

于 2009-04-09T03:39:01.997 回答
4

我将用迄今为止的答案打破排名，并提出以下原因，即一维数组很可能更快。

二维数组涉及 2 次内存访问。例如，A[x][y] 首先必须查找 A[x]，然后再查找该数组 [y]。

一维实现传统上是 A[x + (width *y)]。当宽度在寄存器（或文字）中时，这意味着 2 个数学运算和 1 个查找而不是 2 个查找。查找比数学运算慢几个数量级，所以如果宽度在寄存器中的比例很小，或者是文字，它会更快。

当然，标准警告适用。始终分析并避免过早的优化。

于 2009-04-09T04:02:02.767 回答
2

如果不实际编写示例代码并测试结果，我认为无法回答这个问题。例如这个问题发现了以下结果。

sum(double[], int): 2738 ms (100%)
sum(double[,]):     5019 ms (183%)
sum(double[][]):    2540 ms ( 93%)

锯齿状数组最快，其次是一维数组，其次是多维数组。锯齿状阵列最快可能不是人们所预料的。这些结果可能对 Java 毫无用处，因为 Java 有不同的优化（Java 中没有多维数组）。

我会非常小心地做出假设。 例如，如果您在 2D 数组的一行上循环，Java 可能会优化索引查找或越界检查，如果您使用具有内联索引计算的 1D 数组，Java 可能无法做到这一点。

我建议编写一个简单的程序来测试所需平台上的速度。

于 2009-04-09T04:19:50.027 回答
1

根据语言的不同，不会有任何区别。真正的问题是如何分配二维矩阵。它是 X*Y 字节的单个连续空间，还是分配为 X 大小的 Y 独立数组。后者通常在创建稀疏矩阵时完成。

于 2009-04-09T03:40:39.497 回答
0

我在作为机械工程师的职业生涯中使用的商业有限元包，它使用一维数组作为其线性代数计算的基础。有限元方法导致矩阵大、稀疏和带状。将所有这些零元素存储在带外是没有意义的。

唯一一次您会看到二维数组用于小型学术问题或不稀疏的问题（例如，边界元素方法）。

于 2009-04-09T09:57:35.673 回答
0

在一般情况下，任何算法的最有效实现是具有最少代码量的算法。这有很多原因：

  • 更少的代码 -> 更少的编写时间
  • 更少的代码行意味着更少的错误（因为每个 KLOC 的错误对于给定的程序员来说是相当稳定的），更容易找到（因为它们不能很好地隐藏在几行代码中）
  • 如果您的算法不适合该任务，那么当它是 10 行而不是 100 行时更容易替换
  • 一个紧凑的实现通常会导致干净的接口，这使得使用库的代码干净（因此效果成倍增加）。这也可能导致更复杂的库实现，如果这使客户端代码更高效（即您将精力集中在一个地方以使其他一切更简单）。

它还很大程度上取决于访问模式。你总是走整个矩阵吗？稀疏吗？您喜欢处理行还是列？

在极端情况下（具有 10 亿行和列的矩阵，仅使用 10 个单元格），aHashMap可以比任何数组实现更有效。对于其他问题，根据问题混合方法可能更有效（例如，HashMap当单元格“聚集”在巨大的空白空间中时，一组迷你矩阵）。

如果您的问题要求定位行/列然后处理这些值，则使用 2D 方法可能更有效，因此第一次访问会返回一个数组，然后您可以处理该数组而无需担心边界、一次性错误、等等

于 2009-04-09T10:57:59.257 回答