当前位置: 首页 > 面试题库 >

Java为什么没有真正的多维数组?

诸葛绍元
2023-03-14
问题内容

对于那些不需要背景知识的人来说,TL; DR版本是以下特定问题:

Java为什么没有真正的多维数组的实现?有可靠的技术理由吗?我在这里想念什么?

背景

Java在语法级别具有多维数组,因为它可以声明

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

但这似乎并不是人们所期望的。它不是让JVM分配足够大的RAM来存储100 ints int的连续内存块,而是以s
的数组数组的形式出现:因此,每一层都是RAM的连续内存块,但总体而言不是。arr[i][j]因此,访问速度相当慢:JVM必须

  1. 找到int[]存放在arr[i];
  2. 为此索引以找到int存储在的位置arr[i][j]

这涉及查询对象以从一层到另一层,这是相当昂贵的。

为什么Java这样做

在一个层面上,不难理解为什么即使将其全部分配在一个固定的块中,也无法将其优化为简单的按比例添加的查找。问题是arr[3]它本身就是一个引用,可以更改。因此,尽管数组大小固定,但我们可以轻松地编写

arr[3] = new int[11];

现在,由于该层已增长,因此扩展和添加变得很困难。您需要在运行时知道所有内容是否仍与以前相同。另外,当然,这会分配到RAM中的其他位置(必须要分配,因为它比它要替换的要大),因此,即使在扩展和添加的正确位置也不合适。

有什么问题吗

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

首先,它很 。我使用这些方法进行的用于对一维或多维数组的内容求和的测试所花费的时间 几乎 是多维情况的 两倍
(714秒与371秒)(一个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实现太糟糕了,不值得拥有……也许只是谣言……)

那么,为什么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);
    }

}

问题答案:

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

为什么?

认为形式T[]是指“T型数组”,那么正如我们所期待int[]的意思,我们希望“int类型的数组”
int[][]是指“int类型的类型数组的数组”,因为有于没有少的原因int[]是的Tint

因此,考虑到一个人可以拥有任何类型的数组,它只是遵循这种方式[]并用于声明和初始化数组(就此而言{},),没有某种特殊的规则禁止数组的数组,我们免费获得这种使用。

现在,还要考虑使用锯齿数组可以做的其他事情:

  1. 我们可以有“锯齿状”的数组,其中不同的内部数组的大小不同。
  2. 我们可以在外部数组中具有空数组,在该数组中进行数据的适当映射,或者允许延迟构建。
  3. 我们可以故意在数组中使用别名,例如lookup[1]与相同的数组lookup[5]。(这可以节省一些数据集,例如,可以为少量内存中的1,112,064个代码点的全部映射许多Unicode属性,因为可以为具有匹配模式的范围重复属性的叶数组)。
  4. 一些堆实现可以比内存中的一个大对象更好地处理许多较小的对象。

在某些情况下,这类多维数组很有用。

现在,任何功能的默认状态都未指定且未实现。有人需要决定指定和实现一项功能,否则该功能将不存在。

因为,如上所述,除非有人决定引入特殊的禁止数组阵列功能,否则多维数组的数组阵列将存在。由于基于上述原因,数组的数组很有用,因此做出一个奇怪的决定。

相反,多维数组的排序并不自然地遵循已定义的多维数组,其中数组的定义秩可以大于1,因此可以与一组索引而不是单个索引一起使用。有人需要:

  1. 确定用于声明,初始化和使用的规范。
  2. 记录下来。
  3. 编写实际的代码来执行此操作。
  4. 测试代码以执行此操作。
  5. 处理错误,边缘情况,错误报告(实际上不是错误),由修复错误引起的向后兼容性问题。

用户还必须学习此新功能。

因此,这是值得的。一些值得的事情是:

  1. 如果没有办法做同样的事情。
  2. 如果做同一件事的方式很奇怪或不为人所知。
  3. 人们会在类似的情况下期望它。
  4. 用户自己不能提供类似的功能。

在这种情况下:

  1. 但是还有。
  2. C和C ++程序员以及基于其语法的Java已经知道在数组中使用跨步,因此可以直接应用相同的技术
  3. Java的语法基于C ,类似地,C 仅直接支持多维数组作为数组数组。(除非是静态分配的,但是在Java中数组是对象的情况下,这不是一个比喻)。
  4. 可以轻松编写一个类,该类包装数组和步幅大小的详细信息,并允许通过一组索引进行访问。

确实,问题不在于“为什么Java没有真正的多维数组”?但是“为什么要这样?”

当然,您支持多维数组的观点是正确的,并且某些语言确实出于这个原因拥有它们,但是,负担仍然是争论一个特征而不是争论不休。

(我听说C#会做类似的事情,尽管我也听到另一个谣言,说CLR实现太糟糕了,不值得拥有……也许只是谣言……)

像许多谣言一样,这里有一个真理要素,但这不是全部真理。

.NET数组确实可以具有多个等级。这不是比Java更灵活的唯一方法。每个等级还可以具有除零以外的下限。这样,例如,您可以拥有一个从-3到42的数组或一个二维数组,其中一个等级从-2到5到另一个等级从57到100,等等。

C#不能从其内置语法中完全访问所有这些内容(您需要调用Array.CreateInstance()除零以外的下限),但是它允许您将语法int[,]用于的二维数组intint[,,]对于三个维数组,依此类推。

现在,处理除零以外的下限所涉及的额外工作增加了性能负担,但是这些情况相对不常见。因此,将具有较低下限0的单列数组视为具有更高性能实现的特殊情况。实际上,它们在内部是另一种结构。

在.NET中,下界为零的多维数组被视为其下界恰好为零的多维数组(即,较慢的情况的一个示例),而不是较快的情况能够处理更大的秩比1。

当然,.NET 对于基于零的多维数组 可能 有一个快速路径案例,但是随后所有Java都没有应用它们的原因 以及
事实已经存在一个特殊情况,并且特殊情况很糟糕,然后将有两种特殊情况,它们会吸收更多。(实际上,尝试将一种类型的值分配给另一种类型的变量可能会有一些问题)。

上面没有任何一件事情清楚地表明Java不可能拥有您所说的那种多维数组。这本来是足够明智的决定,但是做出的决定也是明智的。



 类似资料:
  • 我有一个arraylist,其中添加了以下数字。 然后我使用下面的代码遍历列表并在打印前求和。 它正在打印出一个值6。有人知道发生了什么吗?或者有人能解释我在这里做错了什么吗?感谢您的时间,如果有什么我可以补充澄清的,请不要犹豫。

  • 我启动了一个国际象棋项目,使用一些旧代码绘制地图,基本上所有内容都是复制粘贴的。问题是方块没有出现?我试着修了一会儿,但没有找到解决办法。下面可能是三种最重要的方法,并简要介绍了整个项目。有些是德语的。 https://drive.google.com/file/d/1nnZHLB0Ycy04eMyYbEmduMwbGhVLZ2VB/view?usp=sharing

  • 问题内容: 我知道每次键入字符串文字时,字符串池中都会引用相同的String对象。 但是,为什么String API不包含,所以我可以使用引用? 至少,这将节省编译时间,因为编译器将知道引用现有的String,而不必检查是否已创建它以进行重用,对吗?我个人认为,字符串文字(尤其是很小的文字)在许多情况下是一种“代码异味”。 那么是否没有String.Empty背后的宏伟设计原因,还是语言创建者根本

  • 问题内容: 在Java中,有和接口。两者都属于Java的标准框架,并提供了一种访问元素的分类方法。 但是,据我了解没有。你可以用来对列表进行排序。 知道为什么要这样设计吗? 问题答案: 列表迭代器首先确保你以列表的内部顺序(也称为插入顺序)获取列表的元素。更具体地说,它是按照插入元素的顺序或操作列表的方式进行的。排序可以看作是对数据结构的一种操作,有几种方法可以对列表进行排序。 我将按照自己的见解

  • 问题内容: 我正在探索,惊讶地发现那没有。 我有两个问题。 主要问题 我想知道为什么删除了? 是否存在性能问题或其他问题? 次要问题 我解决我的问题写我的: 这样可以/有更好的方法吗? 问题答案:

  • 我刚刚注意到,C#中的多维数组没有实现,而它实现了。对于单维数组,同时实现和。 为什么会有这种差别?如果多维数组是,那么它是否也应该实现泛型版本?我注意到这一点,是因为我试图在多维数组上使用扩展方法,除非您使用或类似的方法,否则会失败;所以我可以肯定地看到使多维数组实现的一个参数。 为了在代码中澄清我的问题,我希望下面的代码打印四次,而它实际打印的是、、、、和: