-1

以下问题是在 Microsoft 分班考试中提出的。我无法弄清楚哪个会更好。有人可以帮助我吗？

代码1：

int MAX=1000;
int a[MAX][MAX];
for(i=0;i<MAX;i++)
    for(j=0;j<MAX;j++)
        a[j][i]=i*j;

代码2：

int MAX=1000;
int a[MAX][MAX];
for(i=0;i<MAX;i++)
    for(j=0;j<MAX;j++)
        a[i][j]=i*j;

哪个是对的？

  1. 代码 1 更快
  2. 代码 2 更快
  3. 两者在 RISC 架构中是相同的
  4. 两者都差不多
4

2 回答 2

3

假设您使用的是 C/C++，代码 2 可能会更快。C/C++ 以行优先顺序存储数组，这意味着最右边维度的变化使内存地址的变化最小。多亏了这一点，CPU 缓存可以帮助提高代码的性能，并且您不必担心页面错误（代码 2 以单调顺序访问内存地址，因此一旦程序完成读取包含数据的页面之一，它将不必再查看该页面）。

于 2014-11-04T20:59:12.420 回答
2

不同之处在于它们访问内存的方式。您的数组布局如下：

row 0 - 1000 integers
row 1 - 1000 integers
etc.

现在，您的第一个循环访问a[0][0], thena[1][0]等。所以它将定位第 0 行，然后找到第 0 列，并更新它。然后它必须找到第 1 行，在该行中找到第 0 列，然后访问它。所以你最终会在所有地方访问内存——基本上是随机的。这对 CPU 缓存不利，因为它必须在每次内存访问时重新加载。

您的第二个循环访问a[0][0], then a[0][1], thena[0][2]等。因此它定位第 0 行，然后按顺序访问列。这对处理器缓存有好处，并且会执行得更快，因为它不必经常重新加载。

于 2014-11-04T20:59:46.127 回答