For-Schleife sehr langsam - Alternative? - 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:

For-Schleife sehr langsam - Alternative?

dotwinX

Forum-Fortgeschrittener


	Beiträge: 52

	Anmeldedatum: 06.12.09

	Wohnort: ---

	Version: ---

Verfasst am: 17.03.2012, 14:03 Titel: For-Schleife sehr langsam - Alternative?

Moin,

ich habe folgendes Problem und hoffe ihr könnt mir weiterhelfen:
Ich habe 2 Matrizen, die jeweils 2 Zeilen haben, jedoch unterschiedliche Spaltenlängen.
Die zwei Zeilen der beiden unterschiedlich langen Matrizen sind jeweils X und Y-Werte eines Koordinatensystems. Ich weiß, dass alle X-Y Kombinationen der "kleinen Matrix" definitiv in der großen Matrix enthalten sind. Ich suche nur die Indices der großen Matrix, wo X und Y gleich sind.

Das ganze habe ich mit einer For-Schleife gelößt:

Code:

for i=1:1:length(vec_x_klein)
t1=[vec_x_groß; vec_y_groß];
t2=[vec_x_klein(i); vec_y_klein(i)];
t3=bsxfun(@minus, t1, t2);
t4=sum(t3,1);
t5=abs(t4);
[I Zeile]=min(t5);
indicies(i)=I;
end

Funktion ohne Link?

Die kleine Matrix ist ca. 2.300 Einträge lang, die große ca. 260.000

Profiler spuckt mir folgendes raus:
t3=bsxfun(@minus, t1, t2); 28.853s 65.1%
t1=[vec_x_groß; vec_y_groß]; 6.217s 14.0%
[I Zeile]=min(t5); 3.931s 8.9%
t4=sum(t3,1); 3.614s 8.2%
t5=abs(t4); 1.614s 3.6%

Will also heißen, dass die Idee mit der for-Schleife allgemein Mist ist.
Hättet ihr eine fixere Idee?

Gruß, Dennis

Zuletzt bearbeitet von dotwinX am 17.03.2012, 14:33, insgesamt einmal bearbeitet

DSP

Forum-Meister


	Beiträge: 2.117

	Anmeldedatum: 28.02.11

	Wohnort: ---

	Version: R2014b

Verfasst am: 17.03.2012, 14:31 Titel:

Sind die Vektoren, welchen Werte zugewiesen werden vor der Schleife allociert worden? Das spart einiges an Zeit.

Code:

% z.B.
t1 = zeros(x,1); % x = benötigte Größe/Speicherplatz
for ...

Funktion ohne Link?

dotwinX

Themenstarter

Forum-Fortgeschrittener


	Beiträge: 52

	Anmeldedatum: 06.12.09

	Wohnort: ---

	Version: ---

Verfasst am: 17.03.2012, 14:44 Titel:

Zitat:

Sind die Vektoren, welchen Werte zugewiesen werden vor der Schleife allociert worden? Das spart einiges an Zeit.

Hab ich grad ausprobiert - leider keine Verbesserung
Wobei das auch nur beim ersten mal in der Schleife i=1 bremsen würde, oder? Danach würden die Matrizen ja schon existieren und das sollte keine Zeit mehr rauben, da die Größe der Matrizen sich nicht ändert.
Dennoch danke für den Vorschlag.

Jan S

Moderator


	Beiträge: 11.057

	Anmeldedatum: 08.07.10

	Wohnort: Heidelberg

	Version: 2009a, 2016b

Verfasst am: 19.03.2012, 03:33 Titel: Re: For-Schleife sehr langsam - Alternative?

Hallo dotwinX,

Ist "indices" pre-allociert?
Sind die X- und Y-Werte exakt gleich oder können kleine Rundungsfehler auftreten?
Sind die Werte unterschiedlich oder können Wiederholungen auftreten?
Sind die Werte sortiert? Dann wäre ein binary-search deutlich schneller.

Eventuell könnte dies schneller sein:

Code:

indices = zeros(1, length(vec_x_klein));
for i = 1:length(vec_x_klein)
indicies(i) = find(vec_x_groß == vec_x_klein(i) & vec_y_groß == vec_y_klein(i), 1);
end

Funktion ohne Link?

Falls z.B. vec_x_klein nicht-unique ist, könnte man sich die wiederholte Bestimmung von "vec_x_groß == vec_x_klein(i)" sparen.

Man könnte auch ISMEMBER verwenden:

Code:

clear('i'); % It should be the imaginary unit
v1 = vec_x_groß + i*vec_y_groß;
v2 = vec_x_klein + i*vec_y_klein;
[dummy, indices] = ismember(v2, v1);

Funktion ohne Link?

Der Overhead in ISMEMBER kann noch reduziert werden, wenn man direkt ISMEMBC aufruft. Dann muss man die Werte aber vorher sortieren, siehe "edit ismember". ISMEMBC nutzt dann ein binary-search, um die übereinstimmenden Werte in optimaler Zeit zu finden.

Gruß, Jan

Andy386

Forum-Guru


	Beiträge: 485

	Anmeldedatum: 24.06.09

	Wohnort: ---

	Version: 7.1/8

Verfasst am: 19.03.2012, 10:19 Titel:

Für mich sieht das so aus, als würden sich die großen Vektoren nicht ändern -> t1 ist immer gleich -> Rausnehmen und 14% Rechenzeit gespart!
_________________

Ich hasse es wenn die Leute Fragen stellen, man dann versucht sich Mühe zu geben, und diejenigen ihren Thread nie wieder besuchen...

Sirius3

Forum-Guru


	Beiträge: 441

	Anmeldedatum: 12.11.11

	Wohnort: ---

	Version: ---

Verfasst am: 19.03.2012, 20:23 Titel:

Hallo dotwinX,

endlich mal wieder Gelegenheit eine meiner Lieblingsfunktionen anzuwenden:

Code:

[~,igr,ikl]=intersect([vec_x_groß; vec_y_groß]',[vec_x_klein; vec_y_klein]','rows');
[~,idx]=sort(ikl);
indices=igr(idx);

Funktion ohne Link?

Grüße
Sirius

dotwinX

Themenstarter

Forum-Fortgeschrittener


	Beiträge: 52

	Anmeldedatum: 06.12.09

	Wohnort: ---

	Version: ---

Verfasst am: 23.03.2012, 13:30 Titel:

Moin!

Danke erstmal für eure vielen Antworten!

und @Sirius3
Ich selbst hab kürzlich genau diese Funktion verwendet - wusste nur net, dass die auch 'rows' unterstützt. Super Sache, etwa 121 mal schneller als meine Lösung
Elapsed time is 0.328160 seconds.

@Jan S
Jup, "indices" waren pre-allociert - hat leider keinen Unterschied gemacht.
Die For-Schleife war etwas fixer als meine Variante, aber Matlab ist nunmal langsam bei for-schleifen, leider....

Aber deine 2. Lösung ist super!!
Elapsed time is 0.073279 seconds.

Bedanke mich viemals!

Jan S

Moderator


	Beiträge: 11.057

	Anmeldedatum: 08.07.10

	Wohnort: Heidelberg

	Version: 2009a, 2016b

Verfasst am: 24.03.2012, 02:00 Titel:

Hallo dotwinX,

Seit Matlab 6.5 sind Schleifen nicht mehr besonders langsam. Das Gerücht hält sich aber hartnäckig. In diesem Code gibt es ein anderes Problem:

Code:

for i = 1:length(vec_x_klein)
indicies(i) = find(vec_x_groß == vec_x_klein(i) & vec_y_groß == vec_y_klein(i), 1);
end

Funktion ohne Link?

Das Argument im FIND-Befehl wird in jeder Iteration neu erstellt. Defür benötigt man zwei LOGCIAL Vektoren, die danach per & verknüpgft werden, sodass ein dritter LOGICAL Vektor alloziert werden muss. Danach muss man im Durchschnitt die Hälfte der Elemente testen, um per FIND(., 1) das erste Element zu finden. Das Allozieren von 3*LENGTH(vec_x_groß) Arrays ist einfach zeitraubend. Hier wäre C deutlich effizienter, weil es die Zwischen-Schritte gar nicht explizit erstellen müsste.

Gruß, Jan

dotwinX

Themenstarter

Forum-Fortgeschrittener


	Beiträge: 52

	Anmeldedatum: 06.12.09

	Wohnort: ---

	Version: ---

Verfasst am: 30.11.2014, 17:23 Titel:

Moin,

auch wenn der Thread schon etwas älter ist, benutze ich immer noch den Ansatz von Jan:

Code:

v1 = vec_x_groß + i*vec_y_groß;
v2 = vec_x_klein + i*vec_y_klein;
[dummy, indices] = ismember(v2, v1);

Funktion ohne Link?

Nun zeigt sich, dass erneut dieser Teil der "Bottleneck" ist, weil ich den Code "drumherum" optimiert habe. Jetzt frisst dieser kleine Absatz ca. 95% der Zeit (Besser als 99,99%, wie mein erstmaliger Ansatz, siehe oben). Hättet ihr noch eine Idee um noch etwas mehr aus dem Ansatz an Zeit herauszukitzeln?

Die Fragestellung ist die gleiche: Finde die gleichen x und y-Einträge eines großen und kleinen Vektors

@ Jan: Du meintest, dass man sich den Overhead sparen könnte, nur das mit ismembc funzt nicht so wie es soll. Wie müssten die Werte sortiert sein?

VG

Dennis


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.