-Summe in Array

Question

Ich habe 2 Arrays, A und B. Ich will als B ein neues Array C mit derselben Dimension bilden, wobei jedes Element SUM zeigen (A) für A> B

Unter meinen Arbeiten sind Code

A = [1:1:1000] 
B=[1:1:100] 
for n = 1:numel(B) 
    C(n) = sum(A(A>B(n))); 
end 

wenn jedoch eine Millionen von Zeilen hat, und B hat tausende, und ich habe ähnliche Berechnungen für 20 array-Paare zu tun, nimmt es unglaubliche Menge an Zeit.

Gibt es einen schnelleren Weg?

Zum Beispiel ist Histounts ziemlich schnell, aber es zählt, anstatt zu summieren.

Dank

Answer 1

Sie hatten die richtigen Ideen mit histcounts, da Sie im Grunde bestimmte A Elemente basierend auf binning akkumulieren. Diese Binning-Operation könnte mit histc durchgeführt werden. In diesem Post ist eine Lösung aufgelistet, die mit ähnlichen Schritten wie in @David's answer aufgelistet beginnt und dann histc verwendet, um selektive Elemente aus A zu sammeln und zusammenzufassen, um uns die gewünschte Ausgabe und alles vektorisiert zu erhalten. Hier ist die Umsetzung -

%// Sort A and B and also get sorted B indices 
sA = sort(A); 
[sB,sortedB_idx] = sort(B); 

[~,bin] = histc(sB,sA);  %// Bin sorted B onto sorted A 
C_out = zeros(1,numel(B)); %// Setup output array 

%// Take care of the case when all elements in B are greater than A 
if sA(1) > sB(end) 
    C_out(:) = sum(A); 
end 

%// Only do further processing if there is at least one element in B > any element in A 
if any(bin) 
    csA = cumsum(sA,'reverse'); %// Reverse cumsum on sorted A 

    %// Get sum(A(A>B(n))) for every n, but for sorted versions 
    valid_mask = cummax(bin) - bin ==0; 
    valid_mask2 = bin(valid_mask)+1 <= numel(A); 
    valid_mask(1:numel(valid_mask2)) = valid_mask2; 
    C_out(valid_mask) = csA(bin(valid_mask)+1); 

    %// Rearrange C_out to get back in original unsorted version 
    [~,idx] = sort(sortedB_idx); 
    C_out = C_out(idx); 
end 

Auch denken Sie bitte daran, wenn das Ergebnis dieser Methode mit der man von der ursprünglichen for-Schleife Version vergleichen, dass es geringfügige Abweichungen in der Ausgabe sein würde, wie dies vektorisiert Lösung cumsum verwendet, die eine Lauf berechnet Summation und als solche hätte man große kumulativ summierte Zahlen zu einzelnen Elementen hinzugefügt, die vergleichsweise sehr klein sind, während die For-Loop-Version nur selektive Elemente summieren würde. Also, floating-precision issues würde da hoch kommen.

Answer 2

Hier ist eine Methode, die ein bisschen schneller, aber ich bin sicher, dass es ein besserer Weg, um dieses Problem zu lösen.

Nach einigen sehr harten Tests scheint dies etwas besser zu laufen als doppelt so schnell wie die ursprüngliche Methode.

Answer 3

Abhängig von der Größe Ihres Arrays (und Ihre Speicherbeschränkungen), könnte der folgende Code etwas schneller sein:

C = A*bsxfun(@gt,A',B); 

Obwohl es vektorisiert ist, aber es scheint, durch die Zuteilung Engpass (vielleicht) zu der Erinnerung. Ich suche nach einer weiteren Beschleunigung. Abhängig von der Größe Ihres Eingabevektors habe ich bei großen Vektoren bis zu einem Faktor 2 beschleunigt.