Java：多维数组 VS 一维数组

Question

Java：多维数组 VS 一维数组

javaarraysmultidimensional-array

31

例如：

a) int [x][y][z]

对比
b) int[x*y*z]

最初我会选择a)来简化问题。

我知道Java不像C那样在内存中线性存储数组，但这对我的程序有什么影响呢？

- Mikolan

参见：https://dev59.com/R0zSa4cB1Zd3GeqPllJf - polygenelubricants

4个回答

23

在当前的CPU上，非缓存内存访问比算术运算慢数百倍（参见这个演示文稿和阅读每个程序员都应该了解的有关内存的知识）。选项a）将产生约3次内存查找，而选项b）将产生约1次内存查找。此外，CPU的预取算法可能不会工作得很好。因此，在某些情况下，选项b）可能更快（它是一个热点，并且数组不适合CPU的缓存）。有多快？这将取决于应用程序。

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

我进行了一个基准测试，比较了3维int数组（“Multi”列）和相应的1维int数组（“Single”列）。代码在这里，测试在这里。我在64位jdk1.6.0_18、Windows 7 x64、Core 2 Quad Q6600 @ 3.0 GHz、4 GB DDR2上运行了它，使用JVM选项-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%的应用程序，不会有明显的区别。

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

- Esko Luontola

4

使用第一种变量（三维）更容易理解，且出现逻辑错误的可能性较小（特别是在建模三维空间时），因此建议使用它。

- Roman

2

如果您选择后一种方法，则需要为每个数组访问执行算术运算。这将会很痛苦且容易出错（除非您将其封装在提供此功能的类中）。

我认为选择平坦数组没有任何（显著的）优化（特别是考虑到用于索引的算术运算）。就像所有优化一样，您需要进行一些测量并确定它是否真的值得。

- Brian Agnew

1

好的，谢谢。我将使用一个三维数组，如果它导致性能问题，那就进行比较。 - Mikolan

1

如果您使用多维数组，那么每次访问数组都需要执行多次内存访问，这可能比一些简单的算术运算慢得多。但是，是的，对于这种情况，您确实需要在采取行动之前进行测量。 - Michael Borgwardt

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Jack · Accepted Answer

通常在寻找这类问题的答案时，最好的方法是查看选择项如何编译成JVM字节码：

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

This is translated into:

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个随机数，而对于单维数组只生成一个随机数（并且伪随机数生成器可能会消耗一些CPU）。

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

Java版本 "1.6.0_17" Java(TM) SE运行时环境 (版本号为1.6.0_17-b04) Java HotSpot(TM) 64位服务器虚拟机 (版本号为14.3-b01, 混合模式)

（说明：本文是关于Java版本信息的。）