Somma condizionale in Array

Question

Ho 2 matrici, A e B. voglio formare una nuova matrice C con la stessa dimensione come B dove ogni elemento mostrerà SUM (A) per A> B

Sotto è il mio lavoro codice

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

Tuttavia, quando a ha milioni di righe e B ha migliaia, e devo fare calcoli simili per 20 array coppie, prende quantità folle di tempo.

C'è qualche modo più veloce?

Ad esempio, gli account sono piuttosto veloci, ma conta, piuttosto che sommare.

Grazie

Answer 1

Hai avuto le idee giuste con histcounts, dato che stai praticamente "accumulando" determinati elementi A basati su binning. Questa operazione di binning potrebbe essere eseguita con histc. Elencato in questo post è una soluzione che inizia con passaggi simili a quelli elencati in @David's answer e quindi utilizza histc per bin e somma gli elementi selettivi da A per ottenere l'output desiderato e tutto ciò in modo vettorializzato. Ecco l'implementazione -

%// 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 

Inoltre, si ricorda quando si confronta il risultato di questo metodo con quello della versione originale per-loop che ci sarebbero stati lievi variazioni in uscita come questa soluzione vettorizzati utilizza cumsum che calcola un'esecuzione sommatoria e in quanto tale avrebbe sommato numeri cumulativi cumulativi sommati a singoli elementi che sono relativamente molto piccoli, mentre la versione a ciclo sommerebbe solo elementi selettivi. Quindi, floating-precision issues verrebbe lì.

Answer 2

Ecco un metodo che è un po 'più veloce, ma sono sicuro che ci sia un modo migliore per risolvere questo problema.

a=sort(A); %// If A and B are already sorted then this isn't necessary! 
b=sort(B); 
c(numel(B))=0; %// Initialise c 
s=cumsum(a,2,'reverse'); %// Get the partial sums of a 
for n=1:numel(B) 
    %// Pull out the sum for elements in a larger than b(n) 
    c(n)=s(find(a>b(n),1,'first')); 
end 

Secondo alcuni test molto approssimativi, questo sembra funzionare un po 'meglio del doppio della velocità rispetto al metodo originale.

Answer 3

A seconda delle dimensioni degli array (e le vostre limitazioni di memoria), il seguente codice potrebbe essere leggermente più veloce:

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

Anche se è vettorializzare, tuttavia, sembra essere collo di bottiglia (forse) da una dotazione di memoria. Sto cercando di vedere se riesco a ottenere un'ulteriore accelerazione. A seconda della dimensione del vettore di input, ho riscontrato un fattore di accelerazione di 2 per i vettori di grandi dimensioni.