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

Effizienz eines Algorithmus

 

x4ecro
Forum-Anfänger

Forum-Anfänger


Beiträge: 13
Anmeldedatum: 10.09.10
Wohnort: ---
Version: ---
     Beitrag Verfasst am: 24.09.2010, 19:03     Titel: Effizienz eines Algorithmus
  Antworten mit Zitat      
Hallo liebe Community,

ich habe folgendes Problem. Ich habe eine FUnktion geschrieben, die einen Index errechnet. Wie sich dieser Index berechnet steht hier: http://www.wwk.forst.tu-muenchen.de.....nlinePublications/416.pdf

Er gibt also an, wie die räumliche Verteilung von Punkten im 2-dimensionalen Raum ist (von maximaler Klumpung = 0 über zufällige Verteilung =1 bis zu einem streng hexagonalen Muster 2.1419). Soweit so gut.

Nun ist es so, dass ich quasi Punkte erzeugen möchte, die genau einem gewissen Indexwert (bzw. einer Näherung daran) entsprechen. D.h. ich lege zwie Vektoren (X- und Y-Koordinaten) mit zufällig erzeugten Punkten an. Diese ergeben dann logischerweise stets einen Indexwert sehr nahe 1.
Nun gehe ich jeden Punkt durch, weise einen neuen Zufallswert zu und schaue, ob sich der Index in die Richtung verbessert, in die ich ihn gern haben möchte. Auch das funktioniert an sich tadellos. Da Problem ist nur, dass bei einer hohen Anzahl von Punkten und einem extremen Indexwert (als nahe 0 oder nahe 2.1) die Rechenzeit ins unermessliche steigt, da

a) Jeder Punkt bei jedem Durchlauf der while-Schleife verändert wird, unabhängig davon, ob er vll schon den Idealwert hatte und

b) somit natürlich nicht sichergestellt ist, dass der Punkt auch wirklich "verbessert" wird. Ist dies nicht der Fall, so wird der Punkt auf seinen vorherigen Wert zurückgesetzt.

Vor allem, wenn es dann nun noch um ein paar Nachkommastellen geht, dann wird diese Prozedur unerträglich lang.

Nun meine eigentliche Frage. Hat jemand eine Idee, wie man den Algorithmus effektiver gestalten könnte. Kann mir vll jemand ein Flowchart anbieten, dass ich dann umsetzen könnte, oder bestenfalls sogar ein wenig Quellcode?

Danke schonmal für eure Hilfe,

Robert

Hier der Code, der "Optimierungsfunktion"

Code:

% *****************************************************
% ***      Aggregation Index Control Funciton       ***
% ***                                               ***
% ***                Ver. 1.0                       ***
% ***               24-09-2010                      ***
% ***                                               ***
% ***             Robert Eckardt                    ***
% ***             B.Sc Geography                    ***
% ***    Friedrich Schiller University of Jena      ***
% ***                                               ***
% *****************************************************

%+ + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + +
% !!! IMPORTANT !!!
%  This program needs the function
%     - "aggregation index.m"
%  It should be stored within same folder as this one.
%+ + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + +

%+ + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + +
% A.) What will this function do?
%       1. Analyses the difference of the values between the actual
%          Aggregation Index and the designated Aggregation Index
%       2. Re-distributes the passed X- and Y- Vector Coordinate to fit the
%          designated Aggregation Index


%+ + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + +
% B.) Input
%     M - Matrix = Basis for the Distribution analysis
%     n - Number of points
%     r - Cell resolution
%  goal - Designated Aggregation index
%     v - Allowed variation from the goal index
% x_vec - Vector of the X-coordinates
% y_vec - Vector of the Y-coordinates
%+ + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + +

%+ + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + +
% C.) Output
% x_vec - Vector containing the new X-Coordinates
% y_vec - Vector containing the new Y-Coordinates
% index - acutal value of the Aggregatio Index after processing
%+ + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + +

function [x_vec, y_vec, index] = index_control(M,n,r,goal,v,x_vec, y_vec)

%wb = waitbar(0,'Generating Point Distribution'); % initialize waitbar

dim_x= size(M,1);  %x-dimensions of the matrix    
dim_y= size(M,2);  %y-dimensions of the matrix
h=1; % control variable
     
% Estimation of the initial Aggregation index of the input points
%--------------------------------------------------------------------------
 index= aggregation_index(M,n,r,x_vec,y_vec)  
%--------------------------------------------------------------------------
   
while abs(index-goal) > v % while condition not fullfilled move re-distribute points    
   

for j=1:n % Movind every single point after the other
   
    index_old=index; % set the actual index to the old value
     x_vec_backup= x_vec; % store the x-coordinates from the loop before
     y_vec_backup= y_vec; % store the y-coordinates from the loop before
   
   
    diff_old= abs(index-goal); %Diffence of indices from the loop before
   
    %new, random assignment of point j
     x_vec(1,j)=(dim_x)*rand(1);
     y_vec(1,j)=(dim_y)*rand(1);
   
 %Recalculation of the Index    
 index= aggregation_index(M,n,r,x_vec,y_vec)
 
 
 diff_new= abs(index-goal); %Diffence of indices afte the new point was set

 %If the difference between actual index and designated index is increased,
 %keep the old value, else take the new value for point j to the next loop
 %-------------------------------------------------------------------------
 if diff_old<diff_new
     index=index_old;
     x_vec(1,j)=x_vec_backup(1,j);
     y_vec(1,j)=y_vec_backup(1,j);
 end
 %-------------------------------------------------------------------------
 
 %waitbar(1-abs(index-goal),wb);  % proceeding waitbar
 i_array(j)=index; % store the index development to an array
end
h=h+1; % increment control variable
end
%close(wb); % close waitbar
 index = index; % return final index
 x_vec = x_vec; % return new X-Coordinates
 y_vec = y_vec; % return nex Y-Coordinates
 
 
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: 24.09.2010, 19:40     Titel:
  Antworten mit Zitat      
Hallo,

ausgehend von dem momentanen Algorithmus würde ich vorschlagen zu vektorisieren.
Um hier einen Rat zu geben, müsste man etwas mehr über typische Eingabeargumente - vor allem die Dimensionen von M und n - wissen.
Ich würde auch mal den Profiler drüber laufen lassen um zu sehen, wo die Funktion die meiste Zeit verbraucht.

Noch was: wäre es eine Möglichkeit, die Punkte nach einer Weile nicht vollkommen neu zu erzeugen, sondern nur in einem gewissen, im Laufe der Zeit kleiner werdenden Radius?

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

Forum-Anfänger

Forum-Anfänger


Beiträge: 13
Anmeldedatum: 10.09.10
Wohnort: ---
Version: ---
     Beitrag Verfasst am: 24.09.2010, 19:46     Titel:
  Antworten mit Zitat      
Also M hat Dimensionen von 5000 und mehr in x und y Richtung.

n wird vermutlich zwischen 1000 und 10000 variieren.

Wdas Problem ist halt, dass der Algorithmus extrem ineffizient ist. Die FOR-Schleife läuft n-mal und es ist theoretisch nicht garantiert, dass die Differenz zwischen Wunschindex und dem tatsächlichen Index kleiner geworden ist.
Und die While-Schleife läuft halt solange, bis der Index (plus Karenz) erreicht ist.


Harald hat Folgendes geschrieben:
Hallo,

ausgehend von dem momentanen Algorithmus würde ich vorschlagen zu vektorisieren.
Um hier einen Rat zu geben, müsste man etwas mehr über typische Eingabeargumente - vor allem die Dimensionen von M und n - wissen.
Ich würde auch mal den Profiler drüber laufen lassen um zu sehen, wo die Funktion die meiste Zeit verbraucht.

Grüße,
Harald
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: 24.09.2010, 22:22     Titel:
  Antworten mit Zitat      
Hallo,

einen wesentlich anderen Algorithmus (der dasselbe erreicht) wird dir hier wohl niemand vorschlagen können. Entweder du kommst selbst auf einen oder findest eine Veröffentlichung.
Vorschläge nochmal:
- soweit möglich vektorisieren (wahrsch. insbesondere interessant bei der aufgerufenen Funktion)
- mehrere Punkte auf einmal verändern (??)
- nach einer Weile Punkte in der Nähe verwenden --> bessere Erfolgschancen

Gib doch mal einen Beispielaufruf.

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.