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

Mein MATLAB Forum - goMatlab.de

Mein MATLAB Forum

 
Gast > Registrieren       Autologin?   

Partner:




Forum
      Option
[Erweitert]
  • Diese Seite per Mail weiterempfehlen
     


Gehe zu:  
Neues Thema eröffnen Neue Antwort erstellen

Schleife (weg)optimieren? Geschwindigkeitszuwachs gesucht.

 

pooz
Forum-Anfänger

Forum-Anfänger


Beiträge: 49
Anmeldedatum: 04.05.09
Wohnort: ---
Version: ---
     Beitrag Verfasst am: 11.01.2011, 10:39     Titel: Schleife (weg)optimieren? Geschwindigkeitszuwachs gesucht.
  Antworten mit Zitat      
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


Besten Dank!!
Po²z
Private Nachricht senden Benutzer-Profile anzeigen


Jan S
Moderator

Moderator


Beiträge: 11.057
Anmeldedatum: 08.07.10
Wohnort: Heidelberg
Version: 2009a, 2016b
     Beitrag Verfasst am: 11.01.2011, 23:37     Titel: Re: Schleife (weg)optimieren? Geschwindigkeitszuwachs gesuch
  Antworten mit Zitat      
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

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

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
Private Nachricht senden Benutzer-Profile anzeigen
 
pooz
Themenstarter

Forum-Anfänger

Forum-Anfänger


Beiträge: 49
Anmeldedatum: 04.05.09
Wohnort: ---
Version: ---
     Beitrag Verfasst am: 12.01.2011, 11:43     Titel:
  Antworten mit Zitat      
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
Private Nachricht senden Benutzer-Profile anzeigen
 
Jan S
Moderator

Moderator


Beiträge: 11.057
Anmeldedatum: 08.07.10
Wohnort: Heidelberg
Version: 2009a, 2016b
     Beitrag Verfasst am: 13.01.2011, 01:34     Titel:
  Antworten mit Zitat      
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
Private Nachricht senden Benutzer-Profile anzeigen
 
pooz
Themenstarter

Forum-Anfänger

Forum-Anfänger


Beiträge: 49
Anmeldedatum: 04.05.09
Wohnort: ---
Version: ---
     Beitrag Verfasst am: 13.01.2011, 11:07     Titel:
  Antworten mit Zitat      
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

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


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
 


Für jeden Tip wäre ich äußerst Dankbar!
Pooz
Private Nachricht senden Benutzer-Profile anzeigen
 
Jan S
Moderator

Moderator


Beiträge: 11.057
Anmeldedatum: 08.07.10
Wohnort: Heidelberg
Version: 2009a, 2016b
     Beitrag Verfasst am: 14.01.2011, 13:08     Titel:
  Antworten mit Zitat      
Hallo pooz,

Versuche mal dies:
Code:

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

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

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
Private Nachricht senden Benutzer-Profile anzeigen
 
pooz
Themenstarter

Forum-Anfänger

Forum-Anfänger


Beiträge: 49
Anmeldedatum: 04.05.09
Wohnort: ---
Version: ---
     Beitrag Verfasst am: 14.01.2011, 13:26     Titel:
  Antworten mit Zitat      
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
Private Nachricht senden Benutzer-Profile anzeigen
 
Neues Thema eröffnen Neue Antwort erstellen



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 | goMatlab RSS Button 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.