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

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

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

Answer by Thorsten
on 28 Jan 2013

Ytemp = [1:M_MAX]'*[1:N_MAX];

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)];

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

Florin
on 28 Jan 2013

Thanks for the input!

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

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.

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!

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.

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);

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.

Related Content

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

Learn moreOpportunities for recent engineering grads.

Apply Today
## 0 Comments