Was ist der effizienteste Weg, um in Matlab 'for'-Schleifen zu schreiben?

Ich habe gelesen, dass, wenn ich zum Beispiel eine Doppelschleife habe for, die über die Indizes einer Matrix läuft, es effizienter ist, die Spalte, die den Index ausführt, in die äußere Schleife zu setzen. Beispielsweise:

a=zeros(1000);
for j=1:1000
 for i=1:1000
  a(i,j)=1;
 end
end

Was ist der effizienteste Weg, um es zu codieren, wenn ich drei oder mehr forSchleifen habe?

Beispielsweise:

a=zeros(100,100,100);
for j=1:100
 for i=1:100
  for k=1:100
   a(i,j,k)=1;
  end
 end
end

Kurze Antwort, Sie möchten den Index ganz links in der innersten Schleife haben. In Ihrem Beispiel wären die Schleifenindizes k, j, i und die Arrayindizes i, j, k. Dies hängt damit zusammen, wie MATLAB die verschiedenen Dimensionen im Speicher ablegt. Weitere Informationen finden Sie unter # 13 dieses reddit-Beitrags .

Eine etwas längere Antwort, die erklärt, warum es effizienter ist, den Index am schnellsten zu ändern. Es gibt zwei wichtige Dinge, die Sie verstehen müssen.

Erstens speichert MATLAB (und Fortran, aber nicht C und die meisten anderen Programmiersprachen) Arrays im Speicher in "Spaltenhauptreihenfolge". Beispiel: Wenn A eine 2 × 3 × 10-Matrix ist, werden die Einträge in der Reihenfolge gespeichert

A (1,1,1)

A (2,1,1)

A (1,2,1)

A (2,2,1)

A (1,3,1)

A (2,3,1)

A (1,1,2)

A (2,1,2)

...

A (2,3,10)

Diese Wahl der Spalten-Hauptreihenfolge ist willkürlich - wir könnten einfach eine "Zeilen-Hauptreihenfolge" -Konvention übernehmen, und genau das wird in C und einigen anderen Programmiersprachen gemacht.

Die zweite wichtige Sache, die Sie verstehen müssen, ist, dass moderne Prozessoren nicht auf einen Speicherplatz gleichzeitig zugreifen, sondern "Cache-Zeilen" von 64 oder sogar 128 zusammenhängenden Bytes (8 oder 16 Gleitkommazahlen mit doppelter Genauigkeit) laden und speichern. zu einer Zeit aus dem Gedächtnis. Diese Datenblöcke werden vorübergehend in einem schnellen Speichercache gespeichert und bei Bedarf zurückgeschrieben. (In der Praxis ist die Cache-Architektur jetzt mit bis zu 3 oder 4 Ebenen des Cache-Speichers ziemlich kompliziert, aber die Grundidee lässt sich mit einem einstufigen Cache erklären, wie er früher auf Computern verwendet wurde.)

$A$

Wenn die Schleifen so verschachtelt sind, dass die innerste Schleife den Zeilenindex aktualisiert, wird auf die Array-Einträge in der Reihenfolge A (1,1), A (2,1), A (3,1), ... zugegriffen Wenn auf den ersten Eintrag A (1,1) zugegriffen wird, bringt das System eine Cache-Zeile, die A (1,1), A (2,1), ..., A (8,1) enthält, aus dem Hauptspeicher in den Cache . Die nächsten 8 Iterationen der innersten Schleife verarbeiten diese Daten ohne zusätzliche Hauptspeicherübertragungen.

Wenn wir die Schleifen alternativ so strukturieren, dass der Spaltenindex in der innersten Schleife variiert, wird auf die Einträge von A in der Reihenfolge A (1,1), A (1,2), A (1,3) zugegriffen ), ... In diesem Fall würde der erste Zugriff A (1,1), A (2,1), ..., A (8,1) aus dem Hauptspeicher in den Cache bringen, jedoch 7/8 von Diese Einträge würden nicht verwendet. Der Zugriff auf A (1,2) in der zweiten Iteration würde dann weitere 8 Einträge aus dem Hauptspeicher einbringen und so weiter. Wenn der Code in Zeile 2 der Matrix funktioniert, wird der Eintrag A (2,1) möglicherweise aus dem Cache entfernt, um Platz für andere benötigte Daten zu schaffen. Infolgedessen generiert der Code 8-mal so viel Verkehr wie erforderlich.

Einige optimierende Compiler können Schleifen automatisch umstrukturieren, um dieses Problem zu vermeiden.

Viele numerische lineare Algebra-Algorithmen für die Matrixmultiplikation und -faktorisierung können optimiert werden, um je nach Programmiersprache effizient mit dem Reihen- oder Spalten-Hauptordnungsschema zu arbeiten. Eine falsche Vorgehensweise kann die Leistung erheblich beeinträchtigen.