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

12

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
TensoR
quelle
4
ForSchleifen sind in MATLAB sehr langsam. Sie sollten explizite Schleifen in MATLAB nach Möglichkeit vermeiden. Stattdessen kann ein Problem normalerweise in Form von Matrix- / Vektoroperationen ausgedrückt werden. Das ist der MATLABIC-Weg. Es gibt auch eine Menge eingebauter Funktionen zum Initialisieren von Matrizen usw. Beispielsweise gibt es eine Funktion ones () , die alle Elemente einer Matrix auf 1 setzt (durch Erweiterung, durch Multiplikation auf einen beliebigen Wert) (einen Skalar) multipliziert mit der All-Ones-Matrix)). Es funktioniert auch auf 3-D-Arrays (was meines Erachtens das Beispiel hier abdeckt).
Peter Mortensen
3
@PeterMortensen Um welchen Faktor (ungefähr) ist die Effizienz von Loops in Matlab im Vergleich zu C und Python geringer? Und warum ist das? Hat sich die Effizienz von Loops in Matlab in den letzten Jahren nicht verbessert?
TensoR
3
@PeterMortensen "normalerweise kann ein Problem in Form von Matrix- / Vektoroperationen ausgedrückt werden" - für bestimmte Werte von "normalerweise", ja. IMO ist es genauer zu sagen, dass die Leute, die in Matlab und dergleichen arbeiten, eine jahrzehntelange Kultur haben, all die Dinge zu ignorieren, die mit Matrix- / Vektoroperationen nicht möglich sind, so sehr, dass alles für sie wie ein Nagel für diesen Hammer aussieht . Und wir sollten nicht nur sagen, dass "for-Schleifen in Matlab langsam sind", sondern dass "Matlab langsam ist" (es ist nur zufällig mit einer schnellen Bibliothek von LA-Primitiven verknüpft, die in C und Fortran geschrieben sind).
links um den
5
Die Leistung von for-Schleifen ist umstritten: matlabtips.com/matlab-is-no-longer-slow-at-for-loops
ohreally
@ Linksaroundabout True. Die Sorge um die Geschwindigkeit in einer interpretierten (oder semi-interpretierten) Sprache ist ein ziemlich klarer Hinweis darauf, dass Sie ein XY-Problem haben, bei dem die eigentliche Lösung "Diese Sprache nicht verwenden" lautet. Die Ausnahme ist natürlich, wenn Sie die Codegenerierung in Simulink verwenden, aber dann ist die Frage, welches C der Codegenerator erstellt und wie effizient das ist.
Graham

Antworten:

18

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 .

whpowell96
quelle
2
Oder verwenden Sie die eingebauten Funktionen () .
Peter Mortensen
5
Das Beispiel von @Peter OP ist mit ziemlicher Sicherheit nur ein Spielzeugbeispiel für eine for-Schleife, die etwas bewirkt und nicht den tatsächlichen Anwendungsfall.
Matt
@Matt Du bist richtig.
TensoR
11

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.)

EIN

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.

Brian Borchers
quelle