Presidential election predictor using matrix-processing

Question

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.

Answer 1

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.

Answer 2

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).

Answer 3

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.