Die TL; DR-Version für diejenigen, die den Hintergrund nicht wollen, ist die folgende spezielle Frage:

Frag

Warum hat Java keine Implementierung von echten mehrdimensionalen Arrays? Gibt es einen soliden technischen Grund? Was vermisse ich hier?

Hintergrun

Java hat mehrdimensionale Arrays auf Syntaxebene, in denen man @ deklarieren ka

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

aber es scheint, dass dies wirklich nicht das ist, was man erwartet hätte. Anstatt die JVM einen zusammenhängenden RAM-Block zuweisen zu lassen, der groß genug ist, um 100 @ zu speicheints, es kommt als Array von Arrays vonints: Jede Schicht ist also ein zusammenhängender RAM-Block, aber das Ganze ist es nicht. Zugriff aufarr[i][j] ist also eher langsam: die JVM muss

find theint[] gespeichert beiarr[i];index this um das @ zu findint gespeichert beiarr[i][j].

Dies beinhaltet das Abfragen eines Objekts, um von einer Ebene zur nächsten zu gelangen, was ziemlich teuer ist.

Warum macht Java das?

uf einer Ebene ist es nicht schwer zu erkennen, warum dies nicht für eine einfache Suche nach Skalierung und Addition optimiert werden kann, selbst wenn alles in einem festen Block zugeordnet wäre. Das Problem ist, dassarr[3] ist eine eigene Referenz und kann geändert werden. Also, obwohl Arrays von fester Größe sind, könnten wir leicht @ schreib

arr[3] = new int[11];

und jetzt wird das Scale-and-Add geschraubt, weil diese Schicht gewachsen ist. Sie müssten zur Laufzeit wissen, ob alles noch so groß ist wie früher. Darüber hinaus wird dies natürlich an einer anderen Stelle im RAM zugewiesen (dies muss der Fall sein, da es größer ist als das, was es ersetzt), sodass es nicht einmal an der richtigen Stelle zum Skalieren und Hinzufügen ist.

Was ist daran problematisch

Es scheint mir, dass dies nicht ideal ist, und das aus zwei Gründen.

um einen ist esschleppen. Ein Test, den ich mit diesen Methoden zum Summieren des Inhalts eines eindimensionalen oder mehrdimensionalen Arrays durchgeführt habe, hat fast doppelt so lang (714 Sekunden vs 371 Sekunden) für den mehrdimensionalen Fall (einint[1000000] und einint[100][100][100] bzw. gefüllt mit zufälligemint -Werte, 1000000-mal mit warmem Cache ausführen.

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

weitens, weil es langsam ist, ist es dab fördert obskure Kodierung. Wenn Sie auf etwas Leistungskritisches stoßen, das normalerweise mit einem mehrdimensionalen Array durchgeführt wird, haben Sie einen Anreiz, es als flaches Array zu schreiben, auch wenn das unnatürlich und schwer zu lesen ist. Sie haben die unangenehme Wahl: obskurer Code oder langsamer Code.

Was könnte dagegen getan werden

Es scheint mir, dass das Grundproblem leicht genug behoben werden könnte. Der einzige Grund, wie wir bereits gesehen haben, dass es nicht optimiert werden kann, ist, dass sich die Struktur möglicherweise ändert. Aber Java hat bereits einen Mechanismus, um Referenzen unveränderlich zu machen: deklarieren Sie sie alsfinal.

Now, erkläre es einfach mit

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

ist nicht gut genug, weil es nur @ iarr das istfinal Hier:arr[3] ist immer noch nicht und kann geändert werden, sodass sich die Struktur möglicherweise noch ändert. Aber wenn wir eine Möglichkeit hätten, Dinge so zu deklarieren, dass esfinal durchgehend, außer in der untersten Ebene, in der dasint -Werte werden gespeichert, dann hätten wir eine gesamte unveränderliche Struktur, und alles könnte als ein Block zugeordnet und mit scale-and-add indiziert werden.

Wie es syntaktisch aussehen würde, weiß ich nicht genau (ich bin kein Sprachdesigner). Könnte sei

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

although zugegebenermaßen sieht das ein bisschen komisch aus. Das würde bedeuten:final in der obersten Ebene;final in der nächsten Schicht; nichtfinal in der untersten Ebene (sonstint Werte selbst wären unveränderlich).

Durchgängige Endgültigkeit würde es dem JIT-Compiler ermöglichen, dies zu optimieren, um die Leistung eines eindimensionalen Arrays zu verbessern. Dies würde dann die Versuchung aufheben, auf diese Weise zu codieren, um die Langsamkeit mehrdimensionaler Arrays zu umgehen.

(Ich höre ein Gerücht, dass C # so etwas tut, obwohl ich auch ein anderes Gerücht höre, dass die CLR-Implementierung so schlecht ist, dass es sich nicht lohnt ... vielleicht sind es nur Gerüchte ...)

Frag

So warum hat Java keine Implementierung von echten mehrdimensionalen Arrays? Gibt es einen soliden technischen Grund? Was vermisse ich hier?

Aktualisiere

Eine bizarre Randnotiz: Wenn Sie ein @ verwenden, sinkt der Zeitunterschied auf nur wenige Prozenint für die laufende Summe anstatt eineslong. Warum sollte es einen so kleinen Unterschied zu einem @ gebeint, und so ein großer Unterschied mit einemlong?

Benchmarking code

Code, den ich für das Benchmarking verwendet habe, falls jemand versuchen möchte, diese Ergebnisse zu reproduzieren:

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

}