Stuart’s MATLAB Videos

Watch and Learn

Puzzler: optimize this

Often when I post code, there is a discussion of how to optimize it. I tend to subscribe to this maxim:


Rules of Optimization:
Rule 1: Don’t do it.
Rule 2 (for experts only): Don’t do it yet.
— M.A. Jackson

The reason for that is many times coders will complicate their code in an effort to optimize it. This optimization is often premature. I recommend waiting until you know it is too slow or too memory intensive before putting in that effort and adding that complexity. Often times, the bottlenecks are not where you would expect at the beginning and readability would be sacrificed for only a marginal gain.

That being said, code optimization can be a fun way to show how clever you are. Here is your chance with a good puzzler brought to us by John D’Errico.

Given an NxN matrix, M, rearrange the columns such that sum(diag(M)) is minimized. I do not know for certain, but I think an exhaustive search is the only way to find the best possible solution. Since the exhaustive search is very time consuming, one does need to trade off search time versus result.

Here is the challenge:

Rewrite findTrace.m so that the calculated score is minimized. Notice the score formula:

sum(trace) + 10*time

This should give plenty of room to explore time versus results trade-offs.

Here is the code to get you started:

n = 15;
%
for i = 1 : 100
    mat = rand(n)*5;
%    
    tic
    [matOut, trace] = findTrace(mat);
    elapsed(i)      = toc;
%    
    sumTrace(i)     = sum(trace);
%   
end
%
score = (mean(sumTrace) + mean(elapsed)*10)

function [matOut, trace] = findTrace(matIn)
%
matOut = matIn;
trace = diag(matIn);

I think it would be fun to change n to see which code works best for different size inputs.


As always with these puzzlers, be sure to use the proper tags in the comments.


<pre> <code>
[deltaX, deltaY] = puzzler(inMatrix)
%% All the code so someone can just copy and paste it from the comments.
</code> </pre>
|

Comments

To leave a comment, please click here to sign in to your MathWorks Account or create a new one.