6

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.

  • if you use `sort` you can have your 2x lowest min and 2x largest max in one single _expensive_ `sort` operation. Otherwise you have to run 2x `min` and 2x `max`. Make a test and find which approach is less expensive. – Hoki Feb 27 '17 at 11:04
  • True, but if min is able to keep track of the n lower values it won't be expensive at all. I think this would be a nice feature. You can give how many min values you want to recover as a optional parameter. –  Feb 27 '17 at 11:07
  • How big are we talking? `sort` is quite fast. Also, you can always (if you have it) `gpuarray` it. Reduces are very fast in GPUs – Ander Biguri Feb 27 '17 at 11:08
  • Have a look at [this](http://stackoverflow.com/q/3628718/2586922) – Luis Mendo Feb 27 '17 at 11:46
  • Also check Bruno's solutions (one is mex): https://www.mathworks.com/matlabcentral/newsreader/view_thread/309300 –  Feb 27 '17 at 14:16

4 Answers4

3

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 !

beesleep
  • 1,322
  • 8
  • 18
  • If you want only the 2nd min, you can use the index from the first call without going again through the matrix, like this: `[2nd_min,2nd_ind]=min(A(setdiff(1:numel(A),1st_ind)));`. but if you want n minimum values it gets more complicated, and you better use an appropriate algorithm... – Adiel Feb 27 '17 at 14:54
  • Adiel, In principle you should be right. But in practice matlab is way faster with logical indexing.... setdiff is also rather slow. On my computer logical indexing around 6 times faster than the code you propose ! – beesleep Feb 27 '17 at 18:27
  • Ok, nice to know. – Adiel Feb 28 '17 at 06:23
0

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

Community
  • 1
  • 1
Maurits
  • 2,082
  • 3
  • 28
  • 32
  • 1
    Yes, this is what I proposed at the end of the question, but I wanted to avoid using loops since they are slow. –  Feb 27 '17 at 14:50
0

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

Nicky Mattsson
  • 3,052
  • 12
  • 28
0

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))
Community
  • 1
  • 1
Richard
  • 1,020
  • 8
  • 16