Min/Max selection

Search for k smallest or largest elements in the array

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)

[Yuanjun Xiong]

Great function!

[Rui]

Bruno,

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

Now it is working!

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

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

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

[Wok]

 

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

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

[Durga Lal Shrestha]

 

[Cristobal]

Thx Bruno!

[Bruno Luong]

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

[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

[jianbo]

 

[Bruno Luong]

@jianbo,

Try to change

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

and

/* in case the positive set is unordered */

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

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

[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

[Bruno Luong]

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

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

[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

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

[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?

[Huangmao]

Great! It works now. Thank you:)

[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;

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

[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

[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?

[Joshua Dillon]

resolved. thanks!

[Bruno Luong]

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

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

[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

[Siyi Deng]

awesome code!

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

[Matt Fetterman]

 

[Rencheng Á]

Thanks! It is very useful!

[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

[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