Java 多维数组 : Memory Address and Traversal Speed

Question

我了解到，在 Java 中处理二维数组时，您在循环中访问数组元素的顺序会影响遍历数组所需的时间:

int size = 500;
int[][] array = new int[size][size];

// Slower
for (int i = 0; i < size; i++) {
    for (int j = 0; j < size; j++) {
        array[j][i] = 1;
    }
}

// Faster
for (int i = 0; i < size; i++) {
    for (int j = 0; j < size; j++) {
        array[i][j] = 1;
    }
}

这对我来说很有意义，因为它不需要在内存中跳转，而是可以直接跳转到后续地址。

当对 3 维数组执行相同操作时，我对结果有点困惑:

Time:  12356332 nanoseconds. ([i][j][k])
Time:  18278948 nanoseconds. ([i][k][j])
Time:  13985288 nanoseconds. ([j][i][k])
Time: 126192723 nanoseconds. ([j][k][i])
Time:  39441820 nanoseconds. ([k][i][j])
Time: 156352618 nanoseconds. ([k][j][i])

[i][j][k] 和 [j][i][k] 的结果在大多数代码运行中是可以互换的。这是为什么？

另外，您能否解释一下多维数组在 Java 中是如何存储的？

给定数组 int[][][] array = new int[2][2][2] 内存地址会像这样吗(我的理解是可能是每个 block 之间其他变量的附加数据，但我省略了这些情况，因为它们不相关): (抱歉，如果图像令人困惑，我只能使用绘画并尽力表达布局。所以 array[0][0][0]//[i][j ][k] 将位于地址 06)

Answer 1

首先要考虑的是，仔细观察，java 没有多维数组，因为它是一个单一的实体。相反，java 只处理单维数组，但元素类型本身可以是数组类型，并且语言/编译器支持与例如相同的语法。 C 对多个维度进行快捷寻址一个元素。

例如，int[][] twoDim = new int[50][100]; 实际上在内存中创建了 51 个对象； 一个 int[][] 类型的数组，其中包含 50 个 int[] 类型的元素，然后用一个数组填充这 50 个空间int[100] 类型(生成剩余的 50 个对象)。这 51 个对象中的每一个都是独立的，并且它们可以位于堆中的任何位置。实际上，它们甚至不需要在同一语句中创建。

以下两种方法给出相同的数组作为结果，但第二种方法应该清楚真正发生了什么在幕后:

 public int[][] createArrayA(int n, int m) {
     return new int[n][m];
 }

 public int[][] createArrayB(int n, int m) {
     int[][] array = new int[n][];
     for (int i=0; i<n; ++i)
         array[i] = new int[m];
     return array;
 }

请注意，在 createArrayB() 中，您也可以选择向后初始化 n 维(循环向下计数而不是向上计数)，从而得到相同的数组:

 public int[][] createArrayC(int n, int m) {
     int[][] array = new int[n][];
     for (int i=n-1; i>=0; --i)
         array[i] = new int[m];
     return array;
 }

变体 B 和 C 的内存布局会有所不同，因为它们的分配顺序不同。但是不要假设它们的内存布局是恒定的，垃圾收集器稍后可能会在堆中移动它们。

如果您担心访问速度，迭代数组的最快方法总是最左边的维度进入最外层循环， 最右边的维度 进入最内层循环(这严格围绕着各个维度 在内存中线性定位的事实而构建)。 CPU 的线性内存访问比随机访问更快(我不会在这里讨论为什么)。

在处理数组时，可以考虑两个微优化。

首先是尺寸的顺序，当您可以随意排列尺寸时，最小放在最左边，最大最右边:

int[][] slowArray = new int[10000][2];
int[][] fastArray = new int[2][10000];

第二个也节省了大量内存，因为慢速变体由 10000 x int[2] = 10001 个对象组成，而快速变体由 2 x int[10000] = 3 个对象组成。

第二个是处理数组维度的切片(它是代码不变移动的一种形式):

long sum = 0;
int[][] fastArray = new int[2][10000];
for (int i=0; i<fastArray.length; ++i) {
    int[] subArray = fastArray[i];
    for (int j=0; j<subArray.length; ++j) {
        sum += subArray[j];
    }
}

定义一个局部变量 subArray 可以从内部循环中完全消除外部维度(毕竟，i 在内部循环中永远不会改变，所以为什么每次要解析 j 时都要查找数组索引 i？)。这种优化可能由即时编译器自动执行，但据我所知，它并不总是自动执行。这对于偶尔的循环来说无关紧要，但如果数组遍历占据了处理时间的很大一部分，那就需要考虑优化了。