Thread Subject: Vectorizing a nested for loop

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

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