Eine Matrix A[i][j] wird angegeben. Wenn wir die Elemente der Matrix hinzufügen wollen, welche Methode ist besser und warum?
Aus meiner Sicht ist zeilenweise besser, weil in Array-Darstellung Elemente in zusammenhängenden Speicherorten gespeichert sind, so dass der Zugriff auf sie weniger Zeit kostet. Aber da im RAM-Abruf jeder Ort die gleiche Zeit benötigt, ist das wichtig?
Profitieren Sie von Räumlicher Ort
In C werden Matrizen in r Großauftrag gespeichert. Wenn Sie also auf das Element a[i][j] zugreifen, wird wahrscheinlich ein Zugriff auf das Element a[i][j+1] den Cache treffen. Kein Zugriff auf den Hauptspeicher wird ausgeführt. Caches sind schneller als der Hauptspeicher, daher spielt das Zugriffsmuster eine Rolle.
Natürlich müssen mehr Faktoren berücksichtigt werden, wie z. B. Schreibzugriff / Lesezugriff, Schreibrichtlinie (durchschreiben, zurückschreiben / schreiben, reservieren, keine Schreibzuteilung), mehrstufige Caches und so weiter. Aber das scheint für diese Frage ein Overkill.
Machen Sie Spaß mit einem Profiling-Tool wie cachegrind und sehen Sie es sich selbst an.
>Betrachten Sie zum Beispiel ein Dummy-Programm, das auf 4-MB-Matrizen zugreift. Überprüfen Sie die Unterschiede zwischen den Fehltrefferraten für jedes Zugriffsmuster.
Spaltenzugriff
%Vor%Zeilenzugriff
%Vor%Wenn die Arrays klein sind, ist das nicht wichtig. Wenn sie groß sind, kann die Lesezeit beeinträchtigt sein. Das große Problem ist der Cache. Wenn Sie nicht erwarten können, dass Ihre komplette Matrix auf einmal in den Cache geladen wird, dann sollten Sie die Anzahl der Cache-Misses auf ein Minimum reduzieren, da der Umgang mit einem Cache-Miss relativ zeitaufwändig ist.
Wenn die Arrays wirklich groß sind, können Sie noch größere Performance-Treffer erzielen, indem Sie mehr Seitenwechsel durchführen als nötig.
Für C ist die beste Methode zur Behandlung mehrdimensionaler Arrays:
%Vor%Der Grund dafür ist, dass die C-Sprache Arrays als Zeiger mit Offsets behandelt, siehe: Die C-Programmiersprache .