Schleife (weg)optimieren? Geschwindigkeitszuwachs gesucht.

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

Partner:

Forum

Option

[Erweitert]

• Diese Seite per Mail weiterempfehlen

Gehe zu:

pooz

Forum-Anfänger


	Beiträge: 49

	Anmeldedatum: 04.05.09

	Wohnort: ---

	Version: ---

Verfasst am: 11.01.2011, 10:39 Titel: Schleife (weg)optimieren? Geschwindigkeitszuwachs gesucht.

Hallo alle zusammen,
hoffe, ich bin hier im richtigen Unterforum, wenn es um das Thema Optimierung / Geschwindigkeitszuwachs geht.

Wie kann ich die folgende Schleife loswerden, damit das ganze nicht so lange dauert?

Code:

timeMax = 588;
myLen = 1024;
xframe = -1 + 2.* rand(1,myLen+timeMax); % Zahlen aus [-1; 1]
myData = zeros(1,timeMax);

tic
for t = 1:timeMax
myData(t) = sum( (xframe(1:myLen) - xframe((1:myLen)+t)).^2 );
end
toc

Funktion ohne Link?

Besten Dank!!
Po²z

Jan S

Moderator


	Beiträge: 11.057

	Anmeldedatum: 08.07.10

	Wohnort: Heidelberg

	Version: 2009a, 2016b

Verfasst am: 11.01.2011, 23:37 Titel: Re: Schleife (weg)optimieren? Geschwindigkeitszuwachs gesuch

Hallo pooz,

Ich komme auf Anhieb nur eine kleine Änderung, aber unter Matlab 2009a ist es zumindest 4 mal schneller:

Code:

timeMax = 588;
myLen = 1024;
xframe = -1 + 2.* rand(1,myLen+timeMax); % Zahlen aus [-1; 1]
myData = zeros(1,timeMax);

tic
v = xframe(1:myLen);
for t = 1:timeMax
myData(t) = sum((v - xframe(1+t:myLen+t)) .^ 2 );
end
toc

Funktion ohne Link?

Bei "xframe(1+t:myLen+t)" wird der Index-Vektor gar nicht explizit ausgerechnet, während bei "xframe((1:myLen)+t)" zunächst der Vektor "1:myLen" erstellt wird, und dann t dazu addiert. Schließlich wird beim Indizieren für jedes Element geprüft, ob es im erlaubten Bereich liegt. Bei "xframe(1+t:myLen+t)" wird dagegen nur für den ersten und letzten Index getestet, ob die Werte überhaupt im Vektor liegen.

Noch schneller, aber mit minimal anderem Ergebnis (+-EPS):

Code:

v = xframe(1:myLen);
for t = 1:timeMax
w = v - xframe(1+t:myLen+t);
myData(t) = w * w.';
end

Funktion ohne Link?

SUM(X.^2) ist das gleiche wie DOT(X, X), dass mit X*X' noch schneller berechnet wird.

Zeiten: Deine Methode: 0.046 sec, effizienterer Index: 0.012 sec, w*w': 0.009 sec.

Gruß, Jan

pooz

Themenstarter

Forum-Anfänger


	Beiträge: 49

	Anmeldedatum: 04.05.09

	Wohnort: ---

	Version: ---

Verfasst am: 12.01.2011, 11:43 Titel:

Hallo Jan,

super! Vielen Dank. In der Tat bringt es bei mir eine Geschwindigkeitserhöhung um Faktor 3.5 - 4.0 !
Der Punkt mit der Indizierung war mir überhaupt nicht bewusst! Und mit dem Punktprodukt bin ich jetzt auch up-to-date Smile

. Danke dafür!

2 Fragen bleiben noch:
- Was ist der Unterschied zwischen " w.' " (mit Punkt) und " w' " (ohne Punkt) ?

- Ist es möglich, die Schleife ganz weg zu bekommen?
Zu diesem Thema hab ich versucht durch Umformungen und amateurartiger Linearer Algebra einen anderen Ansatz zu verfolgen.
Mein erster Ansatz, diese Schleife wegzubekommen, scheitert noch an einer kleinen Umformung, die du in diesem Thread bereits gesehen hast.

Besten Dank für deine Hilfe!
Gruß
Pooz

Jan S

Moderator


	Beiträge: 11.057

	Anmeldedatum: 08.07.10

	Wohnort: Heidelberg

	Version: 2009a, 2016b

Verfasst am: 13.01.2011, 01:34 Titel:

Hallo pooz,

Zitat:

- Was ist der Unterschied zwischen " w.' " (mit Punkt) und " w' " (ohne Punkt) ?

help transpose
help ctranspose

Zitat:

Mein erster Ansatz, diese Schleife wegzubekommen, scheitert noch an einer kleinen Umformung, die du in diesem Thread bereits gesehen hast.

Ich habe dort den sehr schnellen BUFFER-Befehl gepostet. Allerdings bleibt der Nachteil, dass eine große temporäre Matrix erzeugt wird, die eine Menge redundante Daten enthält. Deswegen gehe ich davon aus, dass die FOR-Schleife im Endeffekt schneller ist, wenn die Matrix eine gewisse Größe überschreitet. Diese Größe hängt von der Größe Deines Prozessorcaches ab, also etwa im zweistelligen kB-Bereich.

Gruß, Jan

pooz

Themenstarter

Forum-Anfänger


	Beiträge: 49

	Anmeldedatum: 04.05.09

	Wohnort: ---

	Version: ---

Verfasst am: 13.01.2011, 11:07 Titel:

Vielen Dank, Jan,

mit beiden Hilfestellungen (hier und der andere Thread) komme ich auf nun auf mein Ziel zu, das ganze noch schneller machen zu wollen.
Mit Hilfe des anderen Threads, möchte ich nun die Schleife aus meinem Ausgangsproblem bzw. aus deiner äußerst guten, optimierten Version entfernen.

Folgende sehr einfache Idee habe ich:

Betrachten wir die Operation an sich,

Code:

v = xframe(1:myLen);
for t = 1:timeMax
myData(t) = sum((v - xframe(1+t:myLen+t)) .^ 2 );
end

Funktion ohne Link?

so wird vom Vektor xframe lediglich seine um t verschobene Version subtrahiert, quadriert und aufsummiert.

Meine neue Idee lautet nun:
Die Subtraktion könnte ich doch aber auch in Matrix-Form EINMAL durchführen, und so die Schleife sparen?
So siehts aus (Pseudocode):

Code:

xframe = [ x1 x2 x3 x4 x5 x6 x7];
R =
x1 x2 x3 x4
x1 x2 x3 x4
x1 x2 x3 x4

A =
x2 x3 x4 x5
x3 x4 x5 x6
x4 x5 x6 x7

C = R-A

Funktion ohne Link?

Jetzt müsste ich nur noch "lediglich" quadrieren und aufsummieren.
Das habe ich gemacht, schleife ist weg, allerdings ist es langsamer als mit Schleife. Merkwürdig. Geht es zu oprimieren?

Hier alles zusammen als Code zum Messen und Probieren:

Code:

% Vorbereitung
clc, clear all
timeMax = 588;
myLen = 1024;
myData3 = zeros(1,timeMax);
myData4 = zeros(1,timeMax);
xframe = (1:timeMax+myLen)+100; % Beispiel Vektor

% Vorbereitungen für die kopierte (R) als auch für die versetzte (A) Matrix
% (kann übersprungen werden)
[v_pos, s_pos] = meshgrid(1:myLen,1:timeMax);
v_pos = v_pos + s_pos;
n_pos = repmat((1:myLen),timeMax,1);

% Referenz
disp('Index explizit & Skalarprodukt')
tic
v2 = xframe(1:myLen);
for t = 1:timeMax
w = v2 - xframe(1+t : myLen+t);
myData3(t) = w * w.';
end
toc

% Oprimierungsversuch
disp('Versuch ohne Schleife')
tic
R = xframe(n_pos); % xframe-Elemente kopiert
A = xframe(v_pos); % xframe-Elemente um 1 pro Zeile versetzt
C = R-A; % Vektor-Subtraktion ohne Schleife!
myData4 = sum(C.^2,2)'; % Aufsummieren und Quadrieren entlang der Zeilen
toc

Funktion ohne Link?

Für jeden Tip wäre ich äußerst Dankbar!
Pooz

Jan S

Moderator


	Beiträge: 11.057

	Anmeldedatum: 08.07.10

	Wohnort: Heidelberg

	Version: 2009a, 2016b

Verfasst am: 14.01.2011, 13:08 Titel:

Hallo pooz,

Versuche mal dies:

Code:

myData4 = sum(C.^2,2)';
% ==>
myData4 = C * C'; % Oder vielleicht C' * C ?

Funktion ohne Link?

Wieder wäre das das Dot-Produkt statt SUM(X.^2).
Aber ein Nachteil bleibt: Die entstehenden Matrizen sind groß und enthalten redundante Daten. Das Reservieren von viel RAM ist meist deutlich zeitraubender, als kleine Arrays, die in den Prozessor-Cache passen immer wieder mit einem neuen Index auszulesen.

Ein C-Mex-File würde die Schleife nochmal deutlich beschleunigen. Aber wie immer muss man beim Lauf-Zeit-Optimieren abwägen: Es lohnt sich nicht, 2 Stunden zu investieren, damit das Programm 2 Minuten schneller läuft. Den ausschlaggebend ist die "Programmzeit", also die Zeit bis zum Vorliegen des Ergebnisses:

Code:

Programmzeit = Programmierzeit + Debugzeit + Laufzeit

Funktion ohne Link?

In Matlab sind die ersten beiden im Allgemeinen sehr niedrig, während die Laufzeit meistens nur mittelmäßig ist. In C kann man dagegen viele Probleme in wenigen Sekunden lösen, braucht aber beim kleinsten Fehler schon mal ein paar Tage zum Debuggen.

Gruß, Jan

pooz

Themenstarter

Forum-Anfänger


	Beiträge: 49

	Anmeldedatum: 04.05.09

	Wohnort: ---

	Version: ---

Verfasst am: 14.01.2011, 13:26 Titel:

Hi Jan,

vielen Dank.
Das habe ich schon probiert. Dachte nämlich, ich wäre mal schlau und übernehme gleich das, was ich von dir gelernt hab. Pustecake. Dauert bei Matrizen länger, liefert die von die besagten redundanten Werte und das zugehörige Auslesen der Diagonalelemente legt noch ein Tüpfelchen an Zeitverbrauch oben drauf. Hm...schade...

Deine Faustregel zur adäquaten Programmierzeitinvestition hab ich nicht ganz verstanden auf Anhieb. Ich müsste nochmal drüber nachdenken, was du meinst.
Kann mir aber vorstellen, dass du den Optimierungsaufwand dem Gewinn gegenüberstellen möchtest.

Gruß
Pooz


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