Matrix rekursiv füllen -> Beschleunigen

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

Partner:

Forum

Option

[Erweitert]

• Diese Seite per Mail weiterempfehlen

Gehe zu:

Mo3bius

Forum-Anfänger


	Beiträge: 11

	Anmeldedatum: 11.01.13

	Wohnort: ---

	Version: ---

Verfasst am: 26.03.2013, 19:22 Titel: Matrix rekursiv füllen -> Beschleunigen

Hi,
hier der Code den ich beschleunigen möchte:

Code:

for i = 2:n
for j = 2:m
D(i,j) = c(i,j) + min(D(i-1,j),min(D(i-1,j-1),D(i,j-1)));
end

Funktion ohne Link?

Die Matrix c ist fest vorgegeben. Die Matrix D wird im Laufe der beiden Schleifen gefüllt.

Hättet ihr einen Vorschlag wie ich das beschleunigen könnte?

Grüsse,
Mo3bius

Jan S

Moderator


	Beiträge: 11.057

	Anmeldedatum: 08.07.10

	Wohnort: Heidelberg

	Version: 2009a, 2016b

Verfasst am: 26.03.2013, 20:06 Titel: Re: Matrix rekursiv füllen -> Beschleunigen

Hallo Mo3bius,

Da fehlt noch ein "end".

Ist die Ausgabe D pre-alloziert? Das ist enorm wichtig.

Die Standard-Methode ist das Bewegen des Schleifen-Zählers in den Ausdruck hinein:

Code:

D = zeros(n, m); % Pre-allocate!!!
for i = 2:n
D(i, 2:m) = c(i, 2:m) + min(D(i-1, 2:m),min(D(i-1,1:m-1),D(i,1:m-1)));
end

Funktion ohne Link?

Würde das mit dem zweiten Zähler genauso funktionieren?

Gruß, Jan

Mo3bius

Themenstarter

Forum-Anfänger


	Beiträge: 11

	Anmeldedatum: 11.01.13

	Wohnort: ---

	Version: ---

Verfasst am: 26.03.2013, 21:01 Titel:

Hallo Jan,

die Matrix D habe ich schon pre-alloziert. Ebenso habe ich das end vergessen. Hier nochmal der vollständige Ausgangscode:

Code:

D = zeros(n,m);

D(1,1) = 1;
for i = 2:n
D(i,1) = D(i-1,1)+c(i,1);
end

for j = 2:m
D(1,j) = c(1,j);
end

for i = 2:n
for j = 2:m

D(i,j) = c(i,j) + min(D(i-1,j),min(D(i-1,j-1),D(i,j-1)));

end
end

Funktion ohne Link?

Die beiden ersten Schleifen fügen die erste Zeile und Spalte hinzu. Danach sollte mein Code die Matrix nach und nach füllen.

Zitat:

Die Standard-Methode ist das Bewegen des Schleifen-Zählers in den Ausdruck hinein:

Deine Methode funktioniert leider nicht wirklich. Ich habe meinen Code so angepasst:

Code:

D = zeros(n,m);
D(1,1) = 1;
for i = 2:n
D(i,1) = D(i-1,1)+c(i,1);
end
for j = 2:m
D(1,j) = c(1,j);
end
for i = 2:n
D(i, 2:m) = c(i, 2:m) + min([D(i-1, 2:m),D(i-1,2:m-1),D(i,2:m-1)]);
end

Funktion ohne Link?

Kann das Matlab überhaupt beschleunigen? Ich muss die Werte ja nach und nach berechnen. Ansonsten wäre deine Methode super schnell Smile

Grüsse,
Mo3bius

Jan S

Moderator


	Beiträge: 11.057

	Anmeldedatum: 08.07.10

	Wohnort: Heidelberg

	Version: 2009a, 2016b

Verfasst am: 27.03.2013, 12:22 Titel:

Hallo Mo3bius,

Es ist immer ein Vorteil, wenn Du Details wie Pre-allocation gleich erwähnst. Dann vertrödeln die Antwortenden keine Zeit damit.

Ichhabe einige Ideen, kann sie aber mangels Matlab nicht ausprobieren. Vielleicht kommt nach Ostern mehr.

Code:

D = zeros(n,m); % Wäre D = c nicht praktischer?

% Das geht auch ohne Schleife:
D(1,1) = 1;
D(2:n, 1) = c(2:n, 1);
D(:, 1) = cumsum(D(:, 1));

% Das geht schon mal ohne Schleife:
D(1, 2:m) = c(1, 2:m);

% Hier bin ich noch am Grübeln:
for i = 2:n
for j = 2:m

D(i,j) = c(i,j) + min(D(i-1,j),min(D(i-1,j-1),D(i,j-1)));

end
end

Funktion ohne Link?

Ich vermute, dass sich das noch deutlich beschleunigen lässt, wenn mir erstmal klar ist, was es überhaupt macht. Es geht um eine [n x m]-Matrix, die zunächst die Werte aus "c" enthält. Dann soll für alle Elemente ausgehend von der Position (1,1) das kleinste Element der linken und oberen benachbarten Elemente addiert werden. Richtig?

Dabei sollte man am besten spalten-weise vorgehen, denn beim bisherigen Zeilen-weisen bearbeiten muss Matlab wild im Speicher herum-springen. Benachbarte Speicherzellen werden aber bevorzugt in den Prozessor-Cache geladen. Starte also mit der Vertauschung der FOR-Schleifen.

Gruß, Jan


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.