Code covered by the BSD License  

Highlights from
Min/Max selection

4.69231

4.7 | 13 ratings Rate this file 90 Downloads (last 30 days) File Size: 21.8 KB File ID: #23576

Min/Max selection

by

 

07 Apr 2009 (Updated )

Search for k smallest or largest elements in the array

| Watch this File

File Information
Description

Using a partial quick-sort algorithm implemented with C-MEX. The complexity is O(n + k.log(k)), where n is the size of the array, and k is the number of elements to be selected.

Faster than SORT or multiple call of MIN/MAX for large size inputs.

Multidimensional capability supported

MATLAB release MATLAB 7.3 (R2006b)
Tags for This File   Please login to tag files.
Please login to add a comment or rating.
Comments and Ratings (40)
25 Oct 2013 Mara

Bruno, which comments? I tried compiling the mex files by hand, but with no success. I get the following error.

No supported SDK or compiler was found on this computer.
For a list of supported compilers, see
http://www.mathworks.com/support/compilers/R2013a/win64.html

Error using mex (line 206)
Unable to complete successfully.

25 Oct 2013 Bruno Luong

Mara, see older comments for workaround.

24 Oct 2013 Mara

I am having trouble installing this package on R2013a. I run minmax_install and get the following output. Thank you for any suggestions.

Mara

-------------

Error using getmexopts (line 36)
getmexopts [Bruno]: cannot open comopts.bat file

Error in minmax_install (line 20)
compiler = getmexopts('COMPILER');

24 May 2013 Yuanjun Xiong

Great function!

27 Apr 2013 Rui

Bruno,

Sorry. I introduced a typo to your codes. When I replaced // by /*, I forgot to add */.

Now it is working!

27 Apr 2013 Rui

Bruno,

Thanks a lot! Now there's a new error on the last line...

At first I thought, maybe there's a missing brace, however the I found that was not the case. The new code was working with matlab 32 bit build-in compiler, but not the LCC on linux.

Rui
-----------------------

minkmex.c: In function ?MinMaxResult?:
minkmex.c:293: warning: incompatible implicit declaration of built-in function ?memset?
minkmex.c: In function ?LocResult?:
minkmex.c:322: warning: incompatible implicit declaration of built-in function ?memset?
minkmex.c: In function ?mexFunction?:
minkmex.c:580: error: expected declaration or statement at end of input

mex: compile of ' "minkmex.c"' failed.

??? Error using ==> mex at 208
Unable to complete successfully.

Error in ==> minmax_install at 46
mex(mexopts{:},'minkmex.c');

26 Apr 2013 Bruno Luong

Rui,
The error is in line #544 (look at the error message). Try to replace the C++ comment style
// in case the positive set is unordered
by C comment style
/* in case the positive set is unordered */

26 Apr 2013 Rui

Hi Bruno,

I like this function. I got a lot of fun with it on Windows, but when I switched to Linux server with GCC compiler, it did not work. The error was the same as jianbo posted two years ago. I tried to modify minkmex.c file as you suggested, (replace "memset((data+p0), 0, sizeof(double)*nz)" with "memset((void*)(data+p0), 0, sizeof(double)*nz)") but it did not work. I tired both matlab 2012a and 2010b on our server, but neither worked. Could you help me on it? Thanks in advance!

--------------------

minkmex.c: In function ?MinMaxResult?:
minkmex.c:293: warning: incompatible implicit declaration of built-in function ?memset?
minkmex.c: In function ?LocResult?:
minkmex.c:322: warning: incompatible implicit declaration of built-in function ?memset?
minkmex.c: In function ?mexFunction?:
minkmex.c:544: error: expected expression before ?/? token

mex: compile of ' "minkmex.c"' failed.

??? Error using ==> mex at 208
Unable to complete successfully.

Error in ==> minmax_install at 46
mex(mexopts{:},'minkmex.c');

09 Nov 2012 Wok  
28 Jul 2012 Bruno Luong

To Durga, The help of the function indicates that when apply on the array, k largest element of each columns will be returned.

If you want to apply for the entire array, just reshape it.

>> [res loc]=mink(list(:),5);
>> [loci locj]=ind2sub(size(list),loc)

The comparison timings you made is irrelevant since you compare the codes that achieve different jobs.

27 Jul 2012 Durga Lal Shrestha

Sorry for previous rating, it was problem due to the FLEX website. I clicked back button on browser not "Submit" button.

I was searching the function that finds the kth largest or smallest values and locations of 2d array and thought that this is the function. But it appears it produces different results that I expected

list = 1:16;
list = reshape(list,4,4)
[res loc]= mink(list,5)

list =

1 5 9 13
2 6 10 14
3 7 11 15
4 8 12 16

res =

1 5 9 13
2 6 10 14
3 7 11 15
4 8 12 16

loc =

1 1 1 1
2 2 2 2
3 3 3 3
4 4 4 4

I thought it produces the max or min of the whole array. So I have written my own program minmax which produces the results

[res,loci,locj] = minmax(list,5)

out =

1
2
3
4
5

loci =

1
2
3
4
1

locj =

1
1
1
1
2

In terms of speed, I do not think it is efficient, see below

list = 1:1000000;
list = reshape(list,1000,1000);
tic
[res loc]= mink(list,5);
toc

%%
tic
[out,loci,locj] = minmax(list,5);
toc

Elapsed time is 0.046343 seconds.
Elapsed time is 0.039491 seconds.

27 Jul 2012 Durga Lal Shrestha  
13 Apr 2012 Cristobal

Thx Bruno!

13 Apr 2012 Bruno Luong

@Cristobal, post installation: please use addpath() to add the folder to Matlab search path.

12 Apr 2012 Cristobal

After running "minmax_install" it worked just fine. But when I reopened Matlab I got the following problem. It gets fixed after running the installation file again, but it last for a short time.

??? Undefined function or method 'inplacecolumnmex' for input arguments of type
'double'.

Error in ==> minmaxk at 110
cn = inplacecolumnmex(list,n); % inplace column

Regards

05 Dec 2011 jianbo  
05 Dec 2011 Bruno Luong

@jianbo,

Try to change

memset((void*)(data+p0), 0, sizeof(double)*nz)

and

/* in case the positive set is unordered */

05 Dec 2011 jianbo

Hi
I try to compile(by GCC under Linux) minkmex.c/maxkmex.c, and encounter an error like

I did not figure out how to modify your C source file to fix the problem. I think your C implementation should be cross-platform.

minkmex.c: In function ‘MinMaxResult’:
minkmex.c:293:5: warning: incompatible implicit declaration of built-in function ‘memset’
minkmex.c: In function ‘LocResult’:
minkmex.c:322:5: warning: incompatible implicit declaration of built-in function ‘memset’
minkmex.c: In function ‘mexFunction’:
minkmex.c:544:25: error: expected expression before ‘/’ token

mex: compile of ' "minkmex.c"' failed.

24 Jul 2011 Bruno Luong

Hi Elisa,

I just check the file inplacecolumnmex.c is included in the package. Set the place where the files is unzipped as default before launching the installation function.

23 Jul 2011 elisa

Hi
i cant use this interesting code. when i run minimax_install, the following error appear:
Error: 'inplacecolumnmex.c' not found.

??? Error using ==> mex at 207
Unable to complete successfully.

Error in ==> minmax_install at 28
mex(mexopts{:},'inplacecolumnmex.c');
please help me
thanks

02 Jun 2011 Bruno Luong

Amin, Yes there is issues with 2010b. please see my post from 23/Nov/2010 for workaround. Hope it helps.

02 Jun 2011 Amin

hi
first of all, i really appreciate your work. as it seems, it is very efficient.

but the problem is i still cant run it, although i used your fixed version for v2010b.
i used testminmax.m

here is what i get:

??? Error using ==> buildInternal_mxArrayDef at 35
Cannot parse matrix.h file

Error in ==> minmax_install at 25
buildInternal_mxArrayDef('Internal_mxArray.h');

Error in ==> testminmax at 11
minmax_install();

05 Mar 2011 Bruno Luong

Hi, Eric, I do not have access to Linux and can't not know what is wrong with the installation of server.

If you comment the two lines #28/29 of the minmax_install, is the installation able to pursue?

% mex(mexopts{:},'inplacecolumnmex.c');
% mex(mexopts{:},'releaseinplace.c');

If yes, you can work around and change the line #91 and #104 of the file minmaxk.m to

if true || issparse(list)
...
end

% Bruno

Bruno

04 Mar 2011 Eric

I try minmax_install in a server without root account and get this error:

mex: inplacecolumnmex.c not a normal file or does not exist.

??? Error using ==> mex at 218
Unable to complete successfully.

Error in ==> minmax_install at 28
mex(mexopts{:},'inplacecolumnmex.c');

What does it mean and what can I do? Matlab details are:
Version 7.8.0.347 (R2009a) 64-bit (glnxa64)

08 Dec 2010 Peter Li

This is a nice implementation. I have posted a very similar solution here: http://www.mathworks.com/matlabcentral/fileexchange/29453-nthelement. nth_element is a built in part of the C++ standard library specification that does something very similar to what Bruno has implemented here in pure C.

Right now I believe the primary differences between my version and this one are that mine is not written to work on sparse matrices while this version does, and mine is written to work with different numerical types while this version doesn't. With my compiler I find that the C++ version is also about 50% faster (runtimes 33% shorter).

Perhaps we should try to collaborate on future releases?

01 Dec 2010 Huangmao

Great! It works now. Thank you:)

23 Nov 2010 Bruno Luong

Oops sorry, you can copy past this declarartion to Internal_mxArray.h, then mex the rest.

/*
Internal_mxArray.h
Matlab version: 2010B
*/

typedef struct {
void *reserved;
int reserved1[2];
void *reserved2;
size_t number_of_dims;
unsigned int reserved3;
struct {
unsigned int flag0 : 1;
unsigned int flag1 : 1;
unsigned int flag2 : 1;
unsigned int flag3 : 1;
unsigned int flag4 : 1;
unsigned int flag5 : 1;
unsigned int flag6 : 1;
unsigned int flag7 : 1;
unsigned int flag7a: 1;
unsigned int flag8 : 1;
unsigned int flag9 : 1;
unsigned int flag10 : 1;
unsigned int flag11 : 4;
unsigned int flag12 : 8;
unsigned int flag13 : 8;
} flags;
size_t reserved4[2];
union {
struct {
void *pdata;
void *pimag_data;
void *reserved5;
size_t reserved6[3];
} number_array;
} data;
} Internal_mxArray;

23 Nov 2010 Chiyuan

I'm afraid manually compiling won't work. Because Internal_mxArray.h is need for compiling. But this file is generated by buildInternal_mxArrayDef which will fail to run under R2010b since parsing matrix.h fails. :-(

19 Nov 2010 Bruno Luong

I'm aware of the compilation issue with 2010B, and I still not able to find a good fix. A workaround is compile by hand the four mex files:

% On 32-bit platform
mex inplacecolumnmex.c
mex releaseinplace.c
mex minkmex.c
mex maxkmex.c

or on 64-bit platform
mex -largeArrayDims inplacecolumnmex.c
mex -largeArrayDims releaseinplace.c
mex -largeArrayDims minkmex.c
mex -largeArrayDims maxkmex.c

19 Nov 2010 Huangmao

I tried to install it on MATLAB 7.11.0 (R2010b), and got errors:
>> minmax_install
??? Error using ==> buildInternal_mxArrayDef at 35
Cannot parse matrix.h file

Error in ==> minmax_install at 25
buildInternal_mxArrayDef('Internal_mxArray.h');

Any ideas to fix this?

16 Aug 2010 Joshua Dillon

resolved. thanks!

16 Aug 2010 Bruno Luong

Joschua, thanks for the report. I have correct the code and hopefully it resolves these two issues.

13 Aug 2010 Joshua Dillon

There is also a problem dealing with NaNs. The easiest fix is to shadow mink.m (conversely maxk.m with):

I = isnan(varargin{1});
if any(I(:))
warning('MATLAB:maxk:hasNan',...
'Input has NaN values. All NaN values will be treated as +Inf. ');
varargin{1}(I)=+Inf;
end

nout=cell(1,max(0,nargout-2));
[out1 out2 nout{:}] = minmaxk(@maxkmex, varargin{:});
varargout={out1 out2 nout{:}};

13 Aug 2010 Joshua Dillon

I have observed the following SERIOUS bug:

>> x=sparse([1 100 150 900 15000],1,[.4992 .4 0 0 .001],30e3,1,5);
>> maxk(x)
ans =
3.8063e+295
>> [a I]=maxk(x)
a =
0.4992
I =
1

05 May 2010 Siyi Deng

awesome code!

10 Jan 2010 Jan Simon

Thanks! Efficient (see note), really tricky+fast usage of shared values for columns accessing, sophisticated sorting, good documentation and an installation method, which considers different Matlab versions. Excellent for teaching using shared data copies in Mex files!

Although this function is not designed to work on small arrays, for this case the VARARGIN/VARARGOUT overhead might be avoidable. E.g. MINK:
function varargout=mink(varargin)
nout = cell(1, max(1, nargout));
[nout{:}] = minmaxk(@minkmex, varargin{:});
vargargout=nout;
10% faster for MINK(1:100, 10):
function [V, Idx] = mink(list, k)
if nargin == 1, k = 1; end
if nargout == 2,
[V, Idx] = minmaxk(@minkmex, list, k);
else, V = minmaxk(@minkmex, list, k);
end
For large inputs, this is obviously negligible. But there are no drawbacks.

NOTE: I've compared this with dull brute force search of the K.th smallest/largest elements. I'll send you the source by mail and be glad for your comments.

05 Dec 2009 Matt Fetterman  
03 Oct 2009 Rencheng Á

Thanks! It is very useful!

28 Sep 2009 Bruno Luong

Marcello,

Do you have MEX setup? If not, type he following in command line:
>> mex -setup

If it's already installed you have to locate mexopts.bat file somewhere under the directory $MATLABROOT (where the Matlab is installed), then modify OPTPATH variable in line #8 and line #12 of GETMEXOPTS.

then try installation again.

Bruno

28 Sep 2009 Dude25

That's look interesting.
How can I compile it?
When i try to install it with "minmax_install" i get the following error: "getmexopts [Bruno]: cannot open comopts.bat file".
How does this file have to look like?

thx
marcello

Updates
07 Apr 2009

Bug correction (for k=0)
Do not compute unnecessary location indexes when not required.

24 May 2009

Supported sparse input

26 Jun 2009

handle arrays with NaN

29 Jun 2009

Correct bug + inplace engine

11 Aug 2009

Correct bug: cleanup the inplace variable when MEX issues an error (otherwise computer might crash)

10 Jan 2010

Possibility to disable post-sorting step

16 Aug 2010

Fix the bugs for sparse and all-NaN vector

05 Mar 2011

Specific installation for R2010B

27 Aug 2011

Change installation script, now copy prototype header file for V2010B or later.
Correct BUG when working on sparse matrix.

29 Apr 2013

Fix C/C++ comment style issue

Contact us