Schnellste Möglichkeit zum Lesen/speichern viele mehrdimensionale Daten? (Java)

1) Warum ist ein array, also relativ langsam?

Als andere Spitzen, die Sie vergleichen äpfel mit Birnen. Die dreifach-array ist zu langsam-da braucht es zu dereferenzieren (innerlich zumindest - ja, "es gibt keine Pointer in Java") drei mal; aber dann wieder, Sie kann nicht auf eine einzige integer-variable...

2) Und warum wird es sogar langsamer, wenn ich diese in der inneren Schleife:

values[z][y][x] = 1; //(notice x and z switched)

Weil Sie abgenommen haben cache-Kohärenz. Die schnellsten verändernden Indizes sollen die letzten sein, so dass die meisten Speicherzugriffe auftreten, die nebeneinander innerhalb der gleichen cache-Blöcken, stattdessen zwingen Sie Ihren Prozessor zu warten, bis die Blöcke werden gelesen aus dem Haupt-RAM.

3) am wichtigsten: Kann ich mit einer Daten-Struktur, die ist so schnell wie die Zuordnung einer einzelnen ganzen Zahl, aber speichern kann so viel Daten wie der 3D-array?

Nicht. Es gibt keine solche Struktur, da die integer-variable passt in eine Maschine registrieren (sogar schneller als der Prozessor-Speicher-cache), und kann immer zugegriffen werden, schneller als alles, was Sie kümmern zu erwähnen. Prozessor-Geschwindigkeiten sind um ein Vielfaches schneller als Hauptspeicher beschleunigt. Wenn Ihr 'working set' (die Daten, die Sie benötigen, um den Betrieb auf) passt nicht in die Register-oder cache-Speicher, müssen Sie eine Strafe bezahlen, um es zu Holen aus dem RAM (oder noch schlimmer, Scheibe).

Diesem wird gesagt, Java hat Grenze prüft bei jedem array-Zugriff, und scheint nicht zu schlau zu sein über die Optimierung der überprüfung von Grenzen entfernt. Der folgende Vergleich von Interesse sein können:

public static long test1(int[][][] array) {
    long start = System.currentTimeMillis();
    for ( int x = 0; x < 400; x++ ) {
        for ( int y = 0; y < 300; y++ ) {
            for ( int z = 0; z < 400; z++ ) {
                array[x][y][z] = x + y + z;
            }
        }
    }
    return System.currentTimeMillis() - start;
}

public static long test2(int [] array) {
    long start = System.currentTimeMillis();
    for ( int x = 0; x < 400; x++ ) {
        for ( int y = 0; y < 300; y++ ) {
            for ( int z = 0; z < 400; z++ ) {
                array[z + y*400 + x*400*300] = x + y + z;
            }
        }
    }
    return System.currentTimeMillis() - start;
}

public static void main(String[] args) {

    int[][][] a1 = new int[400][300][400];
    int[] a2 = new int[400*300*400];
    int n = 20;

    System.err.println("test1");
    for (int i=0; i<n; i++) {
        System.err.print(test1(a1) + "ms ");
    }
    System.err.println();
    System.err.println("test2");
    for (int i=0; i<n; i++) {
        System.err.print(test2(a2) + "ms ");
    }
    System.err.println();
}

Die Ausgabe auf meinem system, ist

test1
164ms 177ms 148ms 149ms 148ms 147ms 150ms 151ms 152ms 154ms 151ms 150ms 148ms 148ms 150ms 148ms 150ms 148ms 148ms 149ms 
test2
141ms 153ms 130ms 130ms 130ms 133ms 130ms 130ms 130ms 132ms 129ms 131ms 130ms 131ms 131ms 130ms 131ms 130ms 130ms 130ms

Daher ist es etwas Raum für Verbesserung... aber ich glaube wirklich nicht, es lohnt sich.

Haben Sie versucht das:

Object[][][] store = new Object[ 400 ][300][400];

for (int x=0; x<400; x++)
{
    Object[][] matrix = store[x];

    for (int y=0; y<300; y++)
    {
        Object[] line = matrix[y];
        for (int z=0; z<400; z++)
        {
             //compute and store value
             line[z] = //result;
        }
    }
}

könnte es verbessern Sie Ihre cache-thrashing.

Wenn man bedenkt, dass das array ist riesig, die Menge an Arbeitsspeicher verwendet wird, die indirections benötigt (ein mehrdimensionales array ist ein arrays von Referenz auf array...), das scheint nicht bei allen langsam zu mir. Wenn Sie den Schalter x und z sind Sie wahrscheinlich löschen den cache.

Als Vergleich könnte man alles speichern in einem flachen array.... Dies verbessert die Speicherung der Geschwindigkeit... aber dann ist der Abruf wäre komplexer und viel langsamer.

int k = 0;
for (int x=0; x<400; x++)
{
    for (int y=0; y<300; y++)
    {
        for (int z=0; z<400; z++)
        {
             //compute and store value
             arr[k++] = val;
        }
    }
}