Conditional Sum in Array

Question

I have 2 arrays, A and B. I want to form a new array C with same dimension as B where each element will show SUM(A) for A > B

Below is my working code

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

However, when A has millions of rows and B has thousands, and I have to do similar calculations for 20 array-couples,it takes insane amount of time.

Is there any faster way?

For example, histcounts is pretty fast, but it counts, rather than summing.

Thanks

Answer 1

Depending on the size of your arrays (and your memory limitations), the following code might be slightly faster:

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

Though it's vectorized, however, it seems to be bottlenecked (perhaps) by the allocation of memory. I'm looking to see if I can get a further speedup. Depending on your input vector size, I've seen up to a factor of 2 speedup for large vectors.

Answer 2

Here's a method that is a bit quicker, but I'm sure there is a better way to solve this problem.

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

According to some very rough tests, this seems to run a bit better than twice as fast as the original method.