4
\$\begingroup\$

My homework assignment:

Write a function called saddle that finds saddle points in the input matrix M. For the purposes of this problem, a saddle point is defined as an element whose value is greater than or equal to every element in its row, and less than or equal to every element in its column. Note that there may be more than one saddle point in M. Return a matrix called indices that has exactly two columns. Each row of indices corresponds to one saddle point with the first element of the row containing the row index of the saddle point and the second element containing the column index. If there is no saddle point in M, then indices is the empty array.

My solution:

function ind=saddle(matrix)

size_=size(matrix);
a=[];
for ii=1:size_(1)

    for jj=1:size_(2)
        if (matrix(ii,jj)==max(matrix(ii,:))) && (matrix(ii,jj)==min(matrix(:,jj)))
            a=[a;[ii ,jj]];
        end
    end
end
ind=a;   
\$\endgroup\$
3
\$\begingroup\$

Your solution works, but it will be quite slow. For every element in your matrix (m*n many), you check if it is the maximum in the row (n comparisons), and then check if it is the minimum in the column (m comparisons). This will mean that you do a total of m*n*(m+n) many comparisons. You can save some time by only computing the maximum and minimum once, going down to m*n + m + n.

Also, MATLAB hates for loops. Built-ins are optimized and can take advantage of any hardware acceleration or parallelism that your computer offers. Loops on the other hand are always executed sequentially. If you can avoid them and use built-ins instead, it will usually make your code faster.

function [row, col]=saddle(matrix)

% first lets get the min/max for the column/row respectively
minima = min(matrix,[],1) % minimum of each column
maxima = max(matrix,[],2) % maximum of each row

% then, for each element in the column/row check if it matches the min/max
isMinimum = minima == matrix
isMaximum = matrix == maxima

% it needs to be both to be a saddle
saddles = isMinimum & isMaximum

% lastly, figure out the index of each saddle point
% and transform it to the desired output format
[row, col] = find(saddles)

Disclaimer: My MATLAB licence expired this week and I have to wait to renew it. The above code is untested, so there might be the odd typo.

\$\endgroup\$
  • \$\begingroup\$ MATLAB used to hate loops 15 years ago. Nowadays there is a JIT compiler that makes loops quite reasonable. That said, if loops are not necessary you usually get more readable code without them. Also, bsxfun is outdated, it is cheaper to directly compare a row vector to a column vector or to a full matrix. Google “implicit singleton expansion”. \$\endgroup\$ – Cris Luengo Jun 30 at 22:26
  • \$\begingroup\$ Oh, and find with two output arguments returns the row and column numbers directly. \$\endgroup\$ – Cris Luengo Jun 30 at 22:29
  • \$\begingroup\$ @CrisLuengo good pointers! JIT will compile the loop body, which makes things a lot faster, but it won't vectorize code. Hence my remark to avoid loops (and vectorize) if possible. \$\endgroup\$ – FirefoxMetzger Jul 2 at 7:53

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.