Path: news.mathworks.com!not-for-mail
From: <HIDDEN>
Newsgroups: comp.soft-sys.matlab
Subject: Re: avoiding loops to built a z matrix of the most efficient form
Date: Thu, 26 Mar 2009 00:09:01 +0000 (UTC)
Organization: Univ of Newcastle upon Tyne
Lines: 137
Message-ID: <gqeh2t$aqc$1@fred.mathworks.com>
References: <gqdj93$qa4$1@fred.mathworks.com> <gqdn0i$a5r$1@fred.mathworks.com> <gqdr01$jp4$1@fred.mathworks.com> <gqduat$hug$1@fred.mathworks.com> <gqdvgd$bvg$1@fred.mathworks.com> <gqe1nl$cra$1@fred.mathworks.com> <gqe4fp$1ml$1@fred.mathworks.com> <gqe6ja$4fg$1@fred.mathworks.com> <gqe7j5$evd$1@fred.mathworks.com> <gqe7ud$9vm$1@fred.mathworks.com>
Reply-To: <HIDDEN>
NNTP-Posting-Host: webapp-05-blr.mathworks.com
Content-Type: text/plain; charset="ISO-8859-1"
Content-Transfer-Encoding: 8bit
X-Trace: fred.mathworks.com 1238026141 11084 172.30.248.35 (26 Mar 2009 00:09:01 GMT)
X-Complaints-To: news@mathworks.com
NNTP-Posting-Date: Thu, 26 Mar 2009 00:09:01 +0000 (UTC)
X-Newsreader: MATLAB Central Newsreader 1511480
Xref: news.mathworks.com comp.soft-sys.matlab:527787

"Matt Fig" <spamanon@yahoo.com> wrote in message <gqe7ud$9vm$1@fred.mathworks.com>...
> "Matt Fig" <spamanon@yahoo.com> wrote in message <gqe7j5$evd$1@fred.mathworks.com>...
> > As is often the case, I noticed an improvement that could be made after I posted.  On my machine this is as fast as any other.  Though definitely not as cool as Bruno's final offer.
> > 
> > 
> > tic
> > z = zeros(1,nrv);
> > for jj = 1:nrv
> >     tmp2 = [v1(:,1)-v2(jj,1) v1(:,2)-v2(jj,2)];
> >     tmp3 = tmp2*inversa;
> >     zm(jj) = sum(tmp3(:,1).*tmp2(:,1) + tmp3(:,2).*tmp2(:,2));
> > end
> > toc
> 
> 
> 
> Notice I didn't pre-allocate correctly (embarrassed z ~=zm)!  With the correct pre-allocation, this is fastest of all.  Good old For loops!


Hello guys, 
in summary up to the moment the most faster code to work with big 2D-data points v1 and 2D-parameters v2 is done for Bruno (without loops), number 4.

(Look at the results).


%piece of code
clear all
clc


nrv=3000; % number of 2D-parameters 

nrp=5000; % number of 2D-data points 

v1=rand(nrp,2);
v2=rand(nrv,2);

inversa=[1 2; 3 4];

     
1. Roger

tic 

 z = repmat(v1,nrv,1)-reshape(repmat(reshape(v2,1,[]),nrp,1),[],2);
 z = sum(reshape(sum(((z*inversa).*z),2),nrp,nrv));


toc

2. Bruno

tic
vdiff=reshape(bsxfun(@minus,...
              reshape(v1,[nrp 1 2]),...
              reshape(v2,[1 nrv 2])), ...
             [],2);
z = sum(reshape(sum((vdiff*inversa).*vdiff,2), ...
         [nrp nrv]),1);

toc


3. Bruno (improved)

tic
bfun=@(x) sum((x*inversa).*x,2);
qfun=@(x,y) (x*(inversa+inversa.')*y.');
z=sum(bsxfun(@plus,bfun(v1),bfun(v2).')-qfun(v1,v2),1);
toc

4. Bruno (Much better)

tic
bfun=@(x) sum((x*inversa).*x,2);
z=(sum(bfun(v1))+nrp*bfun(v2) - ...
    (v2*((inversa+inversa.')*sum(v1,1).'))).';

toc


5. Matt 

tic
z = zeros(1,nrv);
r = ones(nrp,1);
for jj = 1:nrv
    tmp = v2(jj,:);
    tmp2 = v1 - tmp(r,:);
    tmp3 = tmp2*inversa;
    z(jj) = sum(tmp3(:,1).*tmp2(:,1) + tmp3(:,2).*tmp2(:,2));
end
toc 


6. Matt (improved)

tic 
z = zeros(1,nrv);
for jj = 1:nrv
    tmp2 = [v1(:,1)-v2(jj,1) v1(:,2)-v2(jj,2)];
    tmp3 = tmp2*inversa;
    zm(jj) = sum(tmp3(:,1).*tmp2(:,1) + tmp3(:,2).*tmp2(:,2));
end
toc


7. Matt (much better)

tic
z = zeros(1,nrv);
for jj = 1:nrv
tmp2 = [v1(:,1)-v2(jj,1) v1(:,2)-v2(jj,2)];
tmp3 = tmp2*inversa;
zm(jj) = sum(tmp3(:,1).*tmp2(:,1) + tmp3(:,2).*tmp2(:,2));
end
toc

Results:

without loops:
1.Roger : Elapsed time is 4.267860 seconds.
2.Bruno :Elapsed time is 2.731296 seconds.
3.Bruno (improved): Elapsed time is 0.818409 seconds.
4.Bruno (much better) Elapsed time is 0.015496 seconds.

with lopps:

5.Matt :Elapsed time is 1.031870 seconds.
6.Matt (improve) Elapsed time is 0.462994 seconds.
7.Matt (much better)Elapsed time is 0.449142 seconds.

The code number 4 made for Bruno (without loops) is the most efficient code to built the z matrix with big 2D-data points v1 and 2D-parameters v2.

Althought the code (with loops) is not so bad result as  I showed with my inefficient code called Jose, therefore Matt is right.

Jose.