Discover MakerZone

MATLAB and Simulink resources for Arduino, LEGO, and Raspberry Pi

Learn more

Discover what MATLAB® can do for your career.

Opportunities for recent engineering grads.

Apply Today

Matlab matrix operations without loops

Asked by Florin on 28 Jan 2013

Hello. I have an issue with a code performing some array operations. It is getting to slow, because I am using loops. I am trying for some time to optimize this code and to re-write it with less or without loops. Until now unsuccessful. Can you please help me solve this:

YVal = 1:1:100000;
M_MAX = 1000;
N_MAX = 2000;
clear YTemp
tic
for M=1:1:M_MAX 
    for N = 1:1:N_MAX 
       YTemp(M,N) = sum(YVal (N+1:N+M)  ) - sum(YVal   (1:M)  );  
    end
end

For large N_MAX and M_MAX the execution time of these two loops is very high. How can I optimize this?

Thank you,

Florin

0 Comments

Florin

Products

6 Answers

Answer by Azzi Abdelmalek on 28 Jan 2013
Edited by Azzi Abdelmalek on 28 Jan 2013
Accepted answer

Try his code, 200 faster

YVal = 1:1:100000;
M_MAX = 1000;
N_MAX = 2000;
tic
som1=zeros(1,M_MAX+N_MAX);
YTemp=zeros(M_MAX,N_MAX);
for k=1:M_MAX+N_MAX
  som1(k)=sum(YVal(1:k));
end
for M=1:1:M_MAX % Number of accumulated periods
  som2=som1(M+1)-YVal(1);
  for N = 1:1:N_MAX % statistic
    YTemp(M,N) = som2- som1(M);  
    som2=som2+YVal(N+M+1)-YVal(N+1);
  end 
end
toc

3 Comments

Florin on 28 Jan 2013

:) Thank you for the input! It is fast, indeed.

Jan Simon on 28 Jan 2013

MLint moans, that som1 should be pre-allocated.

Azzi Abdelmalek on 28 Jan 2013

Ok, I will do it

Azzi Abdelmalek
Answer by Thorsten on 28 Jan 2013
 Ytemp = [1:M_MAX]'*[1:N_MAX];

1 Comment

Florin on 28 Jan 2013

Hello!

Thank you for the fast answer. This works perfectly in case if

 YVal = 1:1:100000;

Though, if I change this to

YVal = 1:2:100000 or rand(1, 100000) 

this will not work any more

I Tried:

Ytemp = [YVal(1:M_MAX)]'*[YVal(1:N_MAX)];
Thorsten
Answer by Azzi Abdelmalek on 28 Jan 2013
Edited by Azzi Abdelmalek on 28 Jan 2013

You can begin by pre-allocating

YTemp=zeros(M_MAX,N_MAX);
YVal = 1:1:100000;
M_MAX = 1000;
N_MAX = 2000;
YTemp=zeros(M_MAX,N_MAX);
for k=1:M_MAX
  som1(k)=sum(YVal(1:k));
end
tic
for M=1:1:M_MAX % Number of accumulated periods
  for N = 1:1:N_MAX % statistic
     YTemp(M,N) = sum(YVal(N+1:N+M)) - som1(M);  
  end
end
toc

This code is three times faster

1 Comment

Florin on 28 Jan 2013

Thanks for the input!

Azzi Abdelmalek
Answer by Jan Simon on 28 Jan 2013
Edited by Jan Simon on 28 Jan 2013

No, the code is not slow due to the loops, but due to a missing pre-allocation and repeated work. Please measure the speed of this:

YVal  = 1:100000;
M_MAX = 1000;
N_MAX = 2000;
YTemp = zeros(M_MAX, N_MAX);
tic
a = 0;
for M = 1:M_MAX % Number of accumulated periods
    a = a + YVal(M);                 % sum(YVal(1:M))
    b = a;
    for N = 1:N_MAX                  % statistic
       b = b - YVal(N) + YVal(N+M);  % sum(YVal(N+1:N+M))
       YTemp(M, N) = b - a;
    end
end
toc

 

[EDITED] In fact, the code can be simplified:

YVal  = 1:100000;
M_MAX = 1000;
N_MAX = 2000;
YTemp = zeros(M_MAX, N_MAX);
for M = 1:M_MAX % Number of accumulated periods
    b = 0;
    for N = 1:N_MAX                  % statistic
       b = b - YVal(N) + YVal(N+M);  % sum(YVal(N+1:N+M))
       YTemp(M, N) = b;
    end
end

2 Comments

Florin on 28 Jan 2013

Hmmm... At some point I tried to to some pre-allocation, but not so deep.

Your code, on my machine, is ~18 times faster. Thank you! Next time I will remember this lesson.

Jan Simon on 28 Jan 2013

Here only the ZEROS call pre-allocates. Avoiding the repeated summation helps also according to the simple rule, that all repeated work wastes time - as in the real life also.

Jan Simon
Answer by Florin on 28 Jan 2013
Edited by Florin on 28 Jan 2013

Both answers from Azzi Abdelmaleka and Jan Simon are very helpful, regarding the matter of runtime optimization. Though, I am still curious if you can do this without loops.

Thank you guys and have a nice day!

1 Comment

Jan Simon on 28 Jan 2013

Does my answer reply the correct result? I do not have access to Matlab currently, but if it is correct, there is no dependency to "a" in the inner loop: At first "b" is initialized to "a", than "a" is subtracted in each iteration. Therefore I could imagine, that 2 CUMSUMs could be sufficient, but I cannot try this at the moment.

Florin
Answer by Teja Muppirala on 28 Jan 2013

Your entire script is equivalent to this:

M_MAX = 1000;
N_MAX = 2000;
YTemp  = (1:M_MAX)'*(1:N_MAX);

3 Comments

Azzi Abdelmalek on 28 Jan 2013

Look at Thorsten's answer (the same) and the comment of OP

Teja Muppirala on 28 Jan 2013

Ah, I see, I should have read that. This works quickly, but it's not very readable.

YVal = rand(1,1e6);
M_MAX = 1000;
N_MAX = 2000;
YS = cumsum(YVal);
YTemp = bsxfun(@minus, YS( bsxfun(@plus,(1:N_MAX),(1:M_MAX)') ) , YS(1:N_MAX));
YTemp = bsxfun(@minus, YTemp, YS(1:M_MAX)');
Florin on 29 Jan 2013

This is what I was looking for (regarding code optimization without using loops)! Thank you.

Teja Muppirala

Contact us