二维数组与一维数组的性能对比 [英] Performance of 2-dimensional array vs 1-dimensional array

问题描述

在 C 语言中，m×n 二维数组与长度为 m×n 的一维数组(对于较大的 m 和 n 值)在时间和空间上是否存在差异?使用一维数组访问元素会更快吗?

In C, is there a difference in time and space between an m×n 2-dimensional array vs a 1-dimensional array of length m×n (for large values of m and n)? Will accessing elements be faster with a 1-dimensional array?

推荐答案

在 C 中，二维数组只是一维数组的简洁索引方案.就像一维数组一样，二维数组分配一块连续的内存，A[row][col] 表示法类似于 A[row*NCOLS+col].

In C, 2-dimensional arrays are just a neat indexing scheme for 1-dimensional arrays. Just like with a 1D array, 2D arrays allocate a single block of contiguous memory, and the A[row][col] notation is similar to saying A[row*NCOLS+col].

通常，如果您要使用一维数组实现自己的多维数组，则会编写一个索引函数:

Usually if you were to implement your own multidimensional arrays using single dimensional arrays, you'd write an indexing function:

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

假设您的编译器内联了这个函数，这里的性能将与您使用二维数组的内置索引函数"完全相同.

Assuming your compiler inlines this function, the performance here would be precisely the same as if you used the built in 'indexing function' of 2D arrays.

举例说明:

#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 指出，如果你经常跳来跳去的行，并且行非常大，你可能会遇到很多页面错误......在这种情况下，自定义索引功能(行和列切换)可能帮助，但也可以简单地更改二维数组中的哪些维度，您将其视为行，将哪些维度视为列.

Though as AraK pointed out, if you are jumping around rows a lot, and the rows are very large, you could hit a lot of page faults... in that case the custom indexing function (with rows and cols switched around) could help, but so could simply changing which of the dimensions in a 2-dimensional array you treat as the rows and which you treat as the columns.

这篇关于二维数组与一维数组的性能对比的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！