File Exchange

image thumbnail

findNlargest

version 1.0 (3.15 KB) by

Finds the N largest values in the input. Very fast.

0 Downloads

Updated

View License

LARGEVALUES = findNlargest(INPUTVALUES, N)

Finds the N largest values in INPUTVALUES and outputs them to LARGEVALUES

[LARGEVALUES, INDEX] = findNlargest(INPUTVALUES, N)

INDEX is the index of the returned values in the original INPUTVALUES

Example:

L = findNlargest([2 7 7 6 -1],3)

L =

6
7
7

Written in c, so the operation is fast. Type "mex findNlargest.c" in matlab before use.

You might need a free compiler if it was not installed with your matlab:
http://www.mathworks.com/support/compilers/R2012b/win64.html

Comments and Ratings (4)

Bruno Luong

Bruno Luong (view profile)

Ah sorry, I overlook the index part.

Bruno, I see that you have also written a very nice implementation for this purpose (mink and maxk). Again using your example with a million points, I find that if N is 1000, findNlargest runs about 2.5 times faster than maxk, but for larger N maxk is faster. If the poolsize is 5 million and N is 1000, findNlargest is over 7 times faster than maxk. So, users should be aware that this function is specialized for choosing a small number of values from a large pool. Otherwise maxk and mink will perform better in the general case.

Hi Bruno,
As far as retrieving the index goes, it seems to work fine when I do it:

a = rand(1,1e6);
[x,index] = findNlargest(a,5)

x =

1.0000
1.0000
1.0000
1.0000
1.0000

index =

878652
294446
965700
961872
165538

In this case, if there are more than 5 of the same max value, then the first 5 would be chosen.

And for the second point, yes, this code is intended for cases when you are choosing a small number of values from a large pool. In your example (with a pool of a million values), if N = 5, my code is about 40 times faster than sorting. If N = 1000, my code is 6 times faster. Once N is greater than half the sample size, it makes more sense to find the poolsize-N smallest values. (see findNsmallest).

Bruno Luong

Bruno Luong (view profile)

- It is not possible to retreive the index of the largest elements.

- Very fast, yes when N is small, but it is NOT when N is large.

This code shows findNlargest can be 550 times slower than sorting:

a = rand(1,1e6);
N = 1e5;
tic; x2=findNlargest(a, N); toc; % 10.913513 seconds.
tic; x3=sort(a); x3=x3(1:N); toc % 0.020251 seconds.

MATLAB Release
MATLAB 7 (R14)

Download apps, toolboxes, and other File Exchange content using Add-On Explorer in MATLAB.

» Watch video

findNlargest/