Code covered by the BSD License  

Highlights from
findNlargest

4.0

4.0 | 2 ratings Rate this file 7 Downloads (last 30 days) File Size: 3.15 KB File ID: #39877

findNlargest

by

 

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

| Watch this File

File Information
Description

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

MATLAB release MATLAB 7 (R14)
Other requirements mex compiler (free)
Tags for This File   Please login to tag files.
Please login to add a comment or rating.
Comments and Ratings (4)
18 Jan 2013 Bruno Luong

Ah sorry, I overlook the index part.

18 Jan 2013 Mattias Karlsson

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.

18 Jan 2013 Mattias Karlsson

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).

17 Jan 2013 Bruno Luong

- 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.

Contact us