chi*_*ity 35 java arrays performance multidimensional-array
TL; DR版本,对于那些不想要背景的人,是以下具体问题:
为什么Java没有真正的多维数组的实现？有坚实的技术原因吗？我在这里错过了什么？
Java在语法级别具有多维数组,可以声明
int[][] arr = new int[10][10];
但似乎这真的不是人们所期望的.它不是让JVM分配足够大的连续RAM块来存储100 int秒,而是作为ints 的数组阵列出现:所以每个层都是一个连续的RAM块,但整体而言并非如此.arr[i][j]因此访问速度相当慢:JVM必须这样做
int[]存储的arr[i];int存储的arr[i][j].这涉及查询对象从一层到另一层,这是相当昂贵的.
在一个层面上,不难看出为什么这不能被优化为简单的扩展和添加查找,即使它们都被分配在一个固定块中.问题是arr[3]它本身就是一个引用,它可以被改变.因此,尽管数组具有固定大小,但我们可以轻松编写
arr[3] = new int[11];
现在,由于这一层已经成长,因此缩放和加载是固定的.您需要在运行时知道是否所有内容仍然与以前相同.此外,当然,这将被分配到RAM中的其他地方(它必须是,因为它比它更换的更大),所以它甚至不适合扩展和添加.
在我看来,这并不理想,这有两个原因.
首先,它很慢.我使用这些方法运行的测试用于求和单维或多维数组的内容,对于多维情况(a 和a 分别填充随机值,运行1000000次,温度)几乎是两倍长(714秒对371秒)高速缓存).int[1000000]int[100][100][100]int
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存储值的底层之外,那么我们就有一个完整的不可变结构,并且它可以全部被分配为一个块,并用规模索引-and加.
它在语法上看起来如何,我不确定(我不是语言设计师).也许
final int[final][] arr = new int[10][10];
虽然承认这看起来有点奇怪.这意味着:final在顶层; final在下一层; 不在final底层(否则int值本身将是不可变的).
整个过程将使JIT编译器能够对其进行优化,以提高单维数组的性能,从而消除了为了绕过多维数组的缓慢而采用这种方式进行编码的诱惑.
(我听说有传言说C#会做这样的事情,虽然我也听到另一个传言说CLR的实施非常糟糕,以至于它不值得......也许它们只是谣言......)
那么为什么Java没有真正的多维数组的实现呢？有坚实的技术原因吗？我在这里错过了什么？
一个奇怪的旁注:如果你使用的int是运行总数而不是a,那么时间差异就会下降到几个百分点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);
}
}
Jon*_*nna 19
但似乎这真的不是人们所期望的.
为什么？
认为形式T[]是指"T型数组",那么正如我们所期望的int[]意思是"int类型的数组",我们希望int[][]是指"int类型的类型数组的数组",因为有于没有少的原因int[]是的T比int.
因此,考虑到可以拥有任何类型的数组,它只是从方式开始[,]并用于声明和初始化数组(以及为此{,}和,),没有某种禁止数组数组的特殊规则,我们得到这种"免费"使用.
现在还要考虑我们可以用锯齿状数组做的事情,否则我们无法做到:
lookup[1],与数组相同lookup[5].(这可以允许使用一些数据集进行大量节省,例如,可以在少量内存中为完整的1,112,064个代码点映射许多Unicode属性,因为可以针对具有匹配模式的范围重复属性的叶阵列).当然有些情况下这些多维数组很有用.
现在,任何功能的默认状态都未指定且未实现.有人需要决定指定和实现一个功能,否则就不存在.
因为,如上所示,除非有人决定引入一个特殊的禁止数组数组特征,否则将存在数组数组的多维数组.由于上述原因,数组数组很有用,这将是一个奇怪的决定.
相反,多维数组的类型,其中数组具有可以大于1的定义的等级,因此可以与一组索引而不是单个索引一起使用,并不是从已经定义的内容中自然地遵循.有人需要:
用户也必须学习这个新功能.
所以,它必须值得.一些值得的东西是:
在这种情况下:
真的,问题不是"为什么Java没有真正的多维数组"？但"为什么要这样？"
当然,你支持多维数组的观点是有效的,有些语言确实有它们,但是负担仍然是争论一个特征,而不是争论它.
(我听说有传言说C#会做这样的事情,虽然我也听到另一个传言说CLR的实施非常糟糕,以至于它不值得......也许它们只是谣言......)
像许多谣言一样,这里有一个真理要素,但这不是全部真相.
.NET数组确实可以有多个排名.这不是它比Java更灵活的唯一方式.每个等级也可以具有除零之外的下限.因此,你可以例如有一个从-3到42的数组或一个二维数组,其中一个等级从-2到5,另一个从57到100,或者其他.
C#没有通过其内置语法完全访问所有这些内容(您需要调用Array.CreateInstance()除0以外的下限),但它确实允许您使用int[,]二维数组的语法int,int[,,]对于三 - 维数组,等等.
现在,处理除零之外的下限所涉及的额外工作增加了性能负担,但这些情况相对不常见.因此,具有0的下限的单列数组被视为具有更高性能实现的特殊情况.实际上,它们在内部是一种不同的结构.
在.NET中,下限为零的多维数组被视为多维数组,其下限恰好为零(即,作为较慢情况的一个例子),而不是更快的情况下能够处理更高的等级比1.
当然,.NET 本来可以有基于零的多维数组的快速路径,但是后来Java的所有原因都没有应用,而且已经存在一个特殊情况,特殊情况很糟糕,然后会有两个特殊情况,他们会吸吮更多.(实际上,尝试将一种类型的值分配给另一种类型的变量时可能存在一些问题).
上面没有一件事清楚地表明Java可能不会有你所谈论的那种多维数组; 这本来是一个明智的决定,但所做的决定也是明智的.
apa*_*gin 15
我想这应该是詹姆斯·高斯林的一个问题.Java的初始设计是关于OOP和简单性,而不是关于速度.
如果您更好地了解多维数组应该如何工作,有几种方法可以实现它:
UPD.当然,您并不是第一个质疑Java数组设计问题的人.
例如,苏门答腊岛和巴拿马项目也将受益于真正的多维数组.
"Arrays 2.0"是John Rose在2012年JVM语言峰会上就此主题发表的演讲.
maa*_*nus 10
对我而言,你似乎有点自己回答了这个问题:
......将其写成平面阵列的动机,即使这样做会使其不自然且难以阅读.
所以把它写成一个易于阅读的平面阵列.有一个琐碎的助手像
double get(int row, int col) {
return data[rowLength * row + col];
}
和类似的setter以及可能是+=等价的,你可以假装你正在使用2D数组.这真的没什么大不了的.你不能使用数组表示法,一切都变得冗长和丑陋.但这似乎是Java的方式.它与BigIntegeror 完全相同BigDecimal.您不能使用大括号来访问a Map,这是一个非常类似的情况.
现在的问题是所有这些功能有多重要？将有更多的人高兴,如果他们能写x += BigDecimal.valueOf("123456.654321") + 10;,或者spouse["Paul"] = "Mary";,也可以使用二维数组没有样板,还是什么？所有这些都很好,你可以更进一步,例如阵列切片.但是没有真正的问题.在许多其他情况下,您必须在冗长和低效率之间做出选择.恕我直言,花在这个功能上的努力可以更好地花在其他地方.您的2D阵列是最好的....
Java实际上没有2D原始数组,...
它主要是一个语法糖,底层的东西是对象数组.
double[][] a = new double[1][1];
Object[] b = a;
随着数组的实现,当前的实现几乎不需要任何支持.你的实现会打开一堆蠕虫:
java.lang.reflect.Array？克隆它为2D数组？什么会
??? x = {new int[1], new int[2]};
是？一个旧式的2D int[][]？那么互操作性呢？
我想,这一切都是可行的,但Java中缺少更简单,更重要的东西.有些人一直需要2D数组,但很多人几乎不记得他们何时使用任何数组.
我无法重现您声称的性能优势.具体来说,测试程序:
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);
}
}
}
在我的工作站上运行
Run Code Online (Sandbox Code Playgroud)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)
版画
Run Code Online (Sandbox Code Playgroud)flat 264360.217 ns multi 270303.246 ns multi (idiomatic) 266607.334 ns
也就是说,我们观察到您提供的一维和多维代码之间仅有3%的差异.如果我们使用惯用Java(特别是增强的for循环)进行遍历,这种差异会下降到1%(可能是因为对同一个数组对象执行了边界检查,循环解除引用,使得及时编译器能够更加完全地忽略边界检查) .
因此,绩效似乎不足以证明增加语言的复杂性.具体来说,为了支持真正的多维数组,Java编程语言必须区分数组数组和多维数组.同样,程序员必须区分它们,并意识到它们之间的差异.API设计者必须思考是使用数组数组还是多维数组.必须扩展编译器,类文件格式,类文件验证器,解释器和及时编译器.这将是特别困难的,因为不同维度计数的多维数组将具有不兼容的存储器布局(因为必须存储它们的维度的大小以启用边界检查),因此不能是彼此的子类型.因此,类java.util.Arrays的方法可能必须为每个维度计数重复,就像使用数组的所有其他多态算法一样.
总而言之,扩展Java以支持多维数组将为大多数程序提供可忽略的性能增益,但需要对其类型系统,编译器和运行时环境进行非平凡的扩展.因此,引入它们与Java编程语言的设计目标不一致,特别是它很简单.