second largest element in a matrix
Oluwa KuIse
Can anyone pls tell me how I can find the second (or third) largest element in a matrix AND its position. The max function gives the largest element and its position but how do I find the second largest element and its position?
stephanie
> Hello,
> Can anyone pls tell me how I can find the second (or third) largest element in a matrix AND its position. The max function gives the largest element and its position but how do I find the second largest element and its position?
There are 2 rudimentary ways that I can think of off the top of my head...none of them are optimal though..
1. Use max to find the largest element, then set this element to -Inf. Then use max again to find the 'next'(ie, second) largest element and its position.
This method is definitely only a quick heck, and not suitable for looking for the Nth largest element in case N in large.
2. Sort the matrix, then you will know the value of the second largest element, then use 'find' to get the position of this element.
Hope this helps,
stephanie
Steven Lord
Call SORT with two output arguments.
--
Steve Lord
sl...@mathworks.com
Oluwa KuIse
"Steven Lord" <sl...@mathworks.com> wrote in message <gavast$1dd$1...@fred.mathworks.com>...
Pekka
Example for m by n matrix:
m=3;n=4;ggg = rand(m,n);
[svals,idx] = sort(ggg(:),'descend'); % sort to vector
svals(2) % second largest value
[II,JJ] = ind2sub([m,n],idx(2)) % position in the matrix
Oluwa KuIse
"Pekka " <pekka.nospam...@tut.please.fi> wrote in message <gavern$shn$1...@fred.mathworks.com>...
Greg Heath
> "Oluwa KuIse" <wespeakfo...@yahoo.com> wrote in message
>
> news:gav3p9$som$1...@fred.mathworks.com...
>
> > Hello,
> > Can anyone pls tell me how I can find the second (or third) largest
> > element in a matrix AND its position. The max function gives the largest
> > element and its position but how do I find the second largest element and
> > its position?
>
> Call SORT with two output arguments.
You could also use sort on A(:).
Hope this helps.
Greg
Walter Roberson
> Can anyone pls tell me how I can find the second (or third) largest element in a
> matrix AND its position.
The algorithms that people gave all ran in -at least- time N (length of the
matrix) times the number of largest elements to be found.
I was interested to discover a couple of weeks ago that there are simple
algorithms that for any fixed number L of largest elements, are able to
execute a -single- pass over the array and using L (or was it L+1 ?)
temporary storage locations, find the L largest values.
Unfortunately in the short time I put into reading the algorithm, I did
not understand how the algorithm worked, so I cannot describe it here.
And I no longer recall where I found the algorithm -- though either as
a reference here or on wikipedia are the two most likely candidates.
Justin
Walter Roberson <robe...@hushmail.com> wrote in message <STjCk.14881$Il....@newsfe09.iad>...
Paul
> Hello,
> Can anyone pls tell me how I can find the second (or third) largest element in a matrix AND its position. The max function gives the largest element and its position but how do I find the second largest element and its position?
if temp is your vector, you can get the second largest element as follows:
[c,i] = max(temp(temp~=max(temp)))
why would you sort it?
this is the whole point of logical addressing in matlab.
Paul
> Can anyone pls tell me how I can find the second (or third) largest element in a matrix AND its position. The max function gives the largest element and its position but how do I find the second largest element and its position?
if temp is your vector, you can get the second largest element as follows:
Matt Fig
>
> [c,i] = max(temp(temp~=max(temp)))
> why would you sort it?
> this is the whole point of logical addressing in matlab.
% Some Data
temp = [8 -1 0 1 2 -3 -8 0 5 -4]
% Proposed method
[c,i] = max(temp(temp~=max(temp)));
% As a check:
[srt,idx] = sort(temp,'descend');
idx2 = find(srt~=srt(1),1);
secondhighest = srt(idx2);
location = idx(idx2);
% isequal?
[secondhighest==c,location==i]
Have I misunderstood your proposal?
Matt Fig
R = temp; % Preserve R.
R(~(R~=max(R))) = NaN;
[c,i] = max(R);
Matt Fig
Walter Roberson
Depends on the matrix sizes. max() is an order(N) operation. sort is something like
order (N*log(N)). With large matrices, two linear passes through the matrix would be
considerably faster than a sort().
Note: in previous postings, someone posted a reference to a linear-time routine
to find the "Q largest" values in a vector; that code would only pass through the
matrix once (but might make up to Q comparisons at each point in order to establish
the proper ordering.)
Matt Fig
> Depends on the matrix sizes. max() is an order(N) operation. sort is something like
> order (N*log(N)). With large matrices, two linear passes through the matrix would be
> considerably faster than a sort().
>
> Note: in previous postings, someone posted a reference to a linear-time routine
> to find the "Q largest" values in a vector; that code would only pass through the
> matrix once (but might make up to Q comparisons at each point in order to establish
> the proper ordering.)
True enough, but I was accounting for the copy time in the comparisons I made (apples to apples ---> We start with a vector and end with the vector intact plus the second largest value and its index.)
Nevertheless my timings show you are correct. The relative speed of the approach shown above increases as N gets larger and larger.
N -------------- tsort/tnan
1000--------1.12703739213806
10^4--------1.33
10^5--------1.36
10^6--------1.67
10^7--------2.2
Bruno Luong
While searching something related to a stable quicksort I bump into this article:
http://en.wikipedia.org/wiki/Selection_algorithm
The interesting part are "Optimised Sorting algorithm" and "Tournament algorithm".
Bruno
Jos
Bruno & Walter,
have you seen my KTHVALUE submission on the FEX?
http://www.mathworks.com/matlabcentral/fileexchange/23195
Best,
Jos
Bruno Luong
>
> Bruno & Walter,
>
> have you seen my KTHVALUE submission on the FEX?
> http://www.mathworks.com/matlabcentral/fileexchange/23195
>
> Best,
> Jos
Hi Jos,
Now I see it. Thanks.
Bruno
Bruno Luong
Thanks,
Bruno
/**************************************************************************
* function [res loc] = minkmex(list, k)
* Matlab C-Mex
* Purpose: Same as MINK, i.e.,
* Return in RES the K smallest elements of LIST
* RES is sorted in ascending order [res loc] = mink(...)
* Location of the smallest: RES=LIST(LOC)
* But this MEX works on double, and output RES is unsorted
* Algorithm according to http://en.wikipedia.org/wiki/Selection_algorithm
* Compilation: mex -O -v minkmex.c
* Author Bruno Luong <bruno...@yahoo.com>
* Last update: 06/April/2009
*************************************************************************/
#include "mex.h"
#include "matrix.h"
#define _DEBUG
/* Global variables, used to avoid stacking them during recusive call since
they do not change */
mwSize k;
mwSize *pos;
double *list;
/* Partitioning the list around pivot pivotValue := l[pivotIndex];
* After runing, at exit we obtain:
l[left]...l[index-1] < pivotValue <= l[index] ... l[right]
where l[i] := list[pos[i]] for all i */
mwSize partition(mwSize left, mwSize right, mwSize pivotIndex) {
double pivotValue;
mwSize *pindex, *pi, *pright;
mwSize tmp;
pright=pos+right;
pindex=pos+pivotIndex;
pivotValue = list[tmp = *pindex];
/* Swap pos[pivotIndex] with pos[right] */
*pindex = *pright;
*pright = tmp;
pindex=pos+left;
for (pi=pindex; pi<pright; pi++)
/* Compare with pivotValue */
if (list[*pi] < pivotValue) {
/* if smaller; Swap pos[index] with p[i] */
tmp = *pindex;
*pindex = *pi;
*pi = tmp;
pindex++;
}
/* Swap pos[index] with p[right] */
tmp = *pindex;
*pindex = *pright;
*pright = tmp;
return (pindex-pos); /* Pointer arithmetic */
} /* Partition */
/* Recursive engine (partial quicksort) */
void findFirstK(mwSize left, mwSize right) {
mwSize pivotIndex;
if (right > left) {
pivotIndex = partition(left, right, (left+right+1)/2);
if (pivotIndex > k)
findFirstK(left, pivotIndex-1);
else if (pivotIndex < k)
findFirstK(pivotIndex+1, right);
}
return;
} /* findFirstK */
/* Gateway of minkmex */
void mexFunction(int nlhs, mxArray *plhs[],
int nrhs, const mxArray *prhs[]) {
mwSize l, i;
double *data;
mwSize dims[2];
/* Check arguments */
if (nrhs<2)
mexErrMsgTxt("MINKMEX: Two input arguments required.");
if (!mxIsNumeric(prhs[0]))
mexErrMsgTxt("MINKMEX: First input LIST argument must be numeric.");
if (!mxIsNumeric(prhs[1]))
mexErrMsgTxt("MINKMEX: Second input K must be numeric.");
/* Get the number of elements of the list of subindexes */
if (mxGetM(prhs[0])==1)
l = mxGetN(prhs[0]);
else if (mxGetN(prhs[0])==1)
l = mxGetM(prhs[0]);
else
mexErrMsgTxt("MINKMEX: First input LIST must be a vector.");
if (mxGetClassID(prhs[0]) != mxDOUBLE_CLASS)
mexErrMsgTxt("MINKMEX: First input LIST must be a double.");
/* Get the number of elements of the list of subindexes */
if (mxGetM(prhs[1])!=1 || mxGetN(prhs[1])!=1)
mexErrMsgTxt("MINKMEX: Second input K must be a scalar.");
if (mxGetClassID(prhs[1]) != mxDOUBLE_CLASS)
mexErrMsgTxt("MINKMEX: Second input K must be a double.");
k = (int)(*mxGetPr(prhs[1]));
if (k<0)
mexErrMsgTxt("MINKMEX: K must be non-negative integer.");
/* Get a data pointer */
list = mxGetPr(prhs[0]);
/* Clip k */
if (k>l) k=l;
/* Clean programming */
pos=NULL;
/* Work for non-empty array */
if (l>0) {
/* Vector of index */
pos = mxMalloc(sizeof(mwSize)*l);
if (pos==NULL)
mexErrMsgTxt("Out of memory.");
/* Initialize the array of position (zero-based index) */
for (i=0; i<l; i++) pos[i]=i;
/* Call the recursive engine */
k--; /* because we work on zero-based */
findFirstK(0, l-1);
k++; /* Restore one-based index */
} /* if (l>0) */
/* Create the Matrix result (first output) */
dims[0] = 1; dims[1] = k;
plhs[0] = mxCreateNumericArray(2, dims, mxDOUBLE_CLASS, mxREAL);
if (plhs[0] == NULL)
mexErrMsgTxt("Out of memory.");
data = mxGetPr(plhs[0]);
for (i=0; i<k; i++) data[i]=list[pos[i]];
/* Create the Matrix position (second output) */
if (nlhs>=2)
{
dims[0] = 1; dims[1] = k;
plhs[1] = mxCreateNumericArray(2, dims, mxDOUBLE_CLASS, mxREAL);
if (plhs[1] == NULL)
mexErrMsgTxt("Out of memory.");
data = mxGetPr(plhs[1]);
for (i=0; i<k; i++) data[i]=(double)(pos[i]+1); /* one-based */
}
/* Free the array of position */
if (pos) mxFree(pos);
pos = NULL; /* clean programming */
return;
} /* Gateway of minkmex.c */
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
function [res loc] = mink(list, k)
% function res = mink(list, k)
%
% Return in RES the K smallest elements of LIST
% RES is sorted in ascending order
% [res loc] = mink(...)
% Location of the smallest: RES=LIST(LOC)
%
% Author Bruno Luong <bruno...@yahoo.com>
% Last update: 06/April/2009
clist=class(list);
% Mex file requires double
if ~strcmpi(clist,'double')
list=double(list);
end
k=double(k);
[res loc] = minkmex(list(:),k);
[res is] = sort(res);
loc = loc(is);
% Cast to original class
if ~strcmpi(clist,'double')
res=feval(clist,res);
end
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
Test on command line
clear
k=10;
n=1e6;
ntest=50;
tmink=zeros(1,ntest);
tsort=zeros(1,ntest);
for i=1:ntest
list=rand(1,n);
tic
m=mink(list,k);
tmink(i)=toc;
tic
s=sort(list);
s=s(1:k);
tsort(i)=toc;
if ~isequal(m,s)
keyboard;
end
end
disp('mink')
disp(median(tmink))
disp('sort:')
disp(median(tsort))
Matt Fig
[res,loc] = mink(A,N)
for vector A of length N, the output should be the same as:
[sres,sloc] = sort(A).
But this is not the case for, ex:.
A = randperm(20) - randperm(20);
....
....
[all(loc==sloc) all(res == sres)]
ans =
0 1
Again, it is not a necessity, but for consistency it might be nice!
Bruno Luong
Thanks. You got it, I will take into account your remark. I'll have to process this case apart. Because the partial quicksort above is not a "stable" ordering algorithm, and I can't see right now how can modify it to become stable one.
Best,
Bruno
Bruno Luong
Take a look at the command MINK and MAXK, both having (almost) linear complexity and return the position as well.
Bruno
sssb...@gmail.com
> "Oluwa KuIse" <wespea...@yahoo.com> wrote in message <gav3p9$som$1...@fred.mathworks.com>... > Hello, > Can anyone pls tell me how I can find the second (or third) largest element in a matrix AND its position. The max function gives the largest element and its position but how do I find the second largest element and its position? if temp is your vector, you can get the second largest element as follows: [c,i] = max(temp(temp~=max(temp)))why would you sort it? this is the whole point of logical addressing in matlab.
[c,i] = max(temp(temp~=max(temp)))
I like your answer. Could you show me how to write like this to fine the third max? Thanks
sss
dpb
After a while it starts to get messy trying to keep straight the nesting
levels... :)
And, at some number it would make sense to just go ahead and get the
order vector. I've not tried any timings to see how many values and
what size vectors is the breakpoint...
--
tili...@gmail.com
> Hello,
> Can anyone pls tell me how I can find the second (or third) largest element in a matrix AND its position. The max function gives the largest element and its position but how do I find the second largest element and its position?
Nasser M. Abbasi
>and want to make a function to display the first
>and second largest value, how could i write it?
>
--Nasser
dpb
> On 5/4/2013 6:14 PM, tili...@gmail.com wrote:
>
>> IF for example, i have a matrix [3,1,1,0,2,0]
>
> this is not a matrix. it is a list of a vector.
>> and want to make a function to display the first
>> and second largest value, how could i write it?
>>
>
> may be use sort()?
doc find % use optional arguments...
--
Nasser M. Abbasi
> On 5/4/2013 7:54 PM, Nasser M. Abbasi wrote:
>> On 5/4/2013 6:14 PM, tili...@gmail.com wrote:
>>
>>> IF for example, i have a matrix [3,1,1,0,2,0]
>>
>> this is not a matrix. it is a list of a vector.
>
> A vector is a 1D matrix...
>
https://en.wikipedia.org/wiki/Matrix_%28mathematics%29
"In mathematics, a matrix (plural matrices) is a rectangular
array of numbers, symbols, or expressions, arranged in rows and columns."
While a vector is a list. For example
http://en.wikipedia.org/wiki/Euclidean_vector
"The endpoint of a vector can be identified with an
ordered list of n real numbers (n-tuple). These numbers
are the coordinates of the endpoint of the vector,
with respect to a given Cartesian coordinate system"
ps.
If one really wants to use one name for all of these
objects, then may be tensor is the correct name to use
and not "matrix".
A tensor of rank (or order) 1 can be represented as
vector, while a tensor of rank 2 can be represented as
a matrix. (these are the correct vector and matrix definitions
as per above, not the matlab ones).
A tensor of rank 0 is a scalar and so on... (ps. a matrix
is not always necessarily a tensor of rank 2 but a tensor
of rank 2 can always be written as a matrix). i.e. tensor
is a more general object.
--Nasser
Bruno Luong
> > On 5/4/2013 6:14 PM, tili...@gmail.com wrote:
> >
> >> IF for example, i have a matrix [3,1,1,0,2,0]
> >
> > this is not a matrix. it is a list of a vector.
Wikipedia definition never restrict the size large or equal to 2.
Matrix backslash operator \ can be applied on matrices, vectors or scalars because they are all matrices.
Thinking a matrix must have a size larger than 1 is human, not mathematics.
Bruno
Nasser M. Abbasi
is rectangular array. That is what the teacher told us
in class. I also looked up in many other places.
http://www.thefreedictionary.com/matrix
"a. Mathematics A rectangular array of numeric or algebraic
quantities subject to mathematical operations.
b. Something resembling such an array, as in the regular
formation of elements into columns and rows."
http://oxforddictionaries.com/us/definition/american_english/matrix
"3 Mathematics a rectangular array of quantities or
expressions in rows and columns that is treated as a single
entity and manipulated according to particular rules."
http://chortle.ccsu.edu/vectorlessons/vmch13/vmch13_2.html
"A matrix is a collection of numbers arranged into a
fixed number of rows and columns"
http://science.yourdictionary.com/matrix
"Mathematics A rectangular array of numeric or algebraic
quantities subject to mathematical operations."
http://www.macmillandictionary.com/us/dictionary/american/matrix
"math an arrangement of numbers or symbols in a pattern from top to
bottom and from left to right, used for solving problems in mathematics"
http://mathworld.wolfram.com/Matrix.html
"In his 1851 paper, Sylvester wrote, "For this purpose
we must commence, not with a square, but with an oblong
arrangement of terms consisting, suppose, of m lines and
n columns. This will not in itself represent a determinant,
but is, as it were, a Matrix out of which we may form various
systems of determinants by fixing upon a number p, and
selecting at will p lines and p columns, the squares corresponding
of pth order."
https://en.wikipedia.org/wiki/Matrix_%28mathematics%29
"In mathematics, a matrix (plural matrices) is a rectangular
array of numbers, symbols, or expressions, arranged in rows and columns."
Bruno Luong
>
> I can only go by Mathematics. In Mathematics, a matrix
> is rectangular array. That is what the teacher told us
> in class. I also looked up in many other places.
>
> http://www.thefreedictionary.com/matrix
>
> "a. Mathematics A rectangular array of numeric or algebraic
> quantities subject to mathematical operations.
> b. Something resembling such an array, as in the regular
> formation of elements into columns and rows."
>
>
[ 1 2 3 ] or [1; 2; 3] are a rectangular arrays of numerical numbers, therefore they are matrices. It seems totally coherent with this list of definitions to me.
Bruno
dpb
...
> The correct definition of Matrix is
>
> https://en.wikipedia.org/wiki/Matrix_%28mathematics%29
>
> "In mathematics, a matrix (plural matrices) is a rectangular
> array of numbers, symbols, or expressions, arranged in rows and columns."
>
A 1D matrix is a rectangle of 1xN (or Nx1) perfectly in consonance w/ a
rectangular array of numbers, ...
--
Nasser M. Abbasi
how one writes down a vector and a matrix which happens to have
one row in it.
But from Mathematics and also physics point of view, there is
a big difference between a vector and a matrix, which happens to
have one row (or one column) in it.
These are 2 different objects. They mean different things.
Even when I write my HW, I always write {v} to mean a vector,
but write [v] when v happens to be a matrix, even though
[v] can have one row, but logically it is a matrix, not
a vector.
Actually, number of other language are not as forgiving as
Matlab. Maple makes a difference between a matrix and
a vector
http://www.maplesoft.com/support/help/Maple/view.aspx?path=Vector
-------------------------------
A:=Matrix(1,3,[[5,6,7]]);
type(A,'Matrix');
true
type(A,'Vector');
false
---------------------------------
Also in Mathematica, a:={1,2,3}; is a list, i.e a vector, but NOT
a matrix. To make it a matrix, it has to be written as a:={{1,2,3}}, and
not it is a matrix.
So, one has to be careful between talking about types of mathematical
objects, and between how they are represented in a computer language.
Some languages are more strongly typed, and will make a difference
between a vector and a matrix of one row. But logically they
are not the same.
--Nasser
Nasser M. Abbasi
>
> -------------------------------
> A:=Matrix(1,3,[[5,6,7]]);
> type(A,'Matrix');
> true
> type(A,'Vector');
> false
> ---------------------------------
>
as in a pic is worth a 1000 words :)
http://12000.org/tmp/050513/mat.png
One can see that both 'look' the same, but one is a
matrix, while the other is a vector.
--Nasser
TideMan
These other guys are like Humpty Dumpty in "Through the Looking Glass" who said:
"When I use a word, it means exactly what I choose it to mean, neither more nor less".
Steven_Lord
"Nasser M. Abbasi" <n...@12000.org> wrote in message
news:km4m6n$nlo$1...@speranza.aioe.org...
>> On 5/4/2013 7:54 PM, Nasser M. Abbasi wrote:
>>> On 5/4/2013 6:14 PM, tili...@gmail.com wrote:
>>>
>>>> IF for example, i have a matrix [3,1,1,0,2,0]
>>>
>>> this is not a matrix. it is a list of a vector.
>>
>> A vector is a 1D matrix...
>>
>
> The correct definition of Matrix is
>
> https://en.wikipedia.org/wiki/Matrix_%28mathematics%29
http://www.mathworks.com/help/matlab/ref/isscalar.html
http://www.mathworks.com/help/matlab/ref/isvector.html
http://www.mathworks.com/help/matlab/ref/ismatrix.html
> "In mathematics, a matrix (plural matrices) is a rectangular
> array of numbers, symbols, or expressions, arranged in rows and columns."
A scalar is something whose SIZE is [1 1]. A scalar is also a vector, a
matrix, and an array.
A vector is something whose SIZE is [1 n] or [n 1] for nonnegative n. A
vector is also a matrix and also an array. A vector is NOT also a scalar
unless n is equal to 1.
A matrix is something whose SIZE is [m n] for nonnegative m and n. A matrix
is also an array. A matrix is NOT a vector unless one or both of m and n are
1, and is NOT a scalar unless they BOTH are 1.
--
Steve Lord
sl...@mathworks.com
To contact Technical Support use the Contact Us link on
http://www.mathworks.com