2维数组的性能与1维数组的性能相比如何？

Question

在 C 语言中，对于大的 m 和 n 值，一个 m×n 的二维数组和一个长度为 m×n 的一维数组，在时间和空间上是否有差别？访问数组元素时，使用一维数组会更快吗？

- vishal

Answer 1

在C中，二维数组只是一维数组的便利索引方式。与一维数组类似，二维数组分配一个连续的内存块，而A[row][col]的表示方式类似于A[row*NCOLS+col]。

通常情况下，如果您要使用单个一维数组实现自己的多维数组，您需要编写一个索引函数：

int getIndex(int row, int col) { return row*NCOLS+col; }

假设您的编译器内联此函数，那么这里的性能将与使用2D数组的内置“索引函数”完全相同。

举例说明：

#define NROWS 10
#define NCOLS 20

这个：

int main(int argc, char *argv[]) {
    int myArr[NROWS*NCOLS];
    for (int i=0; i<NROWS; ++i) {
       for (int j=0; j<NCOLS; ++j) {
          myArr[getIndex(i,j)] = i+j;
       }
    }
    return 0;
}

应该与这个执行相同：

int main(int argc, char *argv[]) {
    int myArr[NROWS][NCOLS];
    for (int i=0; i<NROWS; ++i) {
       for (int j=0; j<NCOLS; ++j) {
          myArr[i][j] = i+j;
       }
    }
    return 0;
}

虽然AraK指出，如果您频繁跳转行且行非常大，则可能会遇到许多页面错误...在这种情况下，自定义索引函数（行和列交换）可能有所帮助，但只需更改将二维数组中哪个维度视为行，哪个维度视为列即可。

- David Claridge

Answer 2

实际上，如果您在C中使用所谓的二维数组，编译器会为您将其映射到一维数组中。如果您使用一维数组，并且希望将其视为二维数组，则必须自己编写映射。

唯一需要注意的是，您应该按行访问数组，因为C编译器将逐行存储您的二维数组。如果您以列方式访问“大型”二维数组，则可能会发生页错误。即使您在只支持一维数组的语言中编程，也可以轻松地将映射编写成任意维度。

如果您想进行按行映射，请查看此维基百科文章。例如，您的映射可以是按列排列的，就像FORTRAN矩阵一样。

- Khaled Alshaya

Answer 3

罗伯特是正确的，索引表达式被编译为指针算术表达式，因此没有区别。

然而，访问顺序可以影响性能，所以您可能希望自己实现来控制访问顺序。例如，列优先和行优先形式。

在现代处理器上，以各种步幅访问大型数组可能会产生意外的性能差异。顺序访问始终最快，其他步幅可能由于缓存交互而慢至多30倍。内部维度为2的幂次方的多维数组通常具有较差的性能，因为它们与缓存联想方式的交互方式不同。要理解这些问题，真正的替代品是进行测量。

- Jason Watkins

---

你无需编写自己的代码来决定布局；C内置布局已被定义得很好了。你可以通过编写 array[row][column] 或者 array[column][row] 来选择使用哪种布局。 - derobert

是的，没错。我应该给出一个更好的例子，比如针对阻塞矩阵的各种方案。 - Jason Watkins

Answer 4

我认为两者没有任何区别。在内部，C将二维数组视为多个按顺序排列的一维数组。

然而，就性能而言，实际情况可能会有所不同。可能存在某种微妙的指针算术差异。在两种情况下运行定时测试。哪种运行更快，就采用哪种。

- Robert Harvey

---

你不能在C语言中使用数组吗？例如，int **array，然后你可以使用array = malloc(sizeof(int*)*rows); for (i = 0; i < rows; ++i) { array[i] = malloc(sizeof(int) * cols); }来创建数组。这样做的好处是虽然访问和创建速度较慢，但添加行的速度更快。 - derobert

@derobert: 那个数据结构通常被称为“不规则数组”。它具有类似的语法访问方式，但并不完全相同于普通的二维数组。 - dmckee --- ex-moderator kitten

@dmckee 锯齿状的还是参差不齐的？ - M. Mimpen

Answer 5

正如其他人所说，区别在于访问项目的方式：重要的是项目在内存中的布局，这至少在常见的架构上是线性的。因此，你实际拥有的只是一个一维数组，二维等等只是“方便”，一个合理的编译器应该优化索引——但实际上，一旦你有了多个变量，编译器经常会在像x86这样的架构上由于寄存器饥饿而失败。

现在，这取决于你的应用程序，但我认为你应该默认使用一维布局，特别是如果你需要处理多个维度。C中多维数组的第一个问题是你无法动态分配它们——如果你按行分配，性能会非常差，因为你没有一个连续的内存块。有关此详细信息，请参见FFTW文档。

请注意，你始终可以在其上方使用便捷的数组索引来描述单个内存块（你分配一个大的nxm内存块，然后创建一个指向每行n指针的数组）。

- David Cournapeau

Answer 6

我只是猜测，但我认为一维数组比二维数组更快。然而，速度上的差异不会很明显。就像1000000.01美元比1000000美元多一样。

我会使用编码更容易的那个。

- dan gibson