为什么Java没有真正的multidimensional array?

对于那些不想要背景的人来说,TL; DR版本是以下具体问题:

为什么Java没有实现真正的multidimensional array? 有一个坚实的技术原因吗? 我在这里错过了什么?

背景

Java在语法级别有multidimensional array,可以声明

int[][] arr = new int[10][10]; 

但这似乎并不是人们所期望的。 而不是让JVM分配一个足以存储100个int的连续块,它是以int数组的forms出现的:所以每一层都是连续的RAM块,但是整体来说不是这样。 访问arr[i][j]是相当慢的:JVM必须

  1. find存储在arr[i]int[] arr[i] ;
  2. 索引这个来find存储在arr[i][j]int

这包括查询一个对象从一层到另一层,这是相当昂贵的。

为什么Java这样做

在一个层面上,不难看出为什么不能通过简单的扩展和增加查找来优化,即使它们全部分配在一个固定块中。 问题是, arr[3]是所有它自己的参考,它可以被改变。 所以虽然数组的大小是固定的,但我们可以很容易地写出来

 arr[3] = new int[11]; 

现在规模和增加是因为这个层次的增长而被拧紧的。 你需要知道在运行时是否所有东西都和以前一样大小。 此外,当然,这将被分配到RAM中的其他地方(这将是,因为它比它所替代的要大),所以它甚至不是在缩放和添加的正确位置。

有什么问题呢

在我看来,这是不理想的,这有两个原因。

首先,它很 。 对于多维情况( int[1000000]int[100][100][100] ),使用这些方法对单维或multidimensional array的内容进行求和的testing花费了近两倍的时间 (714秒vs 371秒) int[100][100][100] ,用随机的int值填充,运行1000000次,热caching)。

 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; } 

其次,因为速度很慢,所以鼓励了模糊的编码 。 如果遇到一些自然而然会用multidimensional array来处理的性能问题,那么即使这样做不自然也难以阅读,您也有动力将其写成平面数组。 你留下一个难以接受的select:模糊的代码或慢代码。

可以做些什么呢

在我看来,基本问题很容易被解决。 正如我们前面看到的,唯一的原因是它不能被优化,结构可能会改变。 但是Java已经有了一个使引用不变的机制:把它们声明为final

现在,只要声明

 final int[][] arr = new int[10][10]; 

是不够好的,因为这里只有finalarr[3]还没有,可以改变,所以结构可能会改变。 但是如果我们有一种方法来声明事物,那么除了存储int值的底层以外,我们将拥有一个完整的不可变结构,它可以被分配为一个块,并且被索引与规模和增加。

它如何看起来语法上,我不知道(我不是一个语言devise师)。 也许

 final int[final][] arr = new int[10][10]; 

虽然承认,看起来有点怪异。 这将意味着: final一层在顶层; final在下一层; 不是final一层(否则int值本身将是不可变的)。

通过使用终结性命令,JIT编译器可以优化这个性能,从而使性能达到单维数组的性能,从而消除了以这种方式进行编码的诱惑,以避免multidimensional array的缓慢。

(我听到一个传言,C#做这样的事情,虽然我也听到另一个传言,CLR的实施是如此糟糕,不值得有…也许他们只是谣言…)

那么为什么Java没有实现真正的multidimensional array呢? 有一个坚实的技术原因吗? 我在这里错过了什么?

更新

一个奇怪的方面说明:如果你使用int而不是long int ,那么时间的差异只会降到几个百分点。 为什么会有一个这样的一个小小的差异,一个int ,这么大的差别呢?

基准代码

我用于基准testing的代码,以防万一任何人想要重现这些结果:

 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); } } 

但这似乎并不是人们所期望的。

为什么?

考虑到formsT[]意味着“T型数组”,那么就像我们所期望的int[]意味着“int型数组”一样,我们期望int[][]意味着“数组types的数组int“,因为没有比int int[]作为T原因。

因此,考虑到一个人可以有任何types的数组,就可以按照[]用于声明和初始化数组(以及{}和)的方式来实现,没有某种特殊的规则禁止数组的数组,我们得到这种“免费”的使用。

现在考虑一下我们可以用锯齿形数组做些事情,否则我们无法做到:

  1. 我们可以在不同的内部arrays大小不一的情况下使用锯齿形arrays。
  2. 我们可以在外部数组中的空数组中进行适当的数据映射,或者允许惰性构build。
  3. 我们可以故意在数组中使用别名,例如lookup[1]lookup[5]是一样的数组。 (这可以允许使用某些数据集大量节省,例如许多Unicode属性可以映射到less量内存中的全部1,112,064个代码点,因为属性的叶子数组可以在具有匹配模式的范围内重复。
  4. 一些堆实现可以比内存中的一个大对象更好地处理许多较小的对象。

当然有些情况下这些multidimensional array是有用的。

现在,任何function的默认状态是未指定和未实现的。 有人需要决定指定和实现一个function,否则它不会存在。

因为,如上所示,除非有人决定引入一个特殊的禁止arrays特征,否则将存在arrays数组的multidimensional array。 由于上述原因,数组数组是有用的,这将是一个奇怪的决定。

相反,multidimensional array中sorting大于1的multidimensional array,并不适用于已定义的索引,而是使用一组索引而不是单个索引。 有人需要:

  1. 决定声明,初始化和使用的规范将起作用。
  2. logging它。
  3. 写实际的代码来做到这一点。
  4. testing代码来做到这一点。
  5. 处理错误,边缘情况,实际上没有错误的错误报告,修复错误导致的向后兼容性问题。

用户也必须学习这个新function。

所以,它必须是值得的。 有些事情会使它值得:

  1. 如果没有办法做同样的事情。
  2. 如果做同样的事情的方式是陌生的或不知名的。
  3. 人们会从类似的环境中期待它。
  4. 用户本身不能提供类似的function。

在这种情况下,

  1. 但是还有。
  2. C和C ++程序员已经知道在数组中使用stride,并且在它的语法上构build了Java,所以可以直接应用相同的技术
  3. Java的语法是基于C ++的,而C ++同样只是直接支持multidimensional array作为数组的arrays。 (除非静态分配,但这不是在Java中数组是对象的类比)。
  4. 我们可以很容易地编写一个包装数组和细节步长的类,并允许通过一组索引进行访问。

真的,问题不是“为什么Java没有真正的multidimensional array”? 但是“为什么要这样?”

当然,你们提出的支持multidimensional array的观点是有效的,而且有些语言也是有这个理由的,但是负担却是争辩一个特性,而不是争辩。

(我听到一个传言,C#做这样的事情,虽然我也听到另一个传言,CLR的实施是如此糟糕,不值得有…也许他们只是谣言…)

像许多谣言一样,这里有一些真相,但这不是完整的真相。

.NET数组确实可以有多个等级。 这不是比Java更灵活的唯一方式。 每个等级也可以有一个不等于零的下限。 因此,你可以例如有一个从-3到42的数组或者一个二维数组,其中一个等级从-2到5,另一个从57到100,或者其他。

C#没有完全访问所有这些从它的内置语法(你需要调用Array.CreateInstance()的下限以外的零),但它的确允许你使用语法int[,]作为int的二维数组,三维数组的int int[,,]等等。

现在,处理除零以外的下限所涉及的额外工作增加了性能负担,但这些情况相对不常见。 出于这个原因,具有0的下界的单排列数组被视为具有更高性能实现的特例。 事实上,他们在内部是一种不同的结构。

在.NET中,具有零下界的multidimensional array被视为multidimensional array,其下边界恰好为零(即,作为较慢情况的一个例子),而不是快速的情况下能够处理更大的队列比1。

当然,.NET 可能有一个快速path的零基multidimensional array的情况下,但是所有的原因,Java没有他们申请事实上,已经有一个特殊情况,特殊情况吸,然后会有两个特殊情况,他们会吸更多。 (事实上​​,在尝试将一种types的值赋给另一种types的variables时,可能会有一些问题)。

上面没有一件事情清楚地表明Java不可能有你所说的multidimensional array; 这将是一个明智的决定,但做出的决定也是明智的。

我想这应该是James Gosling的一个问题。 Java的最初devise是关于OOP和简单性,而不是速度。

如果您对multidimensional array的工作方式有更好的了解,可以通过以下几种方式使其生效:

  1. 提交一个JDK增强build议 。
  2. 通过Java Community Process开发一个新的JSR。
  3. 提出一个新的项目 。

UPD 。 当然,你不是第一个质疑Java数组devise问题的人。
例如, 苏门答腊和巴拿马的项目也将从真正的多维arrays中受益。

“数组2.0”是John Rose在2012年JVM语言峰会上关于这个主题的演讲。

对我来说,你看起来像是你自己回答了这个问题:

…把它写成一个平面arrays的动机,即使这使得不自然和难以阅读。

所以把它写成一个容易阅读的平面数组。 像一个微不足道的帮手

 double get(int row, int col) { return data[rowLength * row + col]; } 

和类似的setter,可能是+=等价的,你可以假装你正在使用2D数组。 这真的没什么大不了的。 你不能使用数组符号,一切都变得冗长和难看 。 但是这似乎是Java的方式。 这与BigIntegerBigDecimal完全相同。 你不能使用大括号来访问一个Map ,这是一个非常相似的情况。

现在问题是所有这些function有多重要? 如果可以写x += BigDecimal.valueOf("123456.654321") + 10; ,或spouse["Paul"] = "Mary"; ,还是使用二维数组没有样板,或什么? 所有这一切都将是很好的,你可以走得更远,例如,数组切片。 但是没有真正的问题。 在许多其他情况下,您必须在冗长和无效之间进行select。 恕我直言,花在这个function上的努力可以更好地花在其他地方。 你的二维数组是一个新的最好的….

Java实际上没有2D基元数组,…

它主要是一个语法糖,基本的东西是对象的数组。

 double[][] a = new double[1][1]; Object[] b = a; 

随着数组被通用化,当前的实现几乎不需要任何支持。 你的实现会打开一堆蠕虫:

  • 目前有8个基本types,这意味着9个数组types,是一个二维数组是十个? 那3D呢?
  • 数组有一个特殊的对象头types。 二维数组可能需要另一个。
  • 那么java.lang.reflect.Array呢? 克隆它的二维数组?
  • 许多其他function将被改编,例如序列化。

还有什么

 ??? x = {new int[1], new int[2]}; 

是? 一个旧式的2D int[][] ? 互操作性呢?

我想,这一切都是可行的,但Java中缺less更简单,更重要的东西。 有些人一直都需要二维数组,但很多人根本不记得什么时候使用任何数组。

我无法重现您声明的性能优势。 具体来说,testing程序:

 public abstract class Benchmark { final String name; public Benchmark(String name) { this.name = name; } abstract int run(int iterations) throws Throwable; private BigDecimal time() { try { int nextI = 1; int i; long duration; do { i = nextI; long start = System.nanoTime(); run(i); duration = System.nanoTime() - start; nextI = (i << 1) | 1; } while (duration < 1000000000 && nextI > 0); return new BigDecimal((duration) * 1000 / i).movePointLeft(3); } catch (Throwable e) { throw new RuntimeException(e); } } @Override public String toString() { return name + "\t" + time() + " ns"; } public static void main(String[] args) throws Exception { final int[] flat = new int[100*100*100]; final int[][][] multi = new int[100][100][100]; Random chaos = new Random(); for (int i = 0; i < flat.length; i++) { flat[i] = chaos.nextInt(); } for (int i=0; i<multi.length; i++) for (int j=0; j<multi[0].length; j++) for (int k=0; k<multi[0][0].length; k++) multi[i][j][k] = chaos.nextInt(); Benchmark[] marks = { new Benchmark("flat") { @Override int run(int iterations) throws Throwable { long total = 0; for (int j = 0; j < iterations; j++) for (int i = 0; i < flat.length; i++) total += flat[i]; return (int) total; } }, new Benchmark("multi") { @Override int run(int iterations) throws Throwable { long total = 0; for (int iter = 0; iter < iterations; iter++) for (int i=0; i<multi.length; i++) for (int j=0; j<multi[0].length; j++) for (int k=0; k<multi[0][0].length; k++) total+=multi[i][j][k]; return (int) total; } }, new Benchmark("multi (idiomatic)") { @Override int run(int iterations) throws Throwable { long total = 0; for (int iter = 0; iter < iterations; iter++) for (int[][] a : multi) for (int[] b : a) for (int c : b) total += c; return (int) total; } } }; for (Benchmark mark : marks) { System.out.println(mark); } } } 

在我的工作站上运行

 java version "1.8.0_05" Java(TM) SE Runtime Environment (build 1.8.0_05-b13) Java HotSpot(TM) 64-Bit Server VM (build 25.5-b02, mixed mode) 

版画

 flat 264360.217 ns multi 270303.246 ns multi (idiomatic) 266607.334 ns 

也就是说,我们观察到您提供的一维和多维代码之间仅有3%的差异。 如果我们使用惯用的Java(特别是增强的for循环)进行遍历(这可能是因为边界检查是在相同的数组对象上执行循环引用,使得即时编译器可以更彻底地检查边界检查),这种差异会降低到1% 。

因此,performance似乎不足以提高语言的复杂性。 具体而言,为了支持真正的multidimensional array,Java编程语言将不得不区分数组数组和multidimensional array。 同样,程序员也必须区分它们,并意识到它们的不同之处。 APIdevise者将不得不思考是否使用数组数组或者multidimensional array。 编译器,类文件格式,类文件validation器,解释器以及即时编译器将不得不被扩展。 这将是特别困难的,因为不同维度计数的multidimensional array将具有不兼容的存储器布局(因为它们的维度的大小必须被存储以实现边界检查),因此可以不是彼此的子types。 因此,类java.util.Arrays的方法可能必须重复每个维数,所有其他多态algorithm处理数组。

总而言之,扩展Java来支持multidimensional array将会为大多数程序提供微不足道的性能提升,但需要对其types系统,编译器和运行时环境进行非平凡的扩展。 因此,介绍它们会与Java编程语言的devise目标不一致,具体而言,它很简单 。

由于这个问题在很大程度上是关于性能的,所以让我提出一个适当的基于JMH的基准。 我也改变了一些东西,使你的例子更简单,性能优势更加突出。

在我的情况下,我比较一维数组与二维数组,并使用一个非常短的内部维度。 这是caching最糟糕的情况。

我已经尝试了longint累加器,并没有看到他们之间的差异。 我用int提交版本。

 @OutputTimeUnit(TimeUnit.NANOSECONDS) @BenchmarkMode(Mode.AverageTime) @OperationsPerInvocation(X*Y) @Warmup(iterations = 30, time = 100, timeUnit=MILLISECONDS) @Measurement(iterations = 5, time = 1000, timeUnit=MILLISECONDS) @State(Scope.Thread) @Threads(1) @Fork(1) public class Measure { static final int X = 100_000, Y = 10; private final int[] single = new int[X*Y]; private final int[][] multi = new int[X][Y]; @Setup public void setup() { final ThreadLocalRandom rnd = ThreadLocalRandom.current(); for (int i=0; i<single.length; i++) single[i] = rnd.nextInt(); for (int i=0; i<multi.length; i++) for (int j=0; j<multi[0].length; j++) multi[i][j] = rnd.nextInt(); } @Benchmark public long sumSingle() { return sumSingle(single); } @Benchmark public long sumMulti() { return sumMulti(multi); } public static long sumSingle(int[] arr) { int total = 0; for (int i=0; i<arr.length; i++) total+=arr[i]; return total; } public static long sumMulti(int[][] arr) { int total = 0; for (int i=0; i<arr.length; i++) for (int j=0; j<arr[0].length; j++) total+=arr[i][j]; return total; } } 

性能的差异比您所测量的要大:

 Benchmark Mode Samples Score Score error Units osMeasure.sumMulti avgt 5 1,356 0,121 ns/op osMeasure.sumSingle avgt 5 0,421 0,018 ns/op 

这是三倍以上的因素。 (请注意, 每个数组元素报告时间。)

我也注意到,没有涉及到热身:前100毫秒和其余的一样快。 显然,这是一个简单的任务,解释者已经尽其所能,使其最优化。

更新

sumMulti的内部循环改为

  for (int j=0; j<arr[i].length; j++) total+=arr[i][j]; 

(注意arr[i].length )导致显着的加速,正如maaartinus预测的那样。 使用arr[0].length使得不可能消除索引范围检查。 现在的结果如下:

 Benchmark Mode Samples Score Error Units osMeasure.sumMulti avgt 5 0,992 ± 0,066 ns/op osMeasure.sumSingle avgt 5 0,424 ± 0,046 ns/op 

如果你想快速实现一个真正的multidimensional array,你可以编写一个像这样的自定义实现。 但是你是对的…它不像数组符号那么简单。 虽然整洁的实施可能相当友好。

 public class MyArray{ private int rows = 0; private int cols = 0; String[] backingArray = null; public MyArray(int rows, int cols){ this.rows = rows; this.cols = cols; backingArray = new String[rows*cols]; } public String get(int row, int col){ return backingArray[row*cols + col]; } ... setters and other stuff } 

为什么不是默认的实现?

Java的devise者可能不得不决定如何使用通常的C数组语法的默认表示法。 他们有一个单一的数组符号,可以实现数组的arrays或真正的multidimensional array。

我认为早期的Javadevise人员真的担心Java是安全的。 很多决定似乎都是为了让普通程序员(或者糟糕的一天中的好程序员)不会搞砸某些东西而困难。 使用真正的multidimensional array,用户可以通过将块分配到无用的位置来更容易地浪费大量的内存。

而且,从Java的embedded式系统的根源,他们可能发现它更可能find要分配的内存块,而不是真正的多维对象所需的大块内存。

当然,另一方面是multidimensional array真正感觉到的地方受到损害。 而且你不得不使用库和杂乱的代码来完成你的工作。

为什么它还没有被包含在语言中?

即使在今天,从内存浪费/滥用的angular度来看,真正的multidimensional array也是一个风险。