4
\$\begingroup\$

I'm currently working on a project where I am trying to predict a presidential election based on the population density and region of a voter. I wrote a few MATLAB functions to parse the data, but it takes about a minute to run, which seems long. My languages of choice are usually Java or Python and I feel like this calculation would only top a few seconds in those languages.

Quick side note: although this is for a school project, it is a simulation class, not a programming class. The code works, which is what is required, the efficiency of the code is personal interest.

Main test script

%test metrics
printf("starting test\n");
p0 = parsePopMap("density2010.png"); %not shown because this returns quickly
[vm,rp,dp] = metrics(p0);
printf("republican:%d\ndemocrat:%d\n",rp,dp)

metrics.m

%generate matrix determining republican vote
function [voteMatrix,republicanPixels,democratPixels] = metrics(popGraph)

voteMatrix = zeros(rows(popGraph),columns(popGraph));

republicanPixels=0;
democratPixels=0;
printf("loading regions\n");
%regions is a matrix of size == popGraph, has values from 1-6
%so that any regions(row,column) returns the region of the country
load regions; %based on the printout, this happens within seconds
printf("calculating votes\n");

%suspected bottleneck
for r = [1:rows(popGraph)]
    for c = [1:columns(popGraph)]
        pixelRegion = regions(r,c);
        if (pixelRegion == 6)
            voteMatrix(r,c)=-1; %because it is water
        else 
            vote = voteFromLocation(pixelRegion,popGraph(r,c));
            voteMatrix(r,c) = vote;
            if vote>.5
                republicanPixels +=1;
            else
                democratPixels +=1;
            end
        end
    endfor
endfor

voteFromLocation.m

function vote = voteFromLocation(region,popDens)



% array is percent for urban, suburban, rural 
% probability area will vote republican
voteAverage = [ [.375,.51,.79];%pacific coast
                [.40,.54,.765];%midwest
                [.30,.47,.48];%Northeast
                [.485,.625,.725];%south
                [.46,.62,.795]];%Mountains/plains
voteDelta = [   [.05,.06,.1];%pacific coast
                [.04,.04,.07];%midwest
                [.12,.06,.10];%northeast
                [.09,.07,.27];%south
                [.12,.08,.21]];%mountains/plains


%represents the max value of that demographic
ruralThresh = 900; %so <=900 is rural
subThresh = 1100; % 900<x<=1100 is suburban
%urban is anything above 1100

demo = -1;
if(popDens<=ruralThresh)
    demo = 3;
elseif(popDens<=subThresh)
    demo = 2;
else
    demo = 1;
end
mean = voteAverage(region,demo);
stdDev = voteDelta(region,demo);
probVoteRep = (mean + stdDev * randn());

vote = probVoteRep;

I believe the source of the bottleneck is the for loops of metrics.m. Most matrix processing I've seen uses different approaches, which I believe may be faster.

\$\endgroup\$
5
\$\begingroup\$

Replacing loops in MATLAB with equivalent matrix operations (a technique commonly referred to as vectorization) often, but not always, leads to improvements in performance. However, this frequently results in code that may be difficult for others to read, so it is advisable to use the profiler to identify bottlenecks and then try vectorizing only those sections of code where performance really matters. You could do something like this (outside the loop):

voteMatrix(regions == 6) = -1

This is equivalent to the first if condition in your loop. Try to do the same to the else condition. (Hint: you'll need to update your voteFromLocation method to handle arrays in the same manner.)

It's been a long time since I last used MATLAB, so my syntax may not be very accurate, but you get the general idea.

\$\endgroup\$
  • \$\begingroup\$ @Matt Wow, thanks! Your edit makes the answer much better. I wish I could vote you up! \$\endgroup\$ – Hosam Aly Sep 4 '12 at 9:33
5
\$\begingroup\$

You are without doubt correct in suspecting that the bottleneck is in the double loop over the regions matrix.

The sub2ind function is worth knowing about, because it allows you to write something like this:

% load or pass in popGraph, regions, voteAverage, voteDelta

% assert 2 == ndims(popGraph)
% assert 2 == ndims(regions)
% assert all(size(popGraph) == size(regions))

[nRows, nCols] = size(popGraph)

isRural    = popGraph <= ruralThresh
isUrban    = popGraph >= subThresh
isSuburban = ~isRural && ~isUrban
isSea      = 6 == regions

demo = ones(nRows, nCols)
demo(isRural)    = 3
demo(isSuberban) = 2
demo(isUrban)    = 1

indices = sub2ind(demo, regions)

meanvalue = voteAverage(indices)
stdvalue = voteDelta(indices)

probVoteRep = meanvalue + stdvalue * randn(nRows, nCols)
probVoteRep(isSea) = -1 

republicanPixels = zeros(nRows, nCols)
democratPixels   = zeros(nRows, nCols)

republicanPixels(probVoteRep >  0.5) = 1
democratPixels(  probVoteRep <= 0.5) = 1

(NOTE: I have not run this code, so it will probably not work without modification).

\$\endgroup\$
  • \$\begingroup\$ It's generally faster to use zeros(nRows, nCols) than using ones, but in the case above you could just comment the call to demo(isUrban) = 1 because you already initialized the whole array to ones. \$\endgroup\$ – Hosam Aly Jun 28 '12 at 21:02
  • 1
    \$\begingroup\$ I used demo = ones(nRows, nCols) because the variable demo was going to be used as an index, and, for quick-and-dirty scripts like this, it feels better to use a valid default value. I would have used nan(nRows, nCols) if correctness was more important, justifying a fail-fast approach). Also, I included the redundant assignment to demo(isUrban) for pedagogical reasons, on the assumption that reasonable readability trumps nth-degree efficiency in this case. \$\endgroup\$ – William Payne Jun 28 '12 at 23:30
2
\$\begingroup\$

The most useful advice, that I can give you, is using the Profiler of Matlab. It lets you measure where a program spends time and what portions of your code you should improve. Besides, see Programming Fundamentals/Performance/Techniques for Improving Performance in the Matlab Help documentation for more information about it.

\$\endgroup\$
  • 1
    \$\begingroup\$ The MATLAB profiler really is a very nice little tool. \$\endgroup\$ – William Payne Jun 28 '12 at 23:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.