Simplifying for loop (matlab)

Question

I am working on a program at work to calculate what a plane could see as it fly's over a target area. As it goes over the area it could follow one of many tracks, around 100 for the normal area size. I have created a large loop to see if the plane can see parts of the area or not but it runs very inefficiently. I have defined the area as a grid 1001x1001

xgrid a variable 1001x1 defining the x-values.

thelines is a variable 2 x 1001 x tracks, where the first row is the y-values at the corresponding x-value for the top line. The second row is the y-values for the bottom line.

Between these two lines is the visible area. If it can be seen it marks the point on seenarea(1001x1001) as a 1. If not its a 0.

for M=1:tracks
    for f=1:1001
        for i=1:1001
            if xgrid(f,1)>thelines(i,1,M) && xgrid(f,1)<thelines(i,2,M);
                seenarea(f,i,M)=1; % This indicated the area has been seen
            else
                seenarea(f,i,M)=0; % This is not seen
            end
        end
    end
    fullbestinfo(1,M)={seenarea(:,:,M)}; % This stores the seen area in another cell
    if max(seenarea(:,:,M)) < 1 % No area seen, stop
        seenarea(:,:,M)=[];
        break
    end
end

I have identified this point at the bottleneck of my program using the matlab profiler. Any help would be much appreciated. Thanks, Rich

Answer 1

I can't quite tell exactly what you're trying to do, but I suggest as a first step replacing the inner loops with logical indexing.

seenarea = false(1001, 1001, tracks); #% preallocate matrix to 'false'
xgrid = repmat(1:1001, 1001, 1); #%same size as the first 2D of seenarea

for M=1:tracks
    border1 = thelines(:,ones(1,1001),M); #% same size as xgrid
    border2 = thelines(:,ones(1,1001)*2,M); #% same size as xgrid
    idx = xgrid > border1 & xgrid < border2; #% idx is a "logical index" 
             #%           ^--- single ampersand
    seenarea(idx,M)=true; 
end

Using logical indexing, you can replace the million or so iterations of your nested loops with a single operation.

Here's another tip: Use a logical matrix instead of a double matrix to store true/false values.

>>m1 = zeros(1001,1001,100);
>> m2 = false(1001,1001,100);
>> whos m1
  Name         Size                      Bytes  Class     Attributes

  m1        1001x1001x100            801600800  double              

>> whos m2
  Name         Size                      Bytes  Class      Attributes

  m2        1001x1001x100            100200100  logical 

As you can see, the memory usage is 8 times lower for the logical matrix.

Speed test: I was curious just how large a difference this would make. Below is a quick test (well, quick only for one of the implementations). Vectorizing the inner loops led to a roughly 75-fold increase in speed on my machine, decreasing the time for 10 tracks from 7+ seconds to roughly 0.1 seconds.

tic;
for rep=1:100
    for M=1:tracks
        for f=1:1001
            for i=1:1001
                if xgrid(f,1)>thelines(i,1,M) && xgrid(f,1)<thelines(i,2,M);
                    seenarea(f,i,M)=1; 
                else
                    seenarea(f,i,M)=0; 
                end
            end
        end
    end
end
disp(toc/100)
    7.3459

tic;
for rep=1:100
    for M=1:tracks
        border1 = thelines(:,ones(1,1001),M); 
        border2 = thelines(:,ones(1,1001)*2,M); 
        idx = xgrid > border1 & xgrid < border2;                     
        seenarea(idx,M)=true; 
    end
end
disp(toc/100)
    0.0964

>> 7.3459/.0964    
ans =    
   76.2023