Thread Subject: The N largest values of an M x 1 matrix

I would like to find the indexes of the N largest elements of an M x
1 matrix. right now I do something lik the following, but it doesn't
scale well.

N=10;M=100;a=rand(1,M);[val,ip]=sort(a);idx=ip(end-N:end);a(idx)

Does matlab have a specialized function for this?

                           Palle

Palle Uldenborg <palle.uldenborg@gmail.com> wrote in message
<57537254-3f7e-43e4-8fc4-75d8de63b3d6@s8g2000prg.googlegroups.com>...
> I would like to find the indexes of the N largest elements
of an M x
> 1 matrix. right now I do something lik the following, but
it doesn't
> scale well.
>
>
N=10;M=100;a=rand(1,M);[val,ip]=sort(a);idx=ip(end-N:end);a(idx)
>
> Does matlab have a specialized function for this?
>
> Palle


What do you mean by "it doesn't scale well"?

Other approaches:

  val = sort(-a) ; % or sort(a,'descend')
  val(1:N) ;

or

  val = unique(-a) ;
  val(1:N)

hth
Jos

On Jan 3, 3:39 pm, "Jos " <DEL...@jasenDEL.nl> wrote:
> Palle Uldenborg <palle.uldenb...@gmail.com> wrote in message
> <57537254-3f7e-43e4-8fc4-75d8de63b...@s8g2000prg.googlegroups.com>...
> > I would like to find the indexes of the N largest elements of an M x
> > 1 matrix. right now I do something lik the following, but
> > it doesn't scale well.
> > N=10;M=100;a=rand(1,M);[val,ip]=sort(a);idx=ip(end-N:end);a(idx)
> > Does matlab have a specialized function for this?
> What do you mean by "it doesn't scale well"?

Thank you for your answer. Sorry if I was unclear.

I meant that for for a fixed value of N the CPU cost does not scale
linearly with M.

I am interested in situations such as N=5 and M=100000, so I think
that I could gain from a matlab function that did some kind of partial
sorting.

                       Niels

Palle Uldenborg <palle.uldenborg@gmail.com> wrote in
message <7222b5d8-b1b3-425c-be43-
ac349257c5e7@e23g2000prf.googlegroups.com>...
> On Jan 3, 3:39 pm, "Jos " <DEL...@jasenDEL.nl> wrote:
> > Palle Uldenborg <palle.uldenb...@gmail.com> wrote in
message
> > <57537254-3f7e-43e4-8fc4-
75d8de63b...@s8g2000prg.googlegroups.com>...
> > > I would like to find the indexes of the N largest
elements of an M x
> > > 1 matrix. right now I do something lik the following,
but
> > > it doesn't scale well.
> > > N=10;M=100;a=rand(1,M);[val,ip]=sort(a);idx=ip(end-
N:end);a(idx)
> > > Does matlab have a specialized function for this?
> > What do you mean by "it doesn't scale well"?
>
> Thank you for your answer. Sorry if I was unclear.
>
> I meant that for for a fixed value of N the CPU cost does
not scale
> linearly with M.
>
> I am interested in situations such as N=5 and M=100000,
so I think
> that I could gain from a matlab function that did some
kind of partial
> sorting.
>
> Niels
>
>
>
>
>


For N << M, this may be faster then using sort

M = 1000000 ;
N = 5 ;
A = rand(M,1) ;

val(1:N) = NaN ;
for j=1:N,
   [val(j),ind] = max(A) ;
   A(ind) = -Inf ;
end


hth
Jos

In article <7222b5d8-b1b3-425c-be43-ac349257c5e7@e23g2000prf.googlegroups.com>,
Palle Uldenborg <palle.uldenborg@gmail.com> wrote:
>> Palle Uldenborg <palle.uldenb...@gmail.com> wrote in message
>> <57537254-3f7e-43e4-8fc4-75d8de63b...@s8g2000prg.googlegroups.com>...
>> > I would like to find the indexes of the N largest elements of an M x
>> > 1 matrix. right now I do something lik the following, but
>> > it doesn't scale well.

>I meant that for for a fixed value of N the CPU cost does not scale
>linearly with M.

In that case, use max() to get the value and index of the first
maximum, then replace that index position in the vector with NaN.
Use max() to get the value and index on that vector to get the
value and index of the second maximum, replace it with NaN,
repeat until you have as many as you need. Each pass will be
linear in M, so the total cost will be N*M, which beats
M*log(M) that you would have for a sort().
--
   "History is a pile of debris" -- Laurie Anderson

Palle Uldenborg <palle.uldenborg@gmail.com> wrote in message
<7222b5d8-b1b3-425c-be43-
ac349257c5e7@e23g2000prf.googlegroups.com>...
> > Palle Uldenborg <palle.uldenb...@gmail.com> wrote in message
>......
> > > I would like to find the indexes of the N largest elements of an M x
> > > 1 matrix.......
> I am interested in situations such as N=5 and M=100000, so I think
> that I could gain from a matlab function that did some kind of partial
> sorting.
> Niels
---------
  For values as high as M = 100000 and as small as N = 5, it is true that a
sort operation may be relatively inefficient, since it is an order M*log(M)
algorithm. I have not heard of a matlab "partial sort" function, so you would
probably have to replace the sort with some kind of carefully thought out for-
loop type algorithm.

  One strategy might be to construct an order M*N algorithm along the
following lines using the max function. Let a be the M x 1 vector. Then do:

 q = M:-1:1; % Start with all of vector a in current list
 p = zeros(N,1); % Allocate indices storage
 for r = N:-1:1
  [ignore,s] = max(a(q)); % Find the current maximum
  p(r) = q(s); % Store its index
  q(s) = []; % Drop it from the current list
 end

The N-element vector a(p) will have the N largest elements of a and p will
have their indices.

  It is clear, however, that the number N would not have to be very large
before this method would be far more inefficient than doing a straight sort.

  [Note: Between Jos and Roberson you probably have the essential equivalent
of the above, but I'll include this anyhow.]

Roger Stafford

What about if there are 5 or more values that are equal and
are the max? Are you looking for the top five "unique"
values or simply the top five values (which could all be the
same)?