二维阵列与一维阵列的性能

Question

在C中,m×n 2维阵列与长度m×n的1维阵列之间的时间和空间是否存在差异(对于m和n的大值)？使用一维数组访问元素会更快吗？

Answer 1

在C中,二维数组只是一维数组的简洁索引方案.就像一维数组一样,2D数组分配一个连续内存块,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 指出的那样,如果你经常跳行,并且行非常大,你可能会遇到很多页面错误......在这种情况下,自定义索引功能(行和列切换)可以帮助,但这样可以简单地改变您将二维数组中的哪些维度视为行,并将其视为列.

Answer 2

实际上,如果你在C中使用所谓的二维数组,编译器会为你做一维数组的映射.如果您使用一维数组并且您希望将其视为二维数组,那么您必须自己编写映射.

你唯一需要注意的是你应该逐行访问数组,因为C编译器将逐行存储你的二维数组.如果您按列访问"大"二维数组,则可能会发生页面错误.即使您使用仅支持一维数组的语言进行编程,也可以轻松地将映射写入任意数量的维度.

如果你想按行进行映射,请查看这篇维基百科文章.您的映射可以是列式的,例如FORTRAN矩阵.

Answer 3

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

然而，会产生影响的是访问顺序，因此您可能希望自己实现一些东西，以便您可以控制访问顺序。例如列优先与行优先的形式。

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