Matlab-Vektorisierung - Matrixzeilenindizes ungleich Null für die Zelle

10

Ich arbeite mit Matlab.

Ich habe eine binäre quadratische Matrix. Für jede Zeile gibt es einen oder mehrere Einträge von 1. Ich möchte jede Zeile dieser Matrix durchgehen und den Index dieser Einsen zurückgeben und sie im Eintrag einer Zelle speichern.

Ich habe mich gefragt, ob es eine Möglichkeit gibt, dies zu tun, ohne alle Zeilen dieser Matrix zu durchlaufen, da die Schleife in Matlab sehr langsam ist.

Zum Beispiel meine Matrix

M = 0 1 0
    1 0 1
    1 1 1 

Dann will ich irgendwann so etwas

A = [2]
    [1,3]
    [1,2,3]

So Aist eine Zelle.

Gibt es eine Möglichkeit, dieses Ziel ohne for-Schleife zu erreichen, um das Ergebnis schneller zu berechnen?

ftxx
quelle
Möchten Sie, dass das Ergebnis schnell ist, oder möchten Sie, dass das Ergebnis forSchleifen vermeidet ? Für dieses Problem vermute ich bei modernen Versionen von MATLAB stark, dass eine forSchleife die schnellste Lösung ist. Wenn Sie ein Leistungsproblem haben, suchen Sie vermutlich am falschen Ort nach einer Lösung, die auf veralteten Ratschlägen basiert.
Wird
@ Will ich möchte, dass die Ergebnisse schnell sind. Meine Matrix ist sehr groß. Die Laufzeit in meinem Computer beträgt ungefähr 30 Sekunden, wenn die for-Schleife verwendet wird. Ich möchte wissen, ob es einige clevere Vektorisierungsoperationen oder mapReduce usw. gibt, die die Geschwindigkeit erhöhen können.
ftxx
1
Ich vermute, du kannst nicht. Die Vektorisierung funktioniert mit genau beschriebenen Vektoren und Matrizen, aber Ihr Ergebnis ermöglicht Vektoren unterschiedlicher Länge. Daher gehe ich davon aus, dass Sie immer eine explizite Schleife oder eine ähnliche Schleife haben werden cellfun.
HansHirse
@ftxx wie groß? Und wie viele 1s in einer typischen Reihe? Ich würde nicht erwarten, dass eine findSchleife etwas in der Nähe von 30 Sekunden benötigt, damit etwas klein genug ist, um in den physischen Speicher zu passen.
Wird
@ftxx Bitte beachten Sie meine aktualisierte Antwort, die ich bearbeitet habe, da sie mit einer geringfügigen Leistungsverbesserung akzeptiert wurde
Wolfie

Antworten:

11

Am Ende dieser Antwort steht ein Benchmarking-Code, da Sie klargestellt haben, dass Sie an Leistung interessiert sind, anstatt forSchleifen willkürlich zu vermeiden .

Tatsächlich denke ich, dass forLoops hier wahrscheinlich die performanteste Option sind. Seit Einführung der "neuen" (2015b) JIT-Engine sind ( Quell- ) forSchleifen nicht von Natur aus langsam - tatsächlich werden sie intern optimiert.

Sie können dem Benchmark mat2cellentnehmen, dass die von ThomasIsCoding hier angebotene Option sehr langsam ist ...

Vergleich 1

Wenn wir diese Linie splitapplyentfernen , um die Skala klarer zu machen, ist meine Methode ziemlich langsam. Obchardons Accumarray-Option ist etwas besser, aber die schnellsten (und vergleichbaren) Optionen verwenden entweder arrayfun(wie auch von Thomas vorgeschlagen) oder eine forSchleife. Beachten Sie, dass dies für die meisten Anwendungsfälle im arrayfunGrunde genommen eine forverschleierte Schleife ist. Dies ist also keine überraschende Verbindung!

Vergleich 2

Ich würde empfehlen, eine forSchleife zu verwenden, um die Lesbarkeit des Codes und die beste Leistung zu verbessern.

Bearbeiten :

Wenn wir davon ausgehen, dass das Schleifen der schnellste Ansatz ist, können wir einige Optimierungen am findBefehl vornehmen .

Speziell

  • Machen Sie Mlogisch. Wie das folgende Diagramm zeigt, kann dies für relativ kleine Personen schneller sein M, jedoch langsamer, wenn die Typkonvertierung für große Geräte abgewogen wird M.

  • Verwenden Sie eine Logik, Mum ein Array zu indizieren, 1:size(M,2)anstatt es zu verwenden find. Dies vermeidet den langsamsten Teil der Schleife (den findBefehl) und überwiegt den Typkonvertierungsaufwand, was ihn zur schnellsten Option macht.

Hier ist meine Empfehlung für die beste Leistung:

function A = f_forlooplogicalindexing( M )
    M = logical(M);
    k = 1:size(M,2);
    N = size(M,1);
    A = cell(N,1);
    for r = 1:N
        A{r} = k(M(r,:));
    end
end

Ich habe dies dem unten stehenden Benchmark hinzugefügt. Hier ist der Vergleich von Loop-Ansätzen:

Vergleich 3

Benchmarking-Code:

rng(904); % Gives OP example for randi([0,1],3)
p = 2:12; 
T = NaN( numel(p), 7 );
for ii = p
    N = 2^ii;
    M = randi([0,1],N);

    fprintf( 'N = 2^%.0f = %.0f\n', log2(N), N );

    f1 = @()f_arrayfun( M );
    f2 = @()f_mat2cell( M );
    f3 = @()f_accumarray( M );
    f4 = @()f_splitapply( M );
    f5 = @()f_forloop( M );
    f6 = @()f_forlooplogical( M );
    f7 = @()f_forlooplogicalindexing( M );

    T(ii, 1) = timeit( f1 ); 
    T(ii, 2) = timeit( f2 ); 
    T(ii, 3) = timeit( f3 ); 
    T(ii, 4) = timeit( f4 );  
    T(ii, 5) = timeit( f5 );
    T(ii, 6) = timeit( f6 );
    T(ii, 7) = timeit( f7 );
end

plot( (2.^p).', T(2:end,:) );
legend( {'arrayfun','mat2cell','accumarray','splitapply','for loop',...
         'for loop logical', 'for loop logical + indexing'} );
grid on;
xlabel( 'N, where M = random N*N matrix of 1 or 0' );
ylabel( 'Execution time (s)' );

disp( 'Done' );

function A = f_arrayfun( M )
    A = arrayfun(@(r) find(M(r,:)),1:size(M,1),'UniformOutput',false);
end
function A = f_mat2cell( M )
    [i,j] = find(M.');
    A = mat2cell(i,arrayfun(@(r) sum(j==r),min(j):max(j)));
end
function A = f_accumarray( M )
    [val,ind] = ind2sub(size(M),find(M.'));
    A = accumarray(ind,val,[],@(x) {x});
end
function A = f_splitapply( M )
    [r,c] = find(M);
    A = splitapply( @(x) {x}, c, r );
end
function A = f_forloop( M )
    N = size(M,1);
    A = cell(N,1);
    for r = 1:N
        A{r} = find(M(r,:));
    end
end
function A = f_forlooplogical( M )
    M = logical(M);
    N = size(M,1);
    A = cell(N,1);
    for r = 1:N
        A{r} = find(M(r,:));
    end
end
function A = f_forlooplogicalindexing( M )
    M = logical(M);
    k = 1:size(M,2);
    N = size(M,1);
    A = cell(N,1);
    for r = 1:N
        A{r} = k(M(r,:));
    end
end
Wolfie
quelle
1
Schon gesehen und positiv bewertet. :-) Ich warte immer noch auf Luis; Er hat sicher etwas schwarze MATLAB-Magie dafür.
HansHirse
@Hans Haha Ja, obwohl seine übliche Trickkiste (implizite Erweiterung, clevere Indizierung, ...) normalerweise Dinge als Matrizen enthält, fasst sich der Engpass hier in Zellen zusammen
Wolfie
1
Beachten Sie, dass diese Zeiten stark von der Sparsamkeit von abhängen M. Wenn zum Beispiel nur 5% der Elemente gefüllt sind, M = randi([0,20],N) == 20;ist die forSchleife bei weitem die langsamste und Ihre arrayfunMethode gewinnt.
Wird
@HansHirse :-) Mein Ansatz wäre accumarrayohne gewesen ind2sub, aber er ist langsamer als die forSchleife
Luis Mendo
2

Sie können arrayfunwie unten versuchen , die durch Reihen von fegenM

A = arrayfun(@(r) find(M(r,:)),1:size(M,1),'UniformOutput',false)

A =
{
  [1,1] =  2
  [1,2] =

     1   3

  [1,3] =

     1   2   3

}

oder (ein langsamerer Ansatz von mat2cell)

[i,j] = find(M.');
A = mat2cell(i,arrayfun(@(r) sum(j==r),min(j):max(j)))

A =
{
  [1,1] =  2
  [2,1] =

     1
     3

  [3,1] =

     1
     2
     3

}
ThomasIsCoding
quelle
1
Obwohl arrayfunes sich im Grunde genommen um eine Loop-in-Verkleidung handelt, kann dies an beiden Fronten fehlschlagen: 1) Vermeidung von Loops und 2) Schnelligkeit, wie vom OP erhofft
Wolfie
2

Bearbeiten : Ich habe einen Benchmark hinzugefügt. Die Ergebnisse zeigen, dass eine for-Schleife effizienter ist alsaccumarray .


Sie können verwenden findund accumarray:

[c, r] = find(A');
C = accumarray(r, c, [], @(v) {v'});

Die Matrix wird transponiert ( A'), weil findnach Spalten gruppiert.

Beispiel:

A = [1 0 0 1 0
     0 1 0 0 0
     0 0 1 1 0
     1 0 1 0 1];

%  Find nonzero rows and colums
[c, r] = find(A');

%  Group row indices for each columns
C = accumarray(r, c, [], @(v) {v'});

% Display cell array contents
celldisp(C)

Ausgabe:

C{1} = 
     1     4

C{2} = 
     2

C{3} =
     3     4

C{4} = 
     1     3     5

Benchmark:

m = 10000;
n = 10000;

A = randi([0 1], m,n);

disp('accumarray:')
tic
[c, r] = find(A');
C = accumarray(r, c, [], @(v) {v'});
toc
disp(' ')

disp('For loop:')
tic
C = cell([size(A,1) 1]);
for i = 1:size(A,1)
    C{i} = find(A(i,:));
end
toc

Ergebnis:

accumarray:
Elapsed time is 2.407773 seconds.

For loop:
Elapsed time is 1.671387 seconds.

Eine for-Schleife ist effizienter als accumarray...

Eliahu Aaron
quelle
Dies ist so ziemlich die Methode, die bereits von obchardon vorgeschlagen wurde , nicht wahr ?
Wolfie
Ja, ich war etwas langsam, ich habe seine Antwort gesehen, nachdem ich meine gepostet habe.
Eliahu Aaron
2

Mit accumarray :

M = [0 1 0
     1 0 1
     1 1 1];

[val,ind] = find(M.');

A = accumarray(ind,val,[],@(x) {x});
obchardon
quelle
1
Die Ausführungszeit in Octave und MATLAB Online beträgt ungefähr das Zweifache einer einfachen for-Schleife wie : MM{I} = find(M(I, :)).
HansHirse
2
@Hans Sie möchten vielleicht meine Antwort sehen
Wolfie
Ja, da die Größe jeder Zelle nicht gleich ist, kann dieses Problem nicht vollständig vektorisiert werden (oder es gibt einen Trick, den ich nicht gesehen habe). Es ist nur eine Lösung, die die for-Schleife verbirgt.
Obchardon
Keine Notwendigkeit für ind2sub:[ii, jj] = find(M); accumarray(ii, jj, [], @(x){x})
Luis Mendo
@ LuisMendo danke, ich habe meine Antwort bearbeitet.
Obchardon
2

Sie können strfind verwenden :

A = strfind(cellstr(char(M)), char(1));
rahnema1
quelle
Ich habe (träge) noch nicht einmal in den Dokumenten nachgesehen, aber wäre dies schneller, wenn tatsächliche stringTypen anstelle von Zeichen verwendet würden? Es gibt viele Optimierungen für Saiten, daher gibt es sie auch ...
Wolfie
@ Wolfie Ich denke, numerische Arrays sind char-Arrays ähnlicher als Strings, daher sollte die Konvertierung von numerischen Arrays in Zeichenarrays einfacher sein als die Konvertierung in Strings.
Rahnema1