Laufzeitverhalten beim zeilenweise durchlaufen eines 2 dimensional array

[chris1791]

Hallo Leute,

ich habe rumgegoogelt und alle mögliche zum Durchlaufen von 2-dimensionalen Arrays gefunden. In keinem wird aber erklärt warum der Zeilenweise durchlauf, schneller als der Spaltenweise Durchlauf ist :-(

double [][] array = new double [ zeile ][ spalte ];

//Also, warum läuft diese Schleife schneller durch:

for (int i = 0; i < 10000; i++) {
    for (int x = 0; x <  zeile ; x++) {
       for (int y = 0; y < spalte ; y++) {
           array [x][y] = 0;
       }
    }
}
//als diese Schleife
for (int i = 0; i < 10000; i++) {
    for (int y = 0; y < spalte ; y++) {
        for (int x = 0; x < zeile; x++) {
            array [x][y] = 0;
        }
    }
}

Vielen Dank im Voraus für eure Hilfe.
Gruß, Chris

 

[JavaMeister]

Weil das in einem Array keinen Unterschied macht.

Es sind beides Mathematisch gesehen O(n²) Funktionen.

 

[chris1791]

Hi Meister, das stimmt nicht. Wenn du beide Codes durchlaufen läßt und mit start-stop variablen die laufzeit stoppst dann ist der zeilenweise durchlauf fast 3x schneller! Und ich muss argumentieren: Warum das so ist!

 

[JavaMeister]

Weil dein PC keine Nanosekunden auflösen kann. Solche Micro Benchmarks sind nicht aussagekräftig.

Beachte bitte das mathematische Lemma.

 

[Thallius]

Das liegt daran wie so ein array im Speicher organisiert ist.

a[2][2] liegt so im Speicher

a[0][0], a[0][1], a[1][0],a[1][1]

Wenn ich nun deine erste Schleife durchiteriere, dann kann ich einfach den Speicher hintereinander weglesen. Nehme ich die zweite Schleife, dann muss ich hin- und herspringen.

Genauso geht es auch dem Compiler/Interpreter.

Aus der ersten Schleife kann der Compiler einen ganz einfach optimierten durchlauf machen, der einfach den Speicher ausliest mit und dann den Pointer auf dem Speicher erhöht. Das ist ein wenig schwer zu erklären wenn man kein Assembler kann und kein ahnung von Pointern hat aber im Prinzip kann der Compiler aus der ersten Schleife eine Schleife machen die so aussieht

double zeigerAufDenEintrag=a[0][0]
while(zeigerAufDenEintrag!=a[1][1])
doubleWert=Inhalt(zeigerAufDenEintrag++)

Bei der zweiten Schleife geht das natürlich nicht.

Gruß

Claus

 

[chris1791]

Danke Claus!
Genau das habe ich mir gedacht.
Gruß Chris

 

[chris1791]

Hi JavaMeister,
Ich dachte auch dass, auf Grund dessen, dass die Anzahl der Durchläufe gleich ist, wäre es egal welche Schleife ich nehme. Aber es ist tatsächlich so wie Thallis das schreibt.
Danke Euch beiden.

Gruß. Chris