Java：多维数组与一维数组

通常，在搜索这些问题时，最好的办法是查看如何将选择编译成JVM字节码：

multi = new int[50][50];
single = new int[2500];

这被翻译成：

BIPUSH 50
BIPUSH 50
MULTIANEWARRAY int[][] 2
ASTORE 1
SIPUSH 2500
NEWARRAY T_INT
ASTORE 2

所以，正如你所看到的，JVM已经知道我们正在谈论一个多维数组。

进一步保持：

for (int i = 0; i < 50; ++i)
    for (int j = 0; j < 50; ++j)
    {
        multi[i][j] = 20;
        single[i*50+j] = 20;
    }

这被转换（跳过循环）为：

ALOAD 1: multi
ILOAD 3: i
AALOAD
ILOAD 4: j
BIPUSH 20
IASTORE

ALOAD 2: single
ILOAD 3: i
BIPUSH 50
IMUL
ILOAD 4: j
IADD
BIPUSH 20
IASTORE

因此，如您所见，多维数组在 VM 内部处理，没有由无用的指令生成的开销，而使用单个数组会使用更多指令，因为偏移量是手动计算的。

我不认为性能会是一个问题。

编辑：

我做了一些简单的基准测试，看看这里发生了什么。我选择尝试不同的示例：线性读取、线性写入和随机访问。时间以毫秒为单位（并使用 计算方法）。结果如下：System.nanoTime()

线性写入

• 尺寸： 100x100 （10000）
  • 多： 5.786591
  • 单： 6.131748
• 尺寸： 200x200 （40000）
  • 多： 1.216366
  • 单曲： 0.782041
• 尺寸： 500x500 （250000）
  • 多： 7.177029
  • 单曲： 3.667017
• 尺寸：1000x1000 （1000000）
  • 手机： 30.508131
  • 单曲： 18.064592
• 尺寸：2000x2000（4000000）
  • 多： 185.3548
  • 单曲： 155.590313
• 尺寸：5000x5000（25000000）
  • 多：955.5299
  • 单曲： 923.264417
• 尺寸：10000x10000 （100000000）
  • 多： 4084.798753
  • 单曲： 4015.448829

线性读取

• 尺寸： 100x100 （10000）
  • 手机： 5.241338
  • 单： 5.135957
• 尺寸： 200x200 （40000）
  • 多件： 0.080209
  • 单曲： 0.044371
• 尺寸： 500x500 （250000）
  • 多： 0.088742
  • 单曲： 0.084476
• 尺寸：1000x1000 （1000000）
  • 多： 0.232095
  • 单： 0.167671
• 尺寸：2000x2000（4000000）
  • 多： 0.481683
  • 单： 0.33321
• 尺寸：5000x5000（25000000）
  • 多： 1.222339
  • 单曲： 0.828118
• 尺寸：10000x10000 （100000000）
  • 多： 2.496302
  • 单曲： 1.650691

随机读取

• 尺寸： 100x100 （10000）
  • 手机： 22.317393
  • 单： 8.546134
• 尺寸： 200x200 （40000）
  • 多： 32.287669
  • 单： 11.022383
• 尺寸： 500x500 （250000）
  • 手机： 189.542751
  • 单曲： 68.181343
• 尺寸：1000x1000 （1000000）
  • 手机：1124.78609
  • 单曲： 272.235584
• 尺寸：2000x2000（4000000）
  • 手机： 6814.477101
  • 单曲： 1091.998395
• 尺寸：5000x5000（25000000）
  • 手机： 50051.306239
  • 单曲： 7028.422262

随机数组有点误导，因为它为多维数组生成2个随机数，而为单维数组仅生成一个随机数（PNRG可能会消耗一些CPU）。

请注意，我试图让JIT仅在同一循环的第20次运行之后通过基准测试来工作。为了完整起见，我的java VM如下：

java 版本 “1.6.0_17” Java（TM） SE Runtime Environment （build 1.6.0_17-b04） Java HotSpot（TM） 64-Bit Server VM （build 14.3-b01， mixed mode）

在当前的CPU上，非缓存内存访问比算术学慢数百倍（请参阅此演示文稿并阅读每个程序员应该了解的内存知识）。a） 选项将导致大约 3 次内存查找，而 b） 选项将导致大约 1 次内存查找。此外，CPU的预取算法可能也不起作用。因此，在某些情况下，b）选项可以更快（它是一个热点，阵列不适合CPU的缓存）。快多少？- 这将取决于应用程序。

就个人而言，我会首先使用a）选项，因为它将导致更简单的代码。如果探查器显示数组访问是一个瓶颈，那么我会将其转换为b）选项，以便有一对帮助器方法来读取和写入数组值（这样，混乱的代码将被限制在这两个方法中）。

我做了一个基准测试，用于将三维int数组（“多”列）与等效的一维int数组（“单”列）进行比较。代码在这里，测试在这里。我使用JVM选项在64位jdk1.6.0_18，Windows 7 x64，Core 2 Quad Q6600 @ 3.0 GHz，4 GB DDR2上运行了它（我已经从以下结果中删除了调试输出）。结果是：-server -Xmx3G -verbose:gc -XX:+PrintCompilation

Out of 20 repeats, the minimum time in milliseconds is reported.

Array dimensions: 100x100x100 (1000000)
            Multi   Single
Seq Write   1       1
Seq Read    1       1
Random Read 99      90    (of which generating random numbers 59 ms)

Array dimensions: 200x200x200 (8000000)
            Multi   Single
Seq Write   14      13
Seq Read    11      8
Random Read 1482    1239    (of which generating random numbers 474 ms)

Array dimensions: 300x300x300 (27000000)
            Multi   Single
Seq Write   53      46
Seq Read    34      24
Random Read 5915    4418    (of which generating random numbers 1557 ms)

Array dimensions: 400x400x400 (64000000)
            Multi   Single
Seq Write   123     111
Seq Read    71      55
Random Read 16326   11144    (of which generating random numbers 3693 ms)

这表明一维数组更快。尽管差异很小，但对于99%的应用程序来说，这不会引起注意。

我还做了一些测量，通过手动替换并将测量值添加到上面的结果表中来估计在随机读取基准测试中生成随机数的开销。生成随机数需要随机读取基准测试总时间的 1/3 或更少，因此内存访问将按预期主导基准测试。使用4个及以上维度的数组重复此基准测试会很有趣。这可能会使速度差异更大，因为多维数组的最顶层级别将适合CPU的缓存，而只有其他级别需要内存查找。preventOptimizingAway += array.get(x, y, z);preventOptimizingAway += x * y * z;