CODEWITHSUNDEEP
matlabmaxmin
user2261062
user2261062

Reputation:

Efficient way of computing second min value

Given a matrix, it's easy to compute the value and index of the min value:

A = rand(10);
[value, index] = min(A(:));

However I would also like to recover the second min value (idem for max).

I can of course take any of this two approaches:

  1. Converting A to a vector and sorting it.

    PROS: I can then recover the second, third... n minimum value

    CONS: If A is large, sorting is expensive

  2. Once the min location of A is located, I can replace this value by a large one (eg: Inf) and then run min again.

    PROS: Cheaper than sort

    CONS: I must modify my matrix (and save the modified value in an aux variable). Also re-running min is costly on a large matrix.

I'm wondering if there is a better solution:

When computing min the algorithm has to keep track of the min value found so far, until a new value has a lower value (then we update the value). If instead we keep track of the last n min values found so far will allow to recover the minimum n values.

I can implement this, but I'm wondering if it's the best approach or if it's already implemented.

Upvotes: 6

Views: 1411

Answers (4)

Richard
Richard

Reputation: 1060

beesleep has already pointed out that method 2 (by computing the minimum twice) is more efficient that method 1 (by sorting). However the implementation provided in the answer to compute the index of the second minimum via find is, as mentioned, very inefficient.

In fact, to get the index of the second minimum, it is ca. 10x faster to set the first minimum value to inf (as suggested in the question) and then get the index of the second minimum from the min function (as opposed to using find)

[firstMin, firstMinIndex] = min(A(:));
A(firstMinIndex) = inf;
[secondMin, secondMinIndex] = min(A(:));

Here is the code which I used to compare this implementation to the one suggested by beesleep:

for i = 1:10

    A = rand(10000);

    tic
    [firstMin, firstMinIndex] = min(A(:));
    secondMin = min(A(A~=firstMin));
    secondMinIndex = find(A==secondMin); % slow, but use only if you need the index
    t1(i) = toc;

    tic
    [firstMin, firstMinIndex] = min(A(:));
    A(firstMinIndex) = inf;
    [secondMin, secondMinIndex] = min(A(:));
    t2(i) = toc;

end

disp(mean(t1) / mean(t2))

Upvotes: 0

beesleep
beesleep

Reputation: 1362

I don't know in which case it would be less expensive than sorting, but an easy, but not so fast way would be to use the following code. I may be wrong, but I don't think you can get faster with build-in functions if you just want the first and the second min.

A = rand(10);
[firstMin, firstMinIndex] = min(A(:));
secondMin = min(A(A~=firstMin));
secondMinIndex = find(A==secondMin); % slow, but use only if you need the index

Here, you go through the matrix two times more, one for the boolean operation, and one for the second min.

After some testing on 2000x2000 and 4000x4000 random matrix, it seems that this code snipset is around 3.5 time faster than the sort function applied on the same matrix.

If you really need more efficiency, you'd have to write your own mex routine, with which you can theoretically get the two values in n+log n-2 comparison, as explained in the link provided by @luismendotomas.

Hope this help !

Upvotes: 3

Nicky Mattsson
Nicky Mattsson

Reputation: 3052

As already mentioned I suppose the best (read: "most efficient") method is to implement the methods from @luismendotomas link.

However, if you want to avoid doing too much programming yourself, then you could apply some k-nearest neighbours algorithm, given you have a lower bound on your data, e.g. if all your data points are positive, you can find the 2 nearest neighbours to 0. Though I am not sure whether this is faster than your initial suggestions or not.

For one k-nearest neighbour algorithm see e.g. this

Upvotes: 0

Maurits
Maurits

Reputation: 2114

In a single pass:

a = [53 53 49 49 97 75 4 22 4 37];

first = Inf;
second = Inf;

for i = 1:1:numel(a)
    if (a(i) < first)
        second = first;
        first = a(i);
    elseif (a(i) < second && a(i) ~= first)
        second = a(i);
    end
end

fprintf('First smallest %d\n', first);
fprintf('Second smallest %d\n', second);

You can remove the a(i) ~= first condition if you rather have 4, 4 as output instead of 4, 23

Also, see this SO question

Upvotes: 0

Related Questions