Effizienter Code versus Vektorisierung

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

Partner:

Forum

Option

[Erweitert]

• Diese Seite per Mail weiterempfehlen

Gehe zu:

Jan S

Moderator


	Beiträge: 11.057

	Anmeldedatum: 08.07.10

	Wohnort: Heidelberg

	Version: 2009a, 2016b

Verfasst am: 09.12.2016, 11:08 Titel: Effizienter Code versus Vektorisierung

Aufgabe: Erstelle eine CHAR-Matrix wie folgt:

Code:

Str = '1234', k = 2
==>
'12'
'23'
'34'

Funktion ohne Link?

1. Erster Versuch:

Code:

for ii = 1 : numel(str)-k+1
pattern(ii,:) = str(ii:ii+k-1);
end

Funktion ohne Link?

2. Pre-allocation: "pattern" iterativ wachsen zu lassen benötigt viele Resourcen, weil in jeder Iteration ein neues Array erstellt wird und die vorherigen Werte kopiert werden. Wenn man den Output vor der Schleife erstellt, werden nur die jeweiligen Werte einkopiert:

Code:

n = numel(str) - k + 1;
pattern = repmat(' ', n, k); % <-- added
for ii = 1:n
pattern(ii,:) = str(ii:ii+k-1);
end

Funktion ohne Link?

3. Matlab speichert Arrays spalten-orientiert. pattern(ii, :) schreibt deshalb in Speicherzellen, die weit von einander entfernt liegen. Zudem ist k immer kleiner als die String-Länge, sodass die Schleife kürzer wird, wenn man über die Spalten iteriert:

Code:

n = numel(str) - k + 1;
pattern = repmat(' ', n, k);
for ii = 1:k % <-- k instead of n
pattern(:, ii) = str(ii:ii+n-1); % <-- (:, ii) instead of (ii, :)
end

Funktion ohne Link?

4. Vektorisieren - das beschleunigt sehr viele Matlab Programme, aber nicht alle:

Code:

index = bsxfun(@plus, (1:numel(str) - k + 1).', 0:k-1);
pattern = str(index);

Funktion ohne Link?

5. Wie sieht das in C aus?

Code:

#include "mex.h"
void mexFunction(int nlhs, mxArray *plhs[], int nrhs, const mxArray *prhs[])
{
mwSize k, n, f;
mxChar *in, *out;
mwSize dims[2];

// Get inputs:
in = (mxChar *) mxGetData(prhs[0]);
k = (mwSize) mxGetScalar(prhs[1]);

// Create outputs:
n = mxGetNumberOfElements(prhs[0]) - k + 1;
dims[0] = n;
dims[1] = k;
plhs[0] = mxCreateCharArray(2, dims);
out = (mxChar *) mxGetData(plhs[0]);

// Copy data:
f = out + n * k;
while (out < f) {
memcpy(out, in++, n * sizeof(mxChar));
out += n;
}
}

Funktion ohne Link?

Und die Laufzeiten? Matlab 2015b 64, Win7, Mittelwert aus 100 Iterationen:

Code:

str = repmat(' ', 1, 10000); % Testdaten
k = 6;

Original: 0.134 sec
Pre-allocation: 0.0178 sec
Vectorized: 0.000806 sec
Continuous: 0.000348 sec
C-MEX: 0.0000529 sec

Funktion ohne Link?

Schlußfolgerung:
1. Pre-allocation ist fundamental.
2. Spalten-orientiertes Bearbeitung ist besser als zeilenweises Vorgehen.
3. Reduziere die Schleifen-Größe, wenn möglich. Bei geschachtelten Schleifen, ziehe die kürzere nach außen. (Ist hier nicht passend)
4. Vektorisierter Code ist nicht schneller, wenn dazu große temporäre Index-Array erzeugt werden müssen. Hier besteht die Hauptarbeit aus dem Kopieren der Unter-Strings, und das geht mit einer Schleife bereits effizient, während der vektorisierte Code praktisch die doppelte Arbeit hat.
5. Der C-Code ist schnell, aber im Vergleich zu Matlab umständlich, häßlich und fehleranfällig. Hier mal einen Index falsch setzen lässt gleich die ganze Matlab-Session crashen - und wenn man Pech hat nur manchmal.
6. Der C-Mex code ist 7 mal schneller als die beste M-Version. Aber wenn die vom Gesamtprogramm nur 1% benötigt, sinkt die Laufzeit nur um 0.86%. Da kümmert man sich also besser um das Bottleneck, das man mit dem Profiler findet.
7. Die erhaltene Matrix "pattern" ist sehr redundant. Wahrscheinlich wäre es viel effizienter im Code direkt str(ii:ii+k-1) zu verwenden.


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 - 2024 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.