对于那些不想要背景的人来说,TL;DR 版本是以下具体问题:
题
Why doesn't Java have an implementation of true multidimensional arrays? Is there a solid technical reason? What am I missing here?
背景
Java 在语法级别具有多维数组,可以声明
int[][] arr = new int[10][10];
但这似乎真的不是人们所期望的。不是让 JVM 分配一个足够大的连续 RAM 块来存储 100 个
int
,而是以int
数组的形式出现:所以每一层都是一个连续的 RAM 块,但作为一个整体不是。因此访问arr[i][j]
相当慢:JVM 必须int[]
的arr[i]
; int
的arr[i][j]
。 这涉及查询一个对象从一层到下一层,这是相当昂贵的。
为什么 Java 这样做
在一个层面上,不难看出为什么这不能优化为简单的缩放和添加查找,即使它全部分配在一个固定块中。问题是
arr[3]
本身就是一个引用,可以更改。因此,尽管数组的大小是固定的,但我们可以轻松地编写arr[3] = new int[11];
现在缩放和添加被搞砸了,因为这一层已经增长。您需要在运行时知道所有内容是否仍然和以前一样大小。此外,当然,这将被分配到 RAM 中的其他地方(它必须是,因为它比它要替换的要大),因此它甚至不在正确的位置进行缩放和添加。
它有什么问题
在我看来,这并不理想,原因有二。
一方面,它很慢。我使用这些方法对一维或多维数组的内容进行求和的测试,对于多维情况(分别是
int[1000000]
和int[100][100][100]
,填充随机int
值,使用热缓存运行 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]
仍然不是,并且可以更改,因此结构可能仍会更改。但是,如果我们有一种方法来声明事物,使其始终为final
,除了存储int
值的底层,那么我们将拥有一个完整的不可变结构,并且可以将其全部分配为一个块,并用缩放和添加索引。它在语法上看起来如何,我不确定(我不是语言设计师)。也许
final int[final][] arr = new int[10][10];
虽然不可否认,这看起来有点奇怪。这意味着:
final
在顶层;下一层final
;不是底层的final
(否则int
值本身将是不可变的)。最终确定性将使 JIT 编译器能够优化这一点,从而为单维数组提供性能,然后消除以这种方式进行编码的诱惑,只是为了解决多维数组的缓慢问题。
(我听到有传言说 C# 做了这样的事情,虽然我也听到另一个传言说 CLR 实现太糟糕了,不值得拥有......也许他们只是谣言......)
题
So why doesn't Java have an implementation of true multidimensional arrays? Is there a solid technical reason? What am I missing here?
更新
一个奇怪的旁注:如果你使用
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);
}
}
最佳答案
but it seems that this is really not what one might have expected.
为什么?
考虑表单
T[]
表示“类型 T 的数组”,那么正如我们所期望的 int[]
表示“int 类型的数组”,我们期望 int[][]
意思是“int 类型的数组类型的数组”,因为有 int[]
的理由也不少。如 T
比int
.因此,考虑到可以有任何类型的数组,它遵循的方式就是
[
和 ]
用于声明和初始化数组(就此而言, {
、 }
和 ,
),如果没有某种禁止数组数组的特殊规则,我们可以“免费”获得这种使用。现在还要考虑一下,我们可以用锯齿状数组做一些我们不能做的事情:
lookup[1]
与 lookup[5]
是同一个数组. (这可以节省一些数据集的大量成本,例如,可以在少量内存中为 1,112,064 个代码点的完整集合映射许多 Unicode 属性,因为可以为具有匹配模式的范围重复属性的叶数组)。 在某些情况下,这些多维数组很有用。
现在,任何功能的默认状态都是未指定和未实现的。有人需要决定指定和实现一个功能,否则它就不会存在。
因为,如上所示,除非有人决定引入特殊的禁止数组数组功能,否则数组数组排序的多维数组将存在。由于数组的数组由于上述原因而有用,因此做出这样的决定将是一个奇怪的决定。
相反,数组具有可以大于 1 的已定义秩并因此与一组索引而不是单个索引一起使用的多维数组的类型,并不自然地遵循已定义的内容。有人需要:
用户也必须学习这个新功能。
所以,它必须是值得的。一些让它值得的事情是:
在这种情况下:
真的,问题不是“为什么 Java 没有真正的多维数组”?但是“为什么要这样做?”
当然,您支持多维数组的观点是有效的,出于这个原因,某些语言确实有这些观点,但负担仍然是争论一个特性,而不是争论它。
(I hear a rumour that C# does something like this, although I also hear another rumour that the CLR implementation is so bad that it's not worth having... perhaps they're just rumours...)
像许多谣言一样,这里也有一些真相,但这不是全部真相。
.NET 数组确实可以有多个等级。这并不是它比 Java 更灵活的唯一方式。每个等级也可以有一个除零以外的下限。因此,例如,您可以拥有一个从 -3 到 42 的数组或一个二维数组,其中一个等级从 -2 到 5,另一个从 57 到 100,或其他。
C# 并没有从它的内置语法中完全访问所有这些(你需要调用
Array.CreateInstance()
以获得除零以外的下界),但它允许你使用语法 int[,]
对于 int
的二维数组, int[,,]
对于三维数组,依此类推。现在,处理除零以外的下界所涉及的额外工作增加了性能负担,但这些情况相对不常见。出于这个原因,下限为 0 的单秩数组被视为具有更高性能实现的特殊情况。事实上,它们在内部是一种不同的结构。
在 .NET 中,下界为零的多维数组被视为下界恰好为零的多维数组(即,作为较慢情况的示例),而不是能够处理更大等级的较快情况比 1。
当然,.NET 可以 有一个基于零的多维数组的快速路径案例,但是 Java 没有它们的所有原因都适用 和 事实上已经有一个特殊情况,特殊情况很糟糕,然后会有两个特殊情况,他们会更糟糕。 (实际上,尝试将一种类型的值分配给另一种类型的变量时可能会遇到一些问题)。
上面没有一件事清楚地表明 Java 不可能有你所说的那种多维数组;这本来是一个足够明智的决定,但做出的决定也是明智的。
关于java - 为什么 Java 没有真正的多维数组?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/26318341/