OPR Programming Challenge

[Michael Hill]

Originally Posted by Ether

Nice work.

For those of you reading along, the timing above is for a dataset containing 2696 teams, 8921 matches, 17842 alliance scores.

@ Michael Hill: feel free to jump in here now if you want :-)

Fair enough. It's been a while since I've messed around with this, but I dug up my MATLAB script I originally did this with. I got it down to 0.518726 seconds (average over 10 runs.)

There are some optimizations that are done with this. For example, using sparse matrices lets MATLAB do a much quicker job of left divides (which is not the same as inverting the matrix). MATLAB is actually fairly smart and decides which form of factorization to use based on the data that's inputted, so it (generally) will choose the fastest method. Sparse is very fast.

tic
alldata = dlmread('C:\Users\Michael Hill\Documents\Projects\OPR\scores.dat');
teams = [alldata(:,1:3); alldata(:,4:6)];
reddiff = [alldata(:,7)-alldata(:,8)];
bluediff = [alldata(:,8)-alldata(:,7)];
scores = [alldata(:,7); alldata(:,8)];
diffscores = [reddiff; bluediff];
a = size(teams);
A = zeros(max(max(teams)));
B = zeros(max(max(teams)),2);
for i = 1:a(1)
    A(teams(i,1),teams(i,1)) = A(teams(i,1),teams(i,1)) + 1;
    A(teams(i,1),teams(i,2)) = A(teams(i,1),teams(i,2)) + 1;
    A(teams(i,1),teams(i,3)) = A(teams(i,1),teams(i,3)) + 1;
    A(teams(i,2),teams(i,1)) = A(teams(i,2),teams(i,1)) + 1;
    A(teams(i,2),teams(i,2)) = A(teams(i,2),teams(i,2)) + 1;
    A(teams(i,2),teams(i,3)) = A(teams(i,2),teams(i,3)) + 1;
    A(teams(i,3),teams(i,1)) = A(teams(i,3),teams(i,1)) + 1;
    A(teams(i,3),teams(i,2)) = A(teams(i,3),teams(i,2)) + 1;
    A(teams(i,3),teams(i,3)) = A(teams(i,3),teams(i,3)) + 1;
    B(teams(i,1),1) = B(teams(i,1),1) + scores(i);
    B(teams(i,2),1) = B(teams(i,2),1) + scores(i);
    B(teams(i,3),1) = B(teams(i,3),1) + scores(i);
    B(teams(i,1),2) = B(teams(i,1),2) + diffscores(i);
    B(teams(i,2),2) = B(teams(i,2),2) + diffscores(i);
    B(teams(i,3),2) = B(teams(i,3),2) + diffscores(i);
end

%gpuA = gpuArray(A);
%gpuB = gpuArray(B);
A = sparse(A);
B = sparse(B);
A(~any(A,2), :) = [];
A(:, ~any(A,1)) = [];
B(~any(B,2), :) = [];
X = A\B(:,1);
Y = A\B(:,2);
D = X-Y;

tdupe = sort([teams(:,1);teams(:,2);teams(:,3)]);
[junk, index] = unique(tdupe,'first');
teamList = tdupe(sort(index));
numTeams = size(teamList);
out = zeros(numTeams(1),4);
for i = 1:size(teamList)
    out(i,1) = teamList(i);
    out(i,2) = gather(X(i));
    out(i,3) = gather(Y(i));
    out(i,4) = gather(D(i));
end

% expectedRed = zeros(a(1)/2,1);
% expectedBlue = zeros(a(1)/2,1);
% for i=1:a(1)/2
%     index1 = find(out(:,1)==alldata(i,1));
%     index2 = find(out(:,1)==alldata(i,2));
%     index3 = find(out(:,1)==alldata(i,3));
%     index4 = find(out(:,1)==alldata(i,4));
%     index5 = find(out(:,1)==alldata(i,5));
%     index6 = find(out(:,1)==alldata(i,6));
%     opr1 = out(index1,2);
%     opr2 = out(index2,2);
%     opr3 = out(index3,2);
%     opr4 = out(index4,2);
%     opr5 = out(index5,2);
%     opr6 = out(index6,2);
%     expectedRed(i) = opr1+opr2+opr3;
%     expectedBlue(i) = opr4+opr5+opr6;
% end
% 
% diffExpRed = expectedRed - alldata(:,7);
% diffExpBlue = expectedBlue - alldata(:,8);
% 
% diffExp = [diffExpBlue; diffExpRed];
% 
% C = zeros(gather(max(max(teams))));
% for i = 1:a(1)
%     C(teams(i,1)) = C(teams(i,1)) + diffExp(i);
%     C(teams(i,2)) = C(teams(i,2)) + diffExp(i);
%     C(teams(i,3)) = C(teams(i,3)) + diffExp(i);
% end
% gpuC = gpuArray(C);
% gpuC(~any(gpuC,2), :) = [];
% Z = gpuA\gpuC(:,1);
% for i = 1:size(teamList)
%     out(i,5) = gather(Z(i));
% end
disp(out);
toc

There are some remnants in the comments of me messing with gpuArrays on MATLAB, and I'm too lazy to get rid of them. I have a Quadro K1100M Graphics card in my laptop, so I was messing around with using CUDA cores. It turns out that MATLAB has not implemented sparse matrices with CUDA processing, so they have to be full matrices, which actually slows it down (fairly significantly) over using sparse matrices with calculation on the CPU. For the record, my CPU is an Intel i7-4702HQ @ 2.2 GHz with 16 GB of RAM (My Computer is a Dell Precision M3800).

EDIT: I actually just realized there was some code that slows it down in there. the "gather"s in developing the "out" matrix are more remnants of GPU computing that I didn't take out. They are used for getting the variables out of GPU memory to my RAM. After removing them, It took total computation time to about 0.48 seconds.