Kombinatorik - Beschleuigung der Ablaufstruktur - Mein MATLAB Forum

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

Partner:

Forum

Option

[Erweitert]

• Diese Seite per Mail weiterempfehlen

Gehe zu:

Kombinatorik - Beschleuigung der Ablaufstruktur

Tobias14

Forum-Anfänger


	Beiträge: 19

	Anmeldedatum: 15.12.14

	Wohnort: ---

	Version: ---

Verfasst am: 07.01.2015, 18:04 Titel: Kombinatorik - Beschleuigung der Ablaufstruktur

Hallo zusammen,

ich habe ein relativ komplexes Skript und versuche nur die langen Laufzeiten etwas zu reduzieren.

Zum Problem:
Ich habe eine Matrix A, welche mir die Spaltennummer für die anschließenden Vergleiche einer Matrix M (s.u.) liefert:

Code:

A=[1 2 3 4;
1 2 3 5;]
1 2 3 6]; % in Wirklichkeit deutlich länger
[lA,bA]=size(A);

Funktion ohne Link?

Die Matrix M enthält dann andere Zahlen die ich miteinander vergleiche, indem ich die Quotienten bilde, dann einen Tolleranzbereich abfrage und letztlich schaue welche Zeilen noch in beiden vorkommen

Code:

M=[100 150 170 180 190 50 70;
90 60 50 180 30 20 10;
101 82 73 139 192 35 16] % ebenfall deutlich größer

Funktion ohne Link?

Was ich bisher versucht habe:

Code:

for i=1:lA

Q12=M(:,A(i,1))./M(:,A(i,2));
Q34=M(:,A(i,3))./M(:,A(i,4));

% Nun folgt einer Toleranzangabe
Q12(Q12>100 | Q12<.1)=0;
Q34(Q34>100 | Q34<.1)=0;

% "Gemeinsame finden"
V=sum(Q12>0 & Q34>0);
MV(i,:)=V;
end

Funktion ohne Link?

Also zweite Möglichkeit habe ich bislang probiert, alle möglichen Quotienten Qn,k zu berechnen indem ich einfach die Matrix M immer weiterverschoben habe (circshift) und dann in der for-schleife bereits die berechneten Quotienten lade. Allerdings ist das im Moment zu komplex um zu beurteilen was schneller geht.

Die eigentliche Frage ist also: Bringt es etwas, die Quotienten Qn,k bereits vor der for-Schleife (welche einige Millionen Durchläufe hat) zu berechnen und dort nur noch zu laden oder ist die Quotientenbildung ohnehin extrem schnell?
Mit der ersten Methode braucht ich für 50 Mio Zyklen ca. 8h. Gibt es andere hilfreiche Tipps zur Beschleunigung (außer preallocation)?

Viele Grüße
Tobias

Harald

Forum-Meister


	Beiträge: 24.501

	Anmeldedatum: 26.03.09

	Wohnort: Nähe München

	Version: ab 2017b

Verfasst am: 07.01.2015, 18:22 Titel:

Hallo,

wenn ich das richtig sehe, benötigst du überhaupt keine for-Schleife:

Code:

Q12=M(:,A(:,1))./M(:,A(:,2));
Q34=M(:,A(:,3))./M(:,A(:,4));

% Nun folgt einer Toleranzangabe
Q12(Q12>100 | Q12<.1)=0;
Q34(Q34>100 | Q34<.1)=0;

% "Gemeinsame finden"
MV =sum(Q12>0 & Q34>0)

Funktion ohne Link?

Grüße,
Harald

Tobias14

Themenstarter

Forum-Anfänger


	Beiträge: 19

	Anmeldedatum: 15.12.14

	Wohnort: ---

	Version: ---

Verfasst am: 08.01.2015, 11:10 Titel:

Vielen Dank für die schnelle Antwort!
Im Prinzip stimmt es schon, dass ich kein for-schleife brauche. Allerdings bekomme ich dann ein Problem mit dem Arbeitsspeicher!

Bsp:

Code:

M=ones(100,10);
A=ones(500,4);

Q12=M(:,A(:,1))./M(:,A(:,2));

Funktion ohne Link?

Hier bekomme ich also für Q12 eine 100x500 Matrix...
in Wirklichkeit ist aber A einige Mio lang, und M einige 1000,
d.h. ich kann die Matrix so nicht mehr erstellen (Memory).

Grüße
Tobias

Harald

Forum-Meister


	Beiträge: 24.501

	Anmeldedatum: 26.03.09

	Wohnort: Nähe München

	Version: ab 2017b

Verfasst am: 08.01.2015, 11:31 Titel:

Hallo,

dann mit Blöcken arbeiten, etwa so:

Code:

for i=1:numBlocks

idx = (i-1)*blockSize + 1 : i*blockSize;
Q12=M(:,A(idx,1))./M(:,A(idx,2));
Q34=M(:,A(idx,3))./M(:,A(idx,4));

% Nun folgt einer Toleranzangabe
Q12(Q12>100 | Q12<.1)=0;
Q34(Q34>100 | Q34<.1)=0;

% "Gemeinsame finden"
V=sum(Q12>0 & Q34>0);
MV(idx,:)=V;
end

Funktion ohne Link?

Grüße,
Harald

Tobias14

Themenstarter

Forum-Anfänger


	Beiträge: 19

	Anmeldedatum: 15.12.14

	Wohnort: ---

	Version: ---

Verfasst am: 08.01.2015, 11:51 Titel:

Aber werde ich dadurch überhaupt schneller?
Beispiel:

Code:

M=ones(1000,4);
A=ones(5000,4);

% Option mit for-loop
tic
MV=zeros(length(A),1); % Preall.
for i=1:length(A)

Q12=M(:,A(i,1))./M(:,A(i,2));
Q34=M(:,A(i,3))./M(:,A(i,4));

Q12(Q12>100 | Q12<.1)=0;
Q34(Q12>100 | Q34<.1)=0;
V=sum(Q12>0 & Q34>0);
MV(i,:)=V;
end
t1=toc

% Option ohne for-loop

Q12_test=M(:,A(:,1))./M(:,A(:,2));
Q34_test=M(:,A(:,3))./M(:,A(:,4));

Q12_test(Q12_test>100 | Q12_test<.1)=0;
Q34_test(Q12_test>100 | Q34_test<.1)=0;

MV2=sum(Q12_test>0 & Q34_test>0)

t2=toc

Funktion ohne Link?

Bei mir ist jedoch t1 immer kleiner als t2... d.h. die for-schleife ist schneller. Wird das dann für noch größere Werte wieder anders? (Ich habe bis M=100,000 getestet und t1 war immer kleiner t2).
Gewinn ich dann überhaupt Zeit, wenn ich wie gezeigt in Blöcke unterteile um auch noch größerer Matrizen zu prozessieren?

Harald

Forum-Meister


	Beiträge: 24.501

	Anmeldedatum: 26.03.09

	Wohnort: Nähe München

	Version: ab 2017b

Verfasst am: 08.01.2015, 12:22 Titel:

Hallo,

du musst schon ein zweites tic einfügen, bevor die zweite Berechnung anfängt.
Zudem einen ; nach "MV2 = " um die lange dauernde Anzeige zu unterdrücken.

Eine Alternative zur Vektorisierung kann Parallelisierung sein, mit

Code:

parfor

Funktion ohne Link?

Grüße,
Harald

Tobias14

Themenstarter

Forum-Anfänger


	Beiträge: 19

	Anmeldedatum: 15.12.14

	Wohnort: ---

	Version: ---

Verfasst am: 08.01.2015, 12:26 Titel:

... sorry das war ein Fehler. Ich muss den Code gerade vom Laptop abschreiben. Ich habe natürlich ein zweites tic eingefügt und das ;
gesetzt. Trotzdem bin ich mit der schleife immer schneller...

Hier mein Vergleich

Code:

clear all
close all
clc

M=ones(10000,4); %Bspdaten
A=ones(5000,4);

% Mit for-loop
tic
MV1=zeros(length(A),1); %Preall.
for i=1:length(A);
Q12=M(:,A(i,1))./M(:,A(i,2));
Q34=M(:,A(i,3))./M(:,A(i,4));

Q12(Q12>100 | Q12<.1)=0;
Q34(Q34>100 | Q34<.1)=0;

V1=sum(Q12>0 & Q34>0);
MV1(i,:)=V1;
end
t1=toc

%Ohne for-loop
tic
Q12_t=M(:,A(:,1))./M(:,A(:,2));
Q34_t=M(:,A(:,3))./M(:,A(:,4));

Q12_t(Q12_t>100 | Q12_t<.1)=0;
Q34_t(Q34_t>100 | Q34_t<.1)=0;

MV2=sum(Q12_t>0 & Q34_t>0)';
t2=toc

% Mit Blöcken
tic
blocksize=10;
Elements=length(A)/blocksize;
MV3=zeros(length(A),1);
for i=1:blocksize
idx=(i-1)*Elements+1:i*Elements;

Q12_t2=M(:,A(idx,1))./M(:,A(idx,2));
Q34_t2=M(:,A(idx,3))./M(:,A(idx,4));

Q12_t2(Q12_t2>100 | Q12_t2<.1)=0;
Q34_t2(Q34_t2>100 | Q34_t2<.1)=0;

V3=sum(Q12_t2>0 & Q34_t2>0)';
MV3(idx,:)=V3;
end
t3=toc

Funktion ohne Link?

ich bekomme also immer die beste Performance mit Option1. Es scheint also schneller zu sein, wenn ich 2 Vektoren miteinander vergleiche als 2 Matrizen (in dafür keinem (Bsp2) oder weniger (Bsp3) Zyklen)

Grüße

Harald

Forum-Meister


	Beiträge: 24.501

	Anmeldedatum: 26.03.09

	Wohnort: Nähe München

	Version: ab 2017b

Verfasst am: 08.01.2015, 13:42 Titel:

Hallo,

dann sehe ich sequentiell keine Beschleunigungsmöglichkeit.

Eine Alternative wäre wie gesagt parfor.

Grüße,
Harald


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.