Java多维数组：内存地址和遍历速度

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] 内存地址会像这样吗（我的理解是每个块之间的其他变量可能有额外的数据，但我省略了这些情况，因为它们不相关)： （抱歉，如果图像令人困惑，我只能使用绘画并尽力表达布局。所以 array[0][0][0] //[i][j][k] 将在地址 06 中）

Answer 1

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

例如int[][] twoDim = new int[50][100];实际上在内存中创建了51个对象；一个类型 int[][] 的数组，其中 space 用于 50 个 int[] 类型的元素，并用数组填充这 50 个 space 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？）。这种优化可能由即时编译器自动执行，但据我所知，它不会总是自动执行。这对于偶尔的循环并不重要，但如果数组遍历占据了你处理时间的很大一部分，那么它就是一个需要考虑的优化。

Java多维数组：内存地址和遍历速度

Java Multi-Dimensional Array: Memory Address and Traversal Speed

java

memory

arrays