java - 二维数组迭代方法比其他方法更快

Question

我知道结果是相同的，但第一个循环比第二个循环更快。这是为什么？

int[][] values = new int[10][20];

int sum = 0;
int count = 0;
for (int j = 0; j < 20; j++) {

    for (int i = 0; i < 10; i++) {
        count++;
        values[i][j] = count;

        sum += values[i][j];
    }

}
System.out.println(sum);

<小时/>

int[][] values = new int[10][20];

int sum = 0;
int count = 0;
for (int i = 0; i < 10; i++) {

    for (int j = 0; j < 20; j++) {
        count++;
        values[i][j] = count;

        sum += values[i][j];
    }

}
System.out.println(sum);

Answer 1

这是一个loop interchange .

虽然我无法观察到与您的机器完全相同的结果(我的机器使用 Intel i7-4770K 非常强大，并且代码非常简单我用于解决 Stack Overflow 问题的类)，一般来说，这种循环具有性能更高的倾向。

它性能更高的主要原因是它迭代的元素的局部性。迭代连续内存比非连续内存更有效。

让我们考虑一个典型的数组:

int[] anArray = new int[5];

在内存中，Java 将保留* 5 个能够容纳 int 的连续 block 。

int[5] -> [][][][][]

^{*:或者至少尝试一下。}

对于二维数组，Java 将执行相同的操作，但要注意的是，它不会像内存中的网格(如 C 那样)，而是会拥有一个指向数组的数组。

int[2][3] -> [ ] [ ]
              |   |
              v   v
             [ ] [ ]
             [ ] [ ]
             [ ] [ ]

就内存布局而言，第二层数组(即长度为 20 的数组)在内存中可能比第一层数组(即长度为 10 的数组)彼此更接近。迭代连续内存比迭代非连续内存更有效，这就是您注意到速度提高的原因。