Adding up different number of elements from each row

Question

I have a main matrix, say

A=magic(5);

and also a vector

v=[1;3;5;2;2];

I want to add up row-wise the elements of A in this way: add first row from the v(1)st element to the end, second row from the v(2)rd element to the end, third row from the v(3)th element to the end, and so on.

I know that I can do this using for-loop. But I want to know if there is a vectorized way to do it.

edit: Let me clarify my question with an example: Assume A and v as above.

A =

 17    24     1     8    15
 23     5     7    14    16
  4     6    13    20    22
 10    12    19    21     3
 11    18    25     2     9

and

Now I want a way to get the following results:

answer =
 65  % 17+24+1+8+15
 37  % 7+14+16
 22  % 22
 55  % 12+19+21+3
 54  % 18+25+2+9

It's much easier to help you if you post valid Matlab code snippets that we can just cut and paste. Having to modify your definition of A so that Matlab accepts it is a drag. — High Performance Mark, Apr 25 '13 at 13:18

score 4 · Accepted Answer · answered Apr 25 '13 at 13:18

4

You can use cumsum along the rows. The solution is a bit complex, so I'll start with a simpler example:

Suppose you want to sum all elements of the i-th row of A till (including) the v(i)-th place: res_i = \sum_{k=1..v(i)} A_ik

m = size(A,1); % num of rows
csA = cumsum(A, 2); % cumsum along rows
res = csA( sub2ind( size(A), 1:m, v ) ); % pick the vi-th column for the i-th row

Now, for your question, since you want the sum of all elements from v(i) to the end, we need to flip A and change v accordingly

[m n] = size(A);
fA = fliplr(A);
fv = n + 1 - v; % flip the meaning of v
csA = cumsum( fA, 2 ); 
res = csA( sub2ind( [m n], 1:m, fv ) ); % should do the trick...

answered Apr 25 '13 at 13:18

Shai

111,146
38
238
371

Very nice solution and designed better than my mask one since will use less memory. – Oleg Apr 25 '13 at 13:43
2

@OlegKomarov: No reason to delete your solution...I wanted to upvote it! – Rody Oldenhuis Apr 25 '13 at 13:45
1

@Shai I think you are missing a transpose: `res = csA( sub2ind( [m n], 1:m, fv ') );` as `v` is a column vector – Dan Apr 25 '13 at 13:47
1

It's like my physics professor: everything is correct up to a minus sign... (or transpose in my case) – Shai Apr 25 '13 at 13:50

Rody Oldenhuis · Answer 2 · 2013-04-25T22:00:10.513

3

I know it's kinda cheating, but how about:

S = arrayfun(@(ii) sum(A(ii, v(ii):end)), 1:size(A,1)).';

Usually I'm a bit weary when using arrayfun, but when comparing:

% sample data
N = 5000;

A = magic(N);
v = randi(N, N,1);


% simple loop
tic
    S = zeros(N,1);
    for ii = 1:N
        S(ii) = sum(A(ii, v(ii):end));
    end
toc


% arrayfun solution    
tic
    S = arrayfun(@(ii) sum(A(ii, v(ii):end)), 1:N).';
toc

% Shai's solution 
tic
    [m n] = size(A);
    fA = fliplr(A);
    fv = n + 1 - v; 
    csA = cumsum( fA, 2 ); 
    res = csA( sub2ind( [m n], 1:m, fv.' ) ).';
toc

Results:

Elapsed time is 0.386280 seconds. % simple loop
Elapsed time is 0.473916 seconds. % arrayfun
Elapsed time is 0.495794 seconds. % Shai's solution

So, arrayfun's not too bad after all.

But there is an important point here: Just look at the implementations from a distance. How easy to read/understand was the loop solution? How about the vectorized solutions?

With this in mind, also look at the performances. That's for a 5000x5000 matrix...that's 25 million elements there...

Now, would you really want to avoid that loop?

edited Apr 25 '13 at 22:00

answered Apr 25 '13 at 13:44

Rody Oldenhuis

37,726
7
50
96

you compare performance of loop and `arrayfun`? both solutions are not vectorizations of the code? – Shai Apr 25 '13 at 13:58
@Shai: Well, I started with "I know it's cheating", didn't I? :) But yes, in a sense, `arrayfun` is a vectorization of an *arbitrary* loop, just as `cumsum` is a vectorization of a *specific* loop. Especially in the context of `gpuArray`s, `arrayfun` is actually *more* 'vectorized' than `cumsum` is, since it will be vector-processed as well. But OK, I'll add a comparison to your method in a minute. – Rody Oldenhuis Apr 25 '13 at 14:21
@Shai: Also, you know [this question](http://stackoverflow.com/questions/12522888/arrayfun-can-be-significantly-slower-than-an-explicit-loop-in-matlab-why), right? So comparing loop with `arrayfun` *always* makes sense, if the `arrayfun` is to replace the loop. – Rody Oldenhuis Apr 25 '13 at 14:29
+1 for the comparison and the conclusion regarding readability of code! – Shai Apr 25 '13 at 14:30
1

+1 why do people hate for-loops? Dont get me wrong, I like coming up with clever vectorized solutions, but in some cases loops are not so bad :) – Amro Apr 25 '13 at 15:01
It would be useful to know what MATLAB version and OS those timing belong to. In my case Win7 64bit MATLAB 2013a: loop 0.175127 arrayfun 0.205083 and vectorized 0.156223. – Oleg Apr 25 '13 at 15:41
@OlegKomarov: See the updated timings. The new timings are for Ubuntu 12.10/64-bit, Matlb R2012a 64-bit, running on AMD PhenomII X6 1100T. I'm guessing you have an i7? – Rody Oldenhuis Apr 25 '13 at 22:02

Adding up different number of elements from each row

2 Answers2