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

Performance bei Schleifen verbessern
 

LordExcalibur
Forum-Anfänger

Forum-Anfänger

Beiträge: 39
Anmeldedatum: 08.05.10
Wohnort: ---
Version: ---
     Beitrag Verfasst am: 04.10.2012, 21:20     Titel: Performance bei Schleifen verbessern
  Antworten mit Zitat      
Hallo,

ich habe ein kleines Skript geschrieben um einen Binomialbaum zu erstellen.

Den Code habe ich hier (etwas gekürzt) eigefügt:

Code:
function tree=bintree(treedepth)

% Variablen
 % Tree:
   % Zeile ist Index des Nodes;
   % Spalten: lson|rson|father|depth
     % lson: Index des linken Sohns (0 für Blattknoten)
     % rson: Indes des rechten Sohns (0 Für Blattknoten)
     % father: Index des Vaters (0 für Wurzel)
     % depth: Knotentiefe

% Variablen initialisieren
cnode=1; % Current Node (Aktueller Knoten)
cdepth=1; % Current Depth (Aktuelle Ebene)
 
   
% Binomialbaum erstellen
 
 for cdepth=1:treedepth % Für alle Ebenen des Baums
     enode=cnode+2^(cdepth-1)-1; % Letzter Knoten in Ebene
     
     for cnode=cnode:enode   % Für alle Knoten der Ebene
        if cdepth<treedepth % Prüfung auf Blattknoten
            lson=cnode*2;
            rson=cnode*2+1;
        else % Blattknoten
            lson=0;
            rson=0;
        end
        father=fix(cnode/2);
        tree(cnode,:)=[lson,rson,father,cdepth]; % Knoten erstellen tree(lson|rson|father|depth)
        cnode=cnode+1;
     end % for
     
   cdepth=cdepth+1;
 end
 
end
 


Das Problem ist, dass die Perfomance etwas zu wünschen übrig lässt. Ich muss einen Baum mit einer Tiefe von 24 erstellen. Das dauert bei mir am Rechner einige Minuten. Mir ist klar, dass der Baum 2^24 Knoten hat und daher schon sehr groß ist, aber vielleicht gibt es ja hier noch etwas Optimierungspotential.

Viele Grüße.
Sebastian
Private Nachricht senden Benutzer-Profile anzeigen


dmjr
Forum-Century

Forum-Century

Beiträge: 199
Anmeldedatum: 02.10.12
Wohnort: ---
Version: ---
     Beitrag Verfasst am: 05.10.2012, 00:15     Titel:
  Antworten mit Zitat      
Bevor du dir über die Performance gedanken machst sollte der Code erstmal korrekt sein.

Diese beiden Zeile dürften zu viel sein:
cnode=cnode+1;
cdepth=cdepth+1;
Die Variablen werden schon jeweils durch die Schleife selbst hochgesetzt.

Ansonsten kannst du tree noch preallokieren (vor der ersten Verwendung in der richtigen Größe erstellen):
tree = zeros(treedepth,4)
Private Nachricht senden Benutzer-Profile anzeigen
 
Harald
Forum-Meister

Forum-Meister

Beiträge: 24.501
Anmeldedatum: 26.03.09
Wohnort: Nähe München
Version: ab 2017b
     Beitrag Verfasst am: 05.10.2012, 00:39     Titel:
  Antworten mit Zitat      
Hallo,

als erstes sollte man sich die Warnungen von Code Analyzer ansehen, um ein Programm zu verbessern.

Hier würde ich das aber vollkommen anders angehen: die einzelnen Spalten haben ja eine relativ leicht erstellbare Struktur. Man muss den Baum also nicht explizit Stück für Stück erstellen, sondern kann die Spalten auf einen Schlag erzeugen.

Code:
function t = bintree2(treedepth)

powtd = 2^treedepth;
t = zeros(powtd-1, 4);
t(1:powtd/2-1,1) = 2:2:(powtd-2);
t(1:powtd/2-1,2) = 3:2:(powtd-1);
t(:,3) = [0; reshape(repmat(1:powtd/2-1, 2, 1),[],1)];
for I = 1:treedepth
    t(2^(I-1):2^(I)-1,4) = I;
end


Ich komme bei treedepth=24 auf 2,2 Sekunden. Smile
Mit etwas Geschick kann man vielleicht noch mehr rausholen.

Grüße,
Harald
Private Nachricht senden Benutzer-Profile anzeigen
 
LordExcalibur
Themenstarter

 Forum-Anfänger

Forum-Anfänger

Beiträge: 39
Anmeldedatum: 08.05.10
Wohnort: ---
Version: ---
     Beitrag Verfasst am: 05.10.2012, 10:19     Titel:
  Antworten mit Zitat      
dmjr hat Folgendes geschrieben:
Bevor du dir über die Performance gedanken machst sollte der Code erstmal korrekt sein.

Diese beiden Zeile dürften zu viel sein:
cnode=cnode+1;
cdepth=cdepth+1;
Die Variablen werden schon jeweils durch die Schleife selbst hochgesetzt.



Wenn ich die beiden Zeilen auskommentiere bekomme ich ein falsches Ergebnis als Output. Konkret fehlen Zeilen in der Ergebnismatrix.
Private Nachricht senden Benutzer-Profile anzeigen
 
LordExcalibur
Themenstarter

 Forum-Anfänger

Forum-Anfänger

Beiträge: 39
Anmeldedatum: 08.05.10
Wohnort: ---
Version: ---
     Beitrag Verfasst am: 05.10.2012, 11:12     Titel:
  Antworten mit Zitat      
Harald hat Folgendes geschrieben:
Hallo,

als erstes sollte man sich die Warnungen von Code Analyzer ansehen, um ein Programm zu verbessern.

Hier würde ich das aber vollkommen anders angehen: die einzelnen Spalten haben ja eine relativ leicht erstellbare Struktur. Man muss den Baum also nicht explizit Stück für Stück erstellen, sondern kann die Spalten auf einen Schlag erzeugen.

Code:
function t = bintree2(treedepth)

powtd = 2^treedepth;
t = zeros(powtd-1, 4);
t(1:powtd/2-1,1) = 2:2:(powtd-2);
t(1:powtd/2-1,2) = 3:2:(powtd-1);
t(:,3) = [0; reshape(repmat(1:powtd/2-1, 2, 1),[],1)];
for I = 1:treedepth
    t(2^(I-1):2^(I)-1,4) = I;
end


Ich komme bei treedepth=24 auf 2,2 Sekunden. Smile
Mit etwas Geschick kann man vielleicht noch mehr rausholen.


Das funktioniert schon sehr gut. Dauert bei mir zwar etwas mehr als 2,2s ist aber um ein Vielfaches schneller wie die Schleife.

Was mir noch nicht ganz klar ist, wie genau die 3. Spalte geschrieben wird. Das Ergebnis ist korrekt, ich kann deinem Programmcode an dieser Stelle jedoch nicht ganz folgen.


Jetzt geht das ganze weiter. Vielleicht könnt ihr mir hier schonmal ein paar Performancetips geben bevor ich mit der Implementierung anfange.
Es geht darum jedem Knoten noch 2 weitere Parameter zuzuweisen. Zum einen sind das die Kosten für den vorangegangenen Pfad. Diese hängen zum einen von der Entscheidung (Pfadwahl) ab, also davon ob der aktuelle Knoten der linke oder der rechte Sohn ist und zum anderen von dem aktuellen Preis (der wird separat modelliert).
Der zweite Parameter hängt ebenfalls von der Pfadwahl sowie von der Historie eines anderen Paramters ab (wird auch separat berechnet).

Ich gehe davon aus, dass ich hier nicht drum herrumkomme den Baum einmal komplett zu durchlaufen, oder lassen sich solche Entscheidungen und Berechnungen auch vektorisieren?
Private Nachricht senden Benutzer-Profile anzeigen
 
Harald
Forum-Meister

Forum-Meister

Beiträge: 24.501
Anmeldedatum: 26.03.09
Wohnort: Nähe München
Version: ab 2017b
     Beitrag Verfasst am: 05.10.2012, 11:20     Titel:
  Antworten mit Zitat      
Hallo,

zur dritten Spalte am Beispiel mit treedepth = 3:

Erst die 0, dann die Zahlen von 1 bis 7 je 2 Mal.

Also
1 2 ... 7

wird zu
1 2 ... 7
1 2 ... 7

wird umgewandelt in einen Vektor
1
1
2
2
...
...
7
7


Implementier das doch erst mal so. Wenn man dann ein bestimmtes Muster in diesen Kosten erkennt, kann man sehen, wie man das wiederum effizienter erstellen kann.

Grüße,
Harald
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 - 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.