Verfasst am: 17.09.2010, 14:27
Titel: Berechnung in Schleife schneller als Matrizenrechnung
Hallöchen!
Ich wollte letztens mein Programm optimieren und dachte, dass ich doch eine Schleife durch eine Berechnung mit Matrizen ersetzen könnte um dadurch Rechenzeit einzusparen. Jedoch ist das Gegenteil der Fall! Die Berechnung mit Matrizen braucht doppelt solange wie die Berechnung mit der Schleife!
Wie kommt das und welche Möglichkeiten gibt es doch noch Zeit einzusparen?
Ich denke es liegt daran, dass man in der Schleife immer nur eine Spalte aus der Matrix Q ausliest und bei der Matrizenrechnung gleich i-1 Spalten ausgelesen werden und diese Untermatrix extra in den Speicher geladen wird.
Wenn man die Dimensionen verkleinert (also n und k), dann ist die Matrixberechnung schneller!
z.B. bei meinem Rechner:
n = 1000;
k = 50;
Zeit Matrizenrechnung: Elapsed time is 0.008858 seconds.
Zeit Schleifenrechnung: Elapsed time is 0.019846 seconds.
Code:
function test_Orthogonalisierung
clc;
n = 5000;
k = 50;
A = rand(n,k);
tic
Q(:,1) = A(:,1)/norm(A(:,1));
for i = 2:k
v = A(:,i);
v = orthov(v,Q,i);
Q(:,i) = v/norm(v);
end toc % Ausgabe: Elapsed time is 0.102404 seconds. norm(Q'*Q-eye(k))
tic
Q(:,1) = A(:,1)/norm(A(:,1));
for i = 2:k
v = A(:,i);
v = orthov_loop(v,Q,i);
Q(:,i) = v/norm(v);
end toc % Ausgabe: Elapsed time is 0.045078 seconds. % D.h. die Schleife braucht ca. die Hälfte der Zeit!!!! norm(Q'*Q-eye(k))
Hab das gerade mal versucht, nachzuvollziehen, bin aber nicht so weit gekommen. Ich kann dir nur 3 Dinge sagen:
1.) So kleine Zeitmessungen (< 2 sec) sind immer sehr ungenau und gefährlich. Am besten andere Parameter für längere Berechnungen zum Vergleich benutzen, oder das, was du timen willst, mehrfach in einer weiteren Schleife ausführen lassen!
Man weiß nie genau, was im Hintergrund noch für I/O und CPU-Sachen im Betriebssystem laufen, ob MATLAB alle Funktionen im Cache hat usw.
2.) Nur die Walltime (also echte Zeit, tic, toc) anzuschauen ist auf Multicore-CPUs auch "gefährlich". Zwar interessiert dich im Endeffekt genau diese Zeit (aka "wie lange dauert es eigentlich"), es hilft aber auch, sich zusätzlich noch die benötigte Rechenzeit anzugucken (merke dir vorher cputime() und hinterher, und vergleiche). Dann sieht man auch, wie parallelisiert der Code war.
3.) Nutz den Profiler. Der ist wunderbar für genau solche Fälle. Einfach, wenn deine Funktion im Editor ist, unter "Tools", "Open Profiler" auswählen. Das zeigt dir worans liegt!
_________________
1. Natürlich kann man durch geschickten Code Performance gewinnen, aber sehr, sehr häufig wird viel mehr gerechnet als für die Lösung einer Aufgabe nötig ist (Messwerte liegen in DOUBLE und 1 ms Takt vor - die muss ich nutzen, selbst wenn das System das ich identfizieren will eine Zeitkonstante von 1 Minute hat ) - nun gut, hier werden keine Messwerte verrechnet und ich schliesse mich der Aussage zu den kleinen Rechenzeiten an.
2. Ja, Schleifen können schneller sein. Ja, MATLAB kann auch schneller als C-Code sein. Wenn ich die Top 10 "Mythen" über MATLAB zusammentragen wollte gehört bestimmt dazu, dass man Schleifen vermeiden muss.
Verfasst am: 17.09.2010, 23:43
Titel: Re: Berechnung in Schleife schneller als Matrizenrechnung
Hallo Beckster07,
ich habe einiges versucht, aber die Schleifen-Method ist unter modernen Matlab Versionen wirklich schnell. Mit einer kleinen Modifikation kann man weitere 10% Rechenzeit sparen:
Code:
function test_Orthogonalisierung
n = 5000;
k = 50;
A = rand(n,k);
tic for k = 1:100
Q(:,1) = A(:,1)/norm(A(:,1));
for i = 2:k
v = A(:,i);
v = orthov(v,Q,i);
Q(:,i) = v/norm(v);
end end toc
tic for k = 1:100
Q(:,1) = A(:,1)/norm(A(:,1));
for i = 2:k
v = A(:,i);
v = orthov_loop(v,Q,i);
Q(:,i) = v/norm(v);
end end toc
% 10% faster tic for k = 1:100
Q(:,1) = A(:,1)/norm(A(:,1));
for i = 2:k
v = A(:,i);
v = orthov_loop_2(v,Q,i);
Q(:,i) = v/norm(v);
end end toc
% Some further percent faster with inlined loop: tic for k = 1:100
Q(:,1) = A(:,1)/norm(A(:,1));
for i = 2:k
v = A(:,i);
for j = 1:i-1
q = Q(:, j);
v = v - q * (q' * v);
end
Q(:,i) = v/norm(v);
end end toc
%=============================================
function v = orthov(v,Q,i)
h = Q(:,1:i-1)'*v;
v = v - Q(:,1:i-1)*h;
function v = orthov_loop(v,Q,j) for i = 1:j-1
h = Q(:,i)'*v;
v = v - Q(:,i)*h;
end
function v = orthov_loop_2(v,Q,j) for i = 1:j-1
q = Q(:, i);
v = v - q * (q' * v);
end
Die Schleife aus der Unterfunktion in die Hauptschleife einzubauen bringt nochmal ein paar Prozente, da der Aufruf einer Unterfunktion immer Zeit kostet.
Unter Matlab 6.5 sieht das auch ganz interessant aus:
orthov: 2.18 sec
orthov_loop: 3.7 sec (daher die Meinung, dass Matrizen schneller sind!)
orthov_loop_2: 0.99 sec (aha! Der JIT-Accelerator schlägt zu!)
inlined orthov_loop_2: 0.94 sec
Hoffentlich bearbeitest Du wirklich große Matrizen damit. Ansonsten hatr Dich das Schreiben im Forum dann doch wieder mehr Zeit gekostet, als das Optimieren wieder einbringt. Das ist das alte Problem:
Programmzeit = Programmierzeit + Debugzeit + Laufzeit
Eine Laufzeit-Optimierung sorgt nicht unbedingt dafür, dass die Ergebnisse früher fertig sind...
Gruß, Jan
Gast11
Gast
Beiträge: ---
Anmeldedatum: ---
Wohnort: ---
Version: ---
Verfasst am: 02.08.2011, 08:08
Titel: Re: Berechnung in Schleife schneller als Matrizenrechnung
Beckster07 hat Folgendes geschrieben:
Hallöchen!
Ich wollte letztens mein Programm optimieren und dachte, dass ich doch eine Schleife durch eine Berechnung mit Matrizen ersetzen könnte um dadurch Rechenzeit einzusparen. Jedoch ist das Gegenteil der Fall! Die Berechnung mit Matrizen braucht doppelt solange wie die Berechnung mit der Schleife!
Wie kommt das und welche Möglichkeiten gibt es doch noch Zeit einzusparen?
Ich denke es liegt daran, dass man in der Schleife immer nur eine Spalte aus der Matrix Q ausliest und bei der Matrizenrechnung gleich i-1 Spalten ausgelesen werden und diese Untermatrix extra in den Speicher geladen wird.
Wenn man die Dimensionen verkleinert (also n und k), dann ist die Matrixberechnung schneller!
z.B. bei meinem Rechner:
n = 1000;
k = 50;
Zeit Matrizenrechnung: Elapsed time is 0.008858 seconds.
Zeit Schleifenrechnung: Elapsed time is 0.019846 seconds.
Hallo,
wenn mich meine Glasaugen nicht trügen, dann hast du folgendes
Elapsed time Matrizenr. < Elapsed time Schleifenr. oder sind
0.008x sec > 0.019x sec ???
Du kannst Beiträge in dieses Forum schreiben. Du kannst auf Beiträge in diesem Forum antworten. Du kannst deine Beiträge in diesem Forum nicht bearbeiten. Du kannst deine Beiträge in diesem Forum nicht löschen. Du kannst an Umfragen in diesem Forum nicht mitmachen. Du kannst Dateien in diesem Forum posten Du kannst Dateien in diesem Forum herunterladen
MATLAB, Simulink, Stateflow, Handle Graphics, Real-Time Workshop, SimBiology, SimHydraulics, SimEvents, and xPC TargetBox are registered trademarks and The MathWorks, the L-shaped membrane logo, and Embedded MATLAB are trademarks of The MathWorks, Inc.
) - nun gut, hier werden keine Messwerte verrechnet und ich schliesse mich der Aussage zu den kleinen Rechenzeiten an.
RSS