File Exchange

image thumbnail

Min/Max selection

version 1.15.0.0 (20.5 KB) by Bruno Luong

Bruno Luong (view profile)
Search for k smallest or largest elements in the array
4.7
22 Ratings

3 Downloads

Updated 20 May 2016

View License

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

Comments and Ratings (61)

Muhammad Hanif

Muhammad Hanif (view profile)

Useful addition

Xiaodong

Xiaodong (view profile)

The conflict with the official Matlab 2017b persists. Are your code adapted by Mathworks in the official release?

Xiaodong

Xiaodong (view profile)

So, on Matlab 2017b pre-release and maybe also the coming official Matlab 2017b, both maxk and mink functions have conflict with the builtin Matlab functions. Could you rename them to avoid these conflicts? Just to let you know that I found this problem while running 2017b pre-release. Thanks!

chenfei mao

chenfei mao (view profile)

Wrong usage getmexopts (line 38)
getmexopts [Bruno]: cannot open comopts.bat file

error minmax_install (line 20)
compiler = getmexopts('COMPILER');
When running, how to solve the above problems?

Michal Kvasnicka

Michal Kvasnicka (view profile)

Very good code, but should be multi-threaded as built-in sort algorithm!!!

Kun He

Kun He (view profile)

@Marko @kaare: I had success getting second output by changing line 93 in minmaxk.m to:

[res(:,n) loc(:,n)] = mexfun(list(:,n), k);

Marko Filipovic

Marko Filipovic (view profile)

Worked perfectly until R2014b, but using it on R2016a crashes Matlab. If I employ fix suggested by Mr. Luong, then the same error that kaare described appears.

------------------------------------
One or more output arguments not assigned during call to "maxkmex".

Error in minmaxk (line 93)
[res(:,n) loc(:,n) dummy] = mexfun(list(:,n),k); %#ok

Error in maxk (line 19)
[nout{:}] = minmaxk(@maxkmex, varargin{:});
------------------------------------

Since in my case two outputs are necessary, this means I can't use this function anymore.

Marko Filipovic

Marko Filipovic (view profile)

ray mccarthy

ray mccarthy (view profile)

this is hard to install :(

Zakaria Cetinov

Zakaria Cetinov (view profile)

Carl Witthoft

Carl Witthoft (view profile)

Just want to warn users that a pure sorting tool like this (which is very good btw) is useful when you've got integer data. If you've got an array of floats, you're more likely to want to do a spline fit and find the true min/max , i.e. remove noise in the data.

kaare

kaare (view profile)

I et an error when requesting the second output from mink:

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

One or more output arguments not assigned during call to "minkmex".

Error in minmaxk (line 93)
[res(:,n) loc(:,n) dummy] = mexfun(list(:,n),k); %#ok

Error in mink (line 20)
[nout{:}] = minmaxk(@minkmex, varargin{:});

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

this error disappears if I only require 1 output

Ehsan GhasemiMoghadam

Ehsan GhasemiMoghadam (view profile)

I have an error on 2015b 64bit (MacOSX10.11) during installing function. Already, I installed Xcode7.1.1 on OSX10.11 .
During installing, the function searches "MacOSX10.9.sdk" & "MacOSX10.9.sdk", but the correct folder is "MacOSX10.11.sdk".

error:
Did not find installed compiler 'Xcode with Clang'.
Error using mex
No supported compiler or SDK was found. For options, visit
http://www.mathworks.com/support/compilers/R2015b/maci64.html.
Error in minmax_install (line 42)
mex(mexopts{:},'inplacecolumnmex.c');

Bruno Luong

Bruno Luong (view profile)

For those who have crash issues with recent matlab, I pinpoint to the accessing of internal MATLAB data structure that has been changed.

The workaround is to replace 2 statement of minmaxk (line #91, 104) by:

if ~verLessThan('MATLAB', '8.3') || issparse(list)
...
end

This will run slightly slower run don't crash.

Sorry

Vincent Zhang

Vincent Zhang (view profile)

I also experienced the same issue with 2015b 64bits (Linux).

Guillaume

Guillaume (view profile)

I have a crash on 2015b 64bits (Mac) during testing function.

Jerry Gregoire

Jerry Gregoire (view profile)

Quick and easy. What I was looking for. Saved me from writing it myself.

Chang hsiung

Chang hsiung (view profile)

I tried with Matlab 2014b 64bits and still not working.

Shamanth MK

Shamanth MK (view profile)

Bruno Luong

Bruno Luong (view profile)

@JUNBO please replace line #19 of minmax_install.m with this:

if ispc() && datenum(version('-date')) < datenum('January 11, 2014')

JUNBO

JUNBO (view profile)

Hi, Bruno

I am using Matlab 2014a 64x, after installing a SDK 7.1, it still doesn't work, and shows the following messages:
-----------------------------
>> mex -setup
MEX ==> 'Microsoft Windows SDK 7.1 (C)'
Warning: The MATLAB C and Fortran API has changed to support MATLAB
variables with more than 2^32-1 elements. In the near future
you will be required to update your code to utilize the
new API. You can find more information about this at:
http://www.mathworks.com/help/matlab/matlab_external/upgrading-mex-files-to-use-64-bit-api.html.
-----------------------------
and then
testminmax
error getmexopts (line 36)
getmexopts [Bruno]: cannot open comopts.bat file

error minmax_install (line 20)
compiler = getmexopts('COMPILER');

error testminmax (line 11)
minmax_install();
----------------------
Could you help to solve this problem? Thanks!

Junbo

Mara

Mara (view profile)

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.

Bruno Luong

Bruno Luong (view profile)

Mara, see older comments for workaround.

Mara

Mara (view profile)

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');

Yuanjun Xiong

Yuanjun Xiong (view profile)

Great function!

Rui

Rui (view profile)

Bruno,

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

Now it is working!

Rui

Rui (view profile)

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');

Bruno Luong

Bruno Luong (view profile)

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 */

Rui

Rui (view profile)

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');

Wok

Wok (view profile)

Bruno Luong

Bruno Luong (view profile)

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.

Durga Lal Shrestha

Durga Lal Shrestha (view profile)

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.

Durga Lal Shrestha

Durga Lal Shrestha (view profile)

Cristobal

Cristobal (view profile)

Thx Bruno!

Bruno Luong

Bruno Luong (view profile)

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

Cristobal

Cristobal (view profile)

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

jianbo

jianbo (view profile)

Bruno Luong

Bruno Luong (view profile)

@jianbo,

Try to change

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

and

/* in case the positive set is unordered */

jianbo

jianbo (view profile)

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.

Bruno Luong

Bruno Luong (view profile)

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.

elisa

elisa (view profile)

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

Bruno Luong

Bruno Luong (view profile)

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

Amin

Amin (view profile)

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();

Bruno Luong

Bruno Luong (view profile)

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

Eric

Eric (view profile)

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)

Peter Li

Peter Li (view profile)

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?

Huangmao

Huangmao (view profile)

Great! It works now. Thank you:)

Bruno Luong

Bruno Luong (view profile)

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;

Chiyuan

Chiyuan (view profile)

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

Bruno Luong

Bruno Luong (view profile)

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

Huangmao

Huangmao (view profile)

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?

Joshua Dillon

Joshua Dillon (view profile)

resolved. thanks!

Bruno Luong

Bruno Luong (view profile)

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

Joshua Dillon

Joshua Dillon (view profile)

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{:}};

Joshua Dillon

Joshua Dillon (view profile)

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

Siyi Deng

Siyi Deng (view profile)

awesome code!

Jan

Jan (view profile)

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.

Matt Fetterman

Matt Fetterman (view profile)

Rencheng Á

Rencheng Á (view profile)

Thanks! It is very useful!

Bruno Luong

Bruno Luong (view profile)

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

Dude25

Dude25 (view profile)

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

1.15.0.0

Disable inplace arrays for more recent MATLAB versions
Fix issue with dummy argument not assigned
1.14.0.0

Fix install issue with R2014
1.13.0.0

Fix C/C++ comment style issue
1.12.0.0

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

Specific installation for R2010B
1.10.0.0

Fix the bugs for sparse and all-NaN vector
1.9.0.0

Possibility to disable post-sorting step
1.8.0.0

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

Correct bug + inplace engine
1.6.0.0

handle arrays with NaN
1.5.0.0

Supported sparse input
1.1.0.0

Bug correction (for k=0)
Do not compute unnecessary location indexes when not required.
MATLAB Release Compatibility
Created with R2006b
Compatible with any release
Platform Compatibility
Windows macOS Linux

MinMaxSelection/