简短版(TL;DR)的问题是:
问题
为什么Java没有实现真正的多维数组?这是否有充分的技术原因?我在这里错过了什么?
背景
在语法层面上,Java具有多维数组,因为可以声明
int[][] arr = new int[10][10];
然而,事实似乎并非如此。JVM并没有分配足够存储100个int的连续块的内存,而是将其作为int数组的数组:因此每一层都是一块连续的内存,但整体不是连续的。因此,访问arr [i] [j] 相当慢:JVM必须
- 找到存储在arr [i]中的int [];
- 索引此以查找存储在arr [i] [j] 中的int。
这涉及查询对象以从一层到下一层跳转,这相当昂贵。
Java 之所以这样做
从某个层面上来看,即使所有内容都在一个固定的块中分配,也不难看出为什么无法将其优化为简单的比例和添加查找。问题在于 arr[3] 是它自己的引用,并且它可以更改。因此,尽管数组大小固定,但我们很容易编写
arr[3] = new int[11];
现在,由于这一层已经增长,因此scale-and-add功能出了问题。你需要在运行时知道所有内容是否仍然与以前一样大。此外,当然,它将在RAM的其他位置分配(因为它比要替换的大),因此它甚至不在scale-and-add所需的正确位置。
这个方法存在两个问题。
首先,它很慢。我进行了一个测试,对单维或多维数组中的内容求和,多维情况(int[100][100][100]
)几乎需要花费原来的两倍时间(714秒对371秒)(分别用随机int
值填充int[1000000]
和int[100][100][100]
,并在缓存热后运行1000000次)。
public static long sumSingle(int[] arr) {
long total = 0;
for (int i=0; i<arr.length; i++)
total+=arr[i];
return total;
}
public static long sumMulti(int[][][] arr) {
long total = 0;
for (int i=0; i<arr.length; i++)
for (int j=0; j<arr[0].length; j++)
for (int k=0; k<arr[0][0].length; k++)
total+=arr[i][j][k];
return total;
}
其次,由于它很慢,因此会鼓励晦涩的编码。如果您遇到需要性能要求的问题,本来应该使用多维数组解决,但是您会被激励将其写成平面数组,即使这样会使代码变得不自然和难以阅读。你只能面临一个令人无法接受的选择:晦涩的代码或者慢慢的代码。
如何解决这个问题
在我看来,基本问题很容易解决。正如我们之前看到的那样,唯一不能进行优化的原因是结构可能会发生更改。但是Java已经有了一种使引用不可更改的机制:把它们声明为final
。
现在,只需使用声明:
final int[][] arr = new int[10][10];
这样做还不够好,因为只有 arr
在这里是 final
的:arr [3]
仍然不是,可能会改变,因此结构仍然可能发生变化。但如果我们有一种声明方式,使其在底层存储 int
值的地方之外始终是 final
,那么我们就有了一个完整的不可变结构体,并且它可以作为一个块分配,并使用缩放和添加进行索引。
语法上会是什么样子我不确定(我不是设计语言的人)。也许是这样:
final int[final][] arr = new int[10][10];
尽管看起来有点奇怪。这意味着:在顶层使用 final
;在下一层使用final
;在最底层不使用final
(否则,int
值本身将是不可变的)。
如果各级都是final状态,则JIT编译器可以将其优化为与单维数组相同性能的代码,这样就消除了编写这种代码的诱惑,以应对多维数组的缓慢性。
(我听说C#做了类似的事情,虽然我也听到另一个谣言称CLR实现很糟糕,不值得拥有...也许它们只是谣言...)
问题
那么为什么Java没有真正的多维数组实现?是否存在确切的技术原因?我错过了什么吗?
更新
一个奇怪的副笔记:如果你使用int
而不是long
作为运行总计,则时间差异会降至仅几个百分点。为什么使用int
会有如此小的差异,而使用long
会有如此大的差异呢?
基准测试代码
我用于基准测试的代码,以防有人想尝试重现这些结果:
public class Multidimensional {
public static long sumSingle(final int[] arr) {
long total = 0;
for (int i=0; i<arr.length; i++)
total+=arr[i];
return total;
}
public static long sumMulti(final int[][][] arr) {
long total = 0;
for (int i=0; i<arr.length; i++)
for (int j=0; j<arr[0].length; j++)
for (int k=0; k<arr[0][0].length; k++)
total+=arr[i][j][k];
return total;
}
public static void main(String[] args) {
final int iterations = 1000000;
Random r = new Random();
int[] arr = new int[1000000];
for (int i=0; i<arr.length; i++)
arr[i]=r.nextInt();
long total = 0;
System.out.println(sumSingle(arr));
long time = System.nanoTime();
for (int i=0; i<iterations; i++)
total = sumSingle(arr);
time = System.nanoTime()-time;
System.out.printf("Took %d ms for single dimension\n", time/1000000, total);
int[][][] arrMulti = new int[100][100][100];
for (int i=0; i<arrMulti.length; i++)
for (int j=0; j<arrMulti[i].length; j++)
for (int k=0; k<arrMulti[i][j].length; k++)
arrMulti[i][j][k]=r.nextInt();
System.out.println(sumMulti(arrMulti));
time = System.nanoTime();
for (int i=0; i<iterations; i++)
total = sumMulti(arrMulti);
time = System.nanoTime()-time;
System.out.printf("Took %d ms for multi dimension\n", time/1000000, total);
}
}