Help to vectorise a conditional cumulative sum

If you have any time, I need some help vectorizing! Racking my brains, and I can’t figure out a way!

I have two vectors of length m: L and W. L contains a vector of lengths, and W contains a vector of corresponding widths. I would like to make a third vector, C, which is the cumulative total of the elements of L subject to the corresponding W being less than the current value of W. i.e. if W(j)<W(i) for j<i, then include L(j) in the sum, if not, then exclude it from the sum.

I can easily do this using a for loop:

C(1) = 0;
for i = 2:m
      C(i) = sum(L(1:i-1).*(W(1:i-1)<W(i)))
end

however, I cannot think of a way to vectorize this. Can anyone think of a way?

Thanks, Ric

Answer 1

[Andrei Bobrov]

C = sum(tril(W(:) > W(:)',-1).*L(:)',2);

[Ric Porteous]

Hi Andrei,

Thanks so much for your reply. This definitely worked. One thing I noticed, though, is that you get no speed benefit when applying the method to vectors that are >10^3. For example:

m = 10000;
L=randi([1 10],1,m);
W=randi([1 10],1,m);
tic
C = zeros(m,1);
C(1) = 0;
for i = 2:m
    C(i) = sum(L(1:i-1).*(W(1:i-1)<W(i)));
end
toc1 = toc
tic
C2 = sum(tril(W(:) > W(:)',-1).*L(:)',2);
toc2 = toc
toc1 = 0.41 s
toc2 = 0.81 s

I guess that making a giant 10000x10000 matrix might not be the most computationally efficient thing to do. Any thoughts on this?

Thanks, Ric

[Andrei Bobrov]

In case use largest arrays your variant with use loop effecient than my variant.

[Stephen23]

@Ric Porteous: there is no guarantee that vectorized code is more efficient. As you have just found out, when very large intermediate arrays must be created then it is quite possible that a loop is faster.

Do some timing test and decide for yourself. Keep in mind code complexity/comprehensibility and future memory improvements.