数组中的条件求和

Question

我有2个数组,A和B.我想形成一个新的数组C,其尺寸与B相同,其中每个元素将显示为A> B的SUM(A)

以下是我的工作代码

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

然而,当A有数百万行而B有数千行时,我必须对20个阵列对进行类似的计算,这需要花费大量时间.

有没有更快的方法？

例如,histcounts非常快,但它很重要,而不是求和.

谢谢

Answer 1

根据数组的大小(以及内存限制),以下代码可能会稍微快一些:

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

虽然它是矢量化的,但它似乎是通过内存分配的瓶颈(也许).我想看看我是否可以进一步加速.根据您的输入矢量大小,我发现大型矢量的速度提高了2倍.

Answer 2

这是一个更快一点的方法,但我确信有更好的方法来解决这个问题.

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

根据一些非常粗略的测试,这似乎比原始方法快两倍.

Answer 3

你有正确的想法histcounts,因为你基本上"积累"某些A元素binning.这种分箱操作可以完成histc.在这篇文章中列出的解决方案是从列出的类似步骤开始@David's answer,然后用于histc对选择性元素A进行分类和汇总,以便以矢量化方式获得所需的输出和所有输出.这是实施 -

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

另外,请记住,将此方法的结果与原始for循环版本的结果进行比较时,输出会有轻微变化,因为此向量化解决方案使用cumsum计算运行总和,因此会添加大的累计求和数对于相对非常小的单个元素,而for循环版本仅对选择性元素求和.那么,floating-precision issues会出现在那里.