Zu viele Daten, Algorith. dauert zu lange, Optimierung?

WICHTIG: Der Betrieb von goMatlab.de wird privat finanziert fortgesetzt. - Mehr Infos...

Partner:

Forum

Option

[Erweitert]

• Diese Seite per Mail weiterempfehlen

Gehe zu:

Sco

Forum-Meister


	Beiträge: 699

	Anmeldedatum: 15.08.10

	Wohnort: Dundee

	Version: 2008a, 2010a

Verfasst am: 21.10.2010, 14:56 Titel: Zu viele Daten, Algorith. dauert zu lange, Optimierung?

Hallo,

habe folgendes Problem und wuerde mich ueber jegliche Hilfe sehr freuen.

Ich habe eine 250x250x8 Matrix. Nun moechte ich fuer jedes Wertepaar der ersten beiden Dimensionen (250x250) die 8 Punkte (letzte Dimension) linear fitten und daraus einen bestimmten Parameter ermitteln. Ich habe es bis jetzt so gemacht, wobei MAT die besagte Matrix ist:

Code:

fit_func = fittype('poly1');
paras = zeros(250,250);

for a = 1:250
for b = 1:250

[res_fit] = fit(1:8, squeeze(MAT(a,b,:)), fit_func);
paras(a,b) = -1/res_fit.p1;

end
end

Funktion ohne Link?

Das funktioniert soweit, ist jedoch aufgrund der benoetigten Dauer (3min) nicht praktikabel, zumal ich mehrere dieser Matrizen verarbeiten muss.

Wie kann ich die Schleifen rauswerfen, bzw. den 'Algorithmus' optimieren???

Vielen Dank fuer jegliche Hilfe!

MFG

Sco

Achi

Forum-Guru


	Beiträge: 250

	Anmeldedatum: 14.04.10

	Wohnort: ---

	Version: R2007a

Verfasst am: 21.10.2010, 15:10 Titel:

Version: 2008a, 2010a?

Dann dürfte doch die Parallel Comp Tool Box vorhanden sein?

for mit parfor austauschen dürfte schon was bringen wenn mehr als 1 Kern vorhanden ist.

Gruß Achi

Sco

Themenstarter

Forum-Meister


	Beiträge: 699

	Anmeldedatum: 15.08.10

	Wohnort: Dundee

	Version: 2008a, 2010a

Verfasst am: 21.10.2010, 16:33 Titel:

Hallo,

erstmal Danke fuer die Antwort. Hab das parfor mal probiert und die Hilfe studiert. Bei mir bricht es immer ab mit Fehlern:

Code:

??? Error using ==> fit at 254
Attempt to reference field of non-structure array.

Error in ==> parallel_function>distributed_execution at 725
[tags, out] = P.getCompleteIntervals(min(thisDispatchSize, j));

Error in ==> parallel_function at 564
R = distributed_execution(...

Error in ==> knee at 57 % ------> mein Programmname
parfor b=1:256

Funktion ohne Link?

Leider hab ich keine Idee woran es liegt.

Auch wenn ich nur eine einfache Schleife mit dem fit-Befehl verwende kommt der selbe Fehler.

MFG

Sco

mmz

Forum-Anfänger


	Beiträge: 48

	Anmeldedatum: 18.08.10

	Wohnort: ---

	Version: ---

Verfasst am: 21.10.2010, 16:40 Titel:

Hiho,

soweit ich weiß, hat man doch nicht automatisch mit version R2010b die Parallel Comp Tool Box oder? Und der Befehl parfor ist zwar vorhanden aber bringt ohne Toolbox kein geschwindigkeitszuwachs.

grüße

Michael

Sco

Themenstarter

Forum-Meister


	Beiträge: 699

	Anmeldedatum: 15.08.10

	Wohnort: Dundee

	Version: 2008a, 2010a

Verfasst am: 21.10.2010, 16:57 Titel:

Hallo,

ich hab die Toolbox, da Sie in der Toolboxliste steht und der Befehl:

Code:

matlabpool

Funktion ohne Link?

funktioniert, der ja davor gestartet werden muss.

MFG

Sco

Achi

Forum-Guru


	Beiträge: 250

	Anmeldedatum: 14.04.10

	Wohnort: ---

	Version: R2007a

Verfasst am: 21.10.2010, 16:58 Titel:

Ich kann da leider nicht weiterhelfen Sad

Müssen wir wohl auf Jan S warten Razz

Sco

Themenstarter

Forum-Meister


	Beiträge: 699

	Anmeldedatum: 15.08.10

	Wohnort: Dundee

	Version: 2008a, 2010a

Verfasst am: 21.10.2010, 19:58 Titel:

Hallo,

kurzer Zwischenstand. Habe den Code folgendermassen geaendert:

Code:

paras = zeros(250,250);

for a = 1:250
parfor b = 1:250

res_fit = polyfit(1:8, squeeze(MAT(a,b,:)), 1); % so geht auch parfor
paras(a,b) = -1/res_fit(2);

end
end

Funktion ohne Link?

Mit dem Befehl polyfit statt fit, ist das Ganze schonmal gute 60% schneller. Ausserdem ist so auch die Benutzung von parfor moeglich, was nochmal 16% brachte. Also bin ich fuer dieses spezielle Beispiel bei 50s (statt 3 min) angelangt. Jedoch immer noch recht langsam fuer das was ich machen moechte (teilweise haben die Bilder eine 800x800 Matrix, wo wir wieder bei 10 min waeren Crying or Very sad

).

Naja vieleicht faellt ja noch jemanden was ein.

Vielen Dank

MFG

Sco

Jan S

Moderator


	Beiträge: 11.057

	Anmeldedatum: 08.07.10

	Wohnort: Heidelberg

	Version: 2009a, 2016b

Verfasst am: 21.10.2010, 22:27 Titel:

Hallo Sco,

Dein Beispiel braucht bei mir ein TRANSPOSE(1:8) im Aufruf von POLYFIT.

Auf meinem Rechner braucht Dein Progamm 77.4 sec unter Matlab 2009a.

Eine vereinfachte Version von POLYFIT, die gleich nach der Berechnung von p=R\(Q'*y) beendet wird und ohne Aufrufe von WARNING (siehe "edit polyfit"), benötigt 2.6 sec. Schon mal ganz gut, auch wenn es mich etwas wundert. Da läßt sich wohl an POLYFIT noch einiges verbessern!

Die eigentliche Berechnung aus POLYFIT direkt in Dein Programm zu schieben bringt viel, da eine Menge Overhead vermieden wird:

Code:

% Inlined POLYFIT - Calculations are needed once only!!!
V = [transpose(1:8), ones(8, 1)]; % Vandermode matrix
[Q, R] = qr(V, 0);
QT = transpose(Q);

paras = zeros(250,250);
for b = 1:250
for a = 1:250
y = MAT(a, b, :);
p = R \ (QT * y(:));
paras(a, b) = p(2);
end
end
paras = -1.0 ./ paras; % Outside the loops

Funktion ohne Link?

Nun braucht's noch 0.33 sec.

Nebenbei habe ich die Schleifen über "a" und "b" vertauscht, weil dabei auf banachbarte Elemente der Arrays zugegriffen wird, da sie in der ersten Dimension stehen. Hier ist es wohl nicht so wichtig, aber grundsätzlich kann das nützlich sein.

Die doppelte Schleife ist aber sowieso unnötig, wenn man MAT in ein 2D-Array verwandelt:

Code:

MAT2 = transpose(reshape(MAT, 250*250, 8));
paras = zeros(62500, 1);
for a = 1:62500
p = R \ (QT * MAT(:, a));
paras(a) = p(2);
end
paras = reshape(-1.0 ./ paras, 250, 250);

Funktion ohne Link?

Bringt aber nicht viel mehr Geschwindigkeit.

Aber wenn man schon mal so weit ist, fällt auf, dass "R\(QT*MAT)" auch gleich mit einer Matrix "MAT" funktioniert! Also weg mit der Schleife:

Code:

MAT = reshape(MAT, 250*250, 8);

% Inlined POLYFIT:
V = [transpose(1:8), ones(8, 1)]; % Vandermode matrix
[Q, R] = qr(V, 0);
QT = transpose(Q);

p = R \ (QT * transpose(MAT));
paras = -1.0 ./ p(2, :);

Funktion ohne Link?

Nun komme ich auf 0.017 sec. Das ist immerhin 4500 mal schneller.
Für so kleine Probleme lohnt sich das Parallelisieren nicht, weil das Starten der Threads einen deutlichen Overhead hat.

Gruß, Jan

Sco

Themenstarter

Forum-Meister


	Beiträge: 699

	Anmeldedatum: 15.08.10

	Wohnort: Dundee

	Version: 2008a, 2010a

Verfasst am: 22.10.2010, 17:28 Titel:

Hallo Jan,

was soll ich da noch sagen, dass ist GROSSARTIG. Vielen Dank.
Man haette natuerlich auch einmal selbst auf die Idee kommen koennen in die polyfit Funktion rein zu schauen.... Aber mit dem Umformen der Matrix, da waer ich wohl nicht drauf gekommen.

Zitat:

Dein Beispiel braucht bei mir ein TRANSPOSE( 1:8 ) im Aufruf von POLYFIT

braucht es auch bei mir, war nur ein Minimalbeispiel und da hatte ich das ' vergessen.

Naja ich hoffe es gibt irgendwann nochmal ein Forum treffen oder so, weil mich wirklich interessieren wuerde wer hinter 'Jan S' steckt. Ausserdem hab ich dir ja schon ein Bier versprochen, was ich dann mal einloesen koennte Smile

.

MFG

Sco

Jan S

Moderator


	Beiträge: 11.057

	Anmeldedatum: 08.07.10

	Wohnort: Heidelberg

	Version: 2009a, 2016b

Verfasst am: 22.10.2010, 17:55 Titel:

Hallo Sco,

ich selbst war ganz schön erstaunt, dass sich da innerhalb von Matlab so viel mehr rausholen läßt. Im Grunde wird ja auch mit der beschleunigten Version nichts anderes ausgerechnet und die Orginal-Version enthält keine groben Fehler wie fehlende Pre-Allocation oder wirrer Einsatz von EVALs.
Ich konnte schon mal eine nur mäßig effiziente M-Funktion als C-Mex um den Faktor 100 beschleunigen (NCHOOSEK -> FEX:VChooseK). Aber Faktor 4500 bei reinem M-Code... :-)

Deshalb danke ich Dir sehr für dieses exzellente Beispiel. Ich werde es jedem Studenten als Übungsaufgabe geben, der behauptet, Matlab wäre lahm.

Wenn Du in Heidelberg bist, trinken wir einen Cider!

Gruß, Jan

Sco

Themenstarter

Forum-Meister


	Beiträge: 699

	Anmeldedatum: 15.08.10

	Wohnort: Dundee

	Version: 2008a, 2010a

Verfasst am: 22.10.2010, 18:14 Titel:

Hallo Jan,

Zitat:

ich selbst war ganz schön erstaunt, dass sich da innerhalb von Matlab so viel mehr rausholen läßt

ja vielleicht war das auch der Grund warum ich nicht auf die Idee kam mal in Polyfit reinzuschauen, weil man davon ausgeht das es die Mathworks Entwickler schon sehr gut (vielleicht nicht perfekt) optimiert haben.
Aber, dass man nur durch das Abschneiden der If Clauses und den wenigen anderen Zeilen (jedoch Zeitlich wohl eher unrelevant) einen Beschleunigungsfaktor von 13 erhaelt (2.4 vs. 30 sek) ist schon sehr erstaunlich. Der Rest ist dann aber wohl eher auf meine 'schlechte' Programierung zurueckzufuehren: Verwendung der function 'squeeze' in jedem Schleifendurchgang, und natuerlich die Loops. Dein reshape der Matrix, so dass

Code:

p = R \ (QT * transpose(MAT));

Funktion ohne Link?

auf diese Weise berechnet werden kann (ohne Schleifen) ist wohl der Mammutanteil der Beschleunigung (neben der Extraktion der relevanten Zeilen aus der Polyfit function, so dass Sie nicht jedesmal aufgerufen werden muss).

Zitat:

Deshalb danke ich Dir sehr für dieses exzellente Beispiel.

I lol'd. Naja wenn du schon keine Fragen stellt, muss man halt interessante Fragen kreiren Smile

.

Ne Spass beiseite, nochmals vielen Dank und noch einen schoenen Tag.

Wenn ich wirklich mal in Heidelberg sein sollte, sag ich bescheid (es ist jedoch recht weit weg, sowohl von Schottland als auch meinen urspruenglichen Wohnsitz in Deutschland (Leipzig)).

MFG

Sco

Harald

Forum-Meister


	Beiträge: 24.501

	Anmeldedatum: 26.03.09

	Wohnort: Nähe München

	Version: ab 2017b

Verfasst am: 22.10.2010, 20:11 Titel:

Hallo Sco,

man muss sich darüber im klaren sein, dass bei den in MATLAB enthaltenen Funktionen und den Toolboxen immer auch umfangreich auf fehlerhafte Eingabeparameter oder Sinnhaftigkeit bzw. Verwendbarkeit der Ergebnisse überprüft wird. In diesem Fall wird wohl die Konditionierung des dahinterliegenden Gleichungssystems überprüft.
Mit dem Profiler lässt sich leicht feststellen, dass <5% für die tatsächliche Berechnung der Lösung verwendet werden.
In diesem Fall wurde polyfit noch zusätzlich immer mit demselben Eingabeargument aufgerufen, und polyfit hatte den entsprechenden Aufwand für die QR-Zerlegung natürlich mehrfach.
Allerdings sind auch Mathworks-Programmierer keine perfekten Menschen. Wenn man also einen Bug oder eine Möglichkeit für eine signifikante Verbesserung ausgemacht hat, wäre es gut, sich mit den entsprechenden Anregungen (über die Webseite) an Mathworks zu wenden, damit dies berücksichtigt werden kann und andere Anwender später auch etwas davon haben.

Grüße,
Harald


Einstellungen und Berechtigungen
Beiträge der letzten Zeit anzeigen:	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

Impressum | Nutzungsbedingungen | Datenschutz | FAQ |

RSS

Hosted by:

Copyright © 2007 - 2025 goMatlab.de | Dies ist keine offizielle Website der Firma The Mathworks

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.