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

Thread Subject:
Optimize to get rid of loop

Subject: Optimize to get rid of loop

From: Daphne

Date: 26 Feb, 2009 05:52:02

Message: 1 of 7


Is it possible to at least get rid of one loop here?
Note that the length of n and k is not the same...

    for n = 1:s
        for k = n+1:s
            rg = rg + ( bead(k,1) - bead(n,1) )^2 + ( bead(k,2) - bead(n,2) )^2 ;
        end
    end


Thanks,
Daphne

Subject: Optimize to get rid of loop

From: Matt Fig

Date: 26 Feb, 2009 06:22:02

Message: 2 of 7

Your account of what you are doing is not complete, yet I will make a guess:



bead = round(rand(8,2)*10)
s = size(bead,1);
rg = 0;

for n = 1:s
    for k = n+1:s
        rg = rg + ( bead(k,1) - bead(n,1) )^2 + ( bead(k,2) - bead(n,2) )^2;
    end
end
rg
%------------- Method 2 ----------------------%
S = nchoosek(1:size(bead,1),2);
rg2 = sum((bead(S(:,1),1)-bead(S(:,2),1)).^2 +...
          (bead(S(:,1),2)-bead(S(:,2),2)).^2)





J]Bh_bXT#JLhh^hNYN6hhoXoQN.X]hK]RUvJQJVhYKJWQXXPLRU)XN^JJVW

Subject: Optimize to get rid of loop

From: Roger Stafford

Date: 26 Feb, 2009 06:52:01

Message: 3 of 7

"Daphne" <daphnew_too_nospam@yahoo.com> wrote in message <go5am2$g2a$1@fred.mathworks.com>...
> Is it possible to at least get rid of one loop here?
> Note that the length of n and k is not the same...
>
> for n = 1:s
> for k = n+1:s
> rg = rg + ( bead(k,1) - bead(n,1) )^2 + ( bead(k,2) - bead(n,2) )^2 ;
> end
> end
>
> Thanks,
> Daphne

 rg = n*(sum(bead(:,1).^2)+sum(bead(:,2).^2)) ...
       - (sum(bead(:,1))^2+sum(bead(:,2))^2);

Roger Stafford

Subject: Optimize to get rid of loop

From: Roger Stafford

Date: 26 Feb, 2009 07:01:05

Message: 4 of 7

"Roger Stafford" <ellieandrogerxyzzy@mindspring.com.invalid> wrote in message <go5e6h$8of$1@fred.mathworks.com>...
> rg = n*(sum(bead(:,1).^2)+sum(bead(:,2).^2)) ...
> - (sum(bead(:,1))^2+sum(bead(:,2))^2);
> ......

Note 1;
  I should have used 's' instead of 'n' in that formula.

Note 2:
  For large s the round-off errors may be somewhat larger in this formula but the total execution time should be considerably smaller. The algorithm is order s, as opposed to order s^2.

Roger Stafford

Subject: Optimize to get rid of loop

From: Roger Stafford

Date: 26 Feb, 2009 08:44:02

Message: 5 of 7

"Daphne" <daphnew_too_nospam@yahoo.com> wrote in message <go5am2$g2a$1@fred.mathworks.com>...
>
> Is it possible to at least get rid of one loop here?
> Note that the length of n and k is not the same...
>
> for n = 1:s
> for k = n+1:s
> rg = rg + ( bead(k,1) - bead(n,1) )^2 + ( bead(k,2) - bead(n,2) )^2 ;
> end
> end
>
>
> Thanks,
> Daphne

  By way of further elucidation on that sum of yours, Daphne, it is in fact a certain multiple, namely s*(s-1), of the sum of the unbiased variances of the two columns of 'bead', and that is surely the best way to calculate it. That method is both fast (order s) and accurate.

 rg = s*(s-1)*(var(bead(1:s,1))+var(bead(1:s,2)));

Roger Stafford

Subject: Optimize to get rid of loop

From: Daphne

Date: 26 Feb, 2009 10:56:01

Message: 6 of 7


Thanks for this!

Went with your second suggestion. It is a bit slower, but also a tiny bit more accurate on my data, and in any case is still 5 (!!) orders of magnitude faster...
Wow.

Thanks,
Daphne


"Roger Stafford" <ellieandrogerxyzzy@mindspring.com.invalid> wrote in message <go5koi$jb9$1@fred.mathworks.com>...
> "Daphne" <daphnew_too_nospam@yahoo.com> wrote in message <go5am2$g2a$1@fred.mathworks.com>...
> >
> > Is it possible to at least get rid of one loop here?
> > Note that the length of n and k is not the same...
> >
> > for n = 1:s
> > for k = n+1:s
> > rg = rg + ( bead(k,1) - bead(n,1) )^2 + ( bead(k,2) - bead(n,2) )^2 ;
> > end
> > end
> >
> >
> > Thanks,
> > Daphne
>
> By way of further elucidation on that sum of yours, Daphne, it is in fact a certain multiple, namely s*(s-1), of the sum of the unbiased variances of the two columns of 'bead', and that is surely the best way to calculate it. That method is both fast (order s) and accurate.
>
> rg = s*(s-1)*(var(bead(1:s,1))+var(bead(1:s,2)));
>
> Roger Stafford

Subject: Optimize to get rid of loop

From: Roger Stafford

Date: 26 Feb, 2009 21:14:01

Message: 7 of 7

"Daphne" <daphnew_too_nospam@yahoo.com> wrote in message <go5sg1$jn2$1@fred.mathworks.com>...
> .....
> Went with your second suggestion. It is a bit slower, but also a tiny bit more accurate on my data, and in any case is still 5 (!!) orders of magnitude faster...
> .....

  Yes, subtracting the mean value as is done in calculating the variance should increase the accuracy noticeably.

  The reason this method is faster is that it is performing far fewer additions and multiplications. This has little to do with the use of for-loops. As you must have seen, vectorizing your for-loops does not produce this kind of improvement.

  For just three elements [A,B,C] it is a matter of the following reasoning. Let m = (A+B+C)/3 and a = A-m, b = B-m, c = C-m, then we have that a+b+c=0 and

 (A-B)^2+(A-C)^2+(B-C)^2 =
 (a-b)^2+(a-c)^2+(b-c)^2 =
 2*(a^2+b^2+c^2) - (2*a*b+2*a*c+2*b*c) =
 3*(a^2+b^2+c^2) - (a^2+b^2+c^2+2*a*b+2*a*c+2*b*c) =
 3*(a^2+b^2+c^2) - (a+b+c)^2 =
 3*(a^2+b^2+c^2) - 0 = 3*(a^2+b^2+c^2)

This latter is 3*2=6 times the unbiased variance, or s*(s-1) times in the general case.

  Of course for three elements there is little or no gain but for a large 's' value this same kind of algebraic substitution will result in a very impressive improvement in efficiency.

Roger Stafford

Tags for this Thread

What are tags?

A tag is like a keyword or category label associated with each thread. Tags make it easier for you to find threads of interest.

Anyone can tag a thread. Tags are public and visible to everyone.

Contact us