Path: news.mathworks.com!newsfeed-00.mathworks.com!newsfeed2.dallas1.level3.net!news.level3.com!postnews.google.com!e3g2000cwe.googlegroups.com!not-for-mail
From: wegwerp@gmail.com
Newsgroups: comp.soft-sys.matlab
Subject: Re: Vectorizing a nested for loop
Date: 12 Nov 2006 08:53:48 -0800
Organization: http://groups.google.com
Lines: 62
Message-ID: <1163350428.029000.44390@e3g2000cwe.googlegroups.com>
References: <ef45c76.-1@webcrossing.raydaftYaTP>
NNTP-Posting-Host: 82.210.117.33
Mime-Version: 1.0
Content-Type: text/plain; charset="us-ascii"
X-Trace: posting.google.com 1163350433 17930 127.0.0.1 (12 Nov 2006 16:53:53 GMT)
X-Complaints-To: groups-abuse@google.com
NNTP-Posting-Date: Sun, 12 Nov 2006 16:53:53 +0000 (UTC)
User-Agent: G2/1.0
X-HTTP-UserAgent: Mozilla/5.0 (Windows; U; Windows NT 5.0; en-US; rv:1.8.0.8) Gecko/20061025 Firefox/1.5.0.8,gzip(gfe),gzip(gfe)
Complaints-To: groups-abuse@google.com
Injection-Info: e3g2000cwe.googlegroups.com; posting-host=82.210.117.33;
Xref: news.mathworks.com comp.soft-sys.matlab:378355



Mike Stachowsky wrote:
> Hello all,
>
> I'm a beginner to matlab and am looking at a code that runs for so
> long it won't complete in a reasonable amount of time! Its a nested
> for loop shown below:
>
>       entropy = zeros(8,8);
>             for k=1:8
>             %now we figure out entropy
>                  for h = 1:8
>                      n=length(find(coords(:,1)<(-100 +(k*200/8)) &
> coords(:,1)>(-100 + (k-1)*200/8) & coords(:,2) < (-100 +
> (h*200/8)) & coords(:,2)>(-100 + (h-1)*200/8)));
>                      if(n~=0)
>                      entropy(k,h) = -(n/400)*(log(n/400));
>                      else
>                      entropy(k,h)=0;
>                      end
>                 end
>             end
>
> now the problem is that i can't figure out how it can be vectorized.
> here's what it does:
>
> It searches an array of coordinates (x,y) of random dots spread about
> the screen. it breaks up the entire plane into an 8x8 grid, and
> finds how many of those dots are in each grid box.
>
> The problem is that the dots are moved each time through, so in fact
> this nested for loop is itself nested in another for loop that runs
> one million times! clearly 8x8 a million times is unnacceptable for
> runtime.
>
> besides the trivial solution of running the 8x8 for loop once every
> 1000 times rather than each time through the loop, is there a way to
> make this code run faster?
>
> Mike

My idea is to first calculate for every datapoint in which box it falls
and then do some sort of histogram function. My hack would be to not
use 2d coordinates, but with a 0..63 number, and reshaping to a matrix
later.

Untested (only have matlab at work), so check the details yourself:

%assuming that coords are guaranteed to fall within boxes
nbox = 8;
boxwidth = 200/nbox;

%calculate boxnum for each coord = x+nbox*y = 0..63
boxnum = fix((coords(:,1)+100) /boxwidth) + nbox*fix((coords(:,2)+100)
/boxwidth);
N = hist(boxnum, 0:63); % or something with histc
entropy = -(N/400)*(log(N/400));
entropy(isnan(entropy)) = 0; %fix up bad points
entropy = reshape(entropy,nbox,nbox); %reshape to square

HTH,
Bas