c - 哪段代码效率更高？

Question

为了初始化 100×100 二维数组的所有元素，我们可以通过两种方式进行：

方法一：

int a[100][100];
for(i=0; i<100; i++){
    for(j=0; j<100; j++){
        a[i][j] = 10;
    }
}

方法二：

int a[100][100];
for(j=0; j<100; j++){
    for(i=0; i<100; i++){
        a[i][j] = 10;
    }
}

现在我的问题是哪种方法更有效，为什么？

score 8 · Accepted Answer

第一种方法，因为它将按顺序访问数组。

C 以行优先顺序存储二维数组，这意味着 a[i][j] 将与 a[i][j+1] 相邻，但不与 a[i+1][j] 相邻。

说同样事情的另一种方式（推广到> 2维）是最右边的索引在内存中是相邻的。或者，增加索引意味着您必须跳过要增加的索引右侧的所有维度。

score 2 · Accepted Answer

C11 标准，第6.5.2.1.3 节指示数组存储为row-major。这意味着第一种方法是顺序访问内存，而第二种方法不是。根据您的 CPU 的缓存机制、RAM 访问机制和数组的尺寸，两者都可能更快。一般来说，我会说第一种方法更快。

score 1 · Accepted Answer

我怀疑两个循环的速度相同，实际上生成的代码是相同的。除非数组是易失的，否则编译器可以自由切换循环，并且应该将它们切换到对目标机器更好的顺序。

score 1 · Accepted Answer

当你声明一个像它的内存一样的数组时，int a[100][100]它的布局与你声明的一样，int a[10000]这意味着如果你只在 a 上迭代，你就可以连续访问所有单元格。

该标准表明该数组是按行存储的，这意味着您在内存中的前一百个单元格将是a[0][0]toa[0][99]然后a[1][0]to a[1][99]。

在大多数 CPU 上，第一种方法会更快，因为 CPU 能够将（大部分）阵列加载到 CPU 缓存中，因此可以快速访问它。请注意，这可能在不同的 CPU 之间有所不同。

score 0 · Accepted Answer

这取决于您使用的语言是行优先还是列优先。内存中的任何内容始终以一维方式布局，因此所有 2D 内容也以 1D 方式转换。现在请注意，有两种方法可以做到这一点。

所以这里第一个是将二维数组转换为一维方式的行主要方式，第二个是列主要方式。像 C/C++ 这样的语言是行优先的，所以它们遵循第一种方式。

现在观察第一种方式，根据行中元素的数量，您的点 (0,0) 和 (1,0) 非常非常远，但是 (0,0) 和 (0,1) 是相邻的.

因此，作为最终答案，您的问题取决于编程语言，它是行主要编程语言还是列主要编程语言。在 C/C++ 中，因为它们是行优先的，所以第一个会更快。

5 回答 5