Path: news.mathworks.com!newsfeed-00.mathworks.com!NNTP.WPI.EDU!elk.ncren.net!newsflash.concordia.ca!canopus.cc.umanitoba.ca!not-for-mail
From: roberson@ibd.nrc-cnrc.gc.ca (Walter Roberson)
Newsgroups: comp.soft-sys.matlab
Subject: Re: The N largest values of an M x 1 matrix
Date: Thu, 3 Jan 2008 19:49:54 +0000 (UTC)
Organization: National Research Council Canada - Conseil national de rechereches Canada
Lines: 20
Message-ID: <flje92$ogi$1@canopus.cc.umanitoba.ca>
References: <57537254-3f7e-43e4-8fc4-75d8de63b3d6@s8g2000prg.googlegroups.com> <flis2c$4nu$1@fred.mathworks.com> <7222b5d8-b1b3-425c-be43-ac349257c5e7@e23g2000prf.googlegroups.com>
NNTP-Posting-Host: origin.ibd.nrc.ca
X-Trace: canopus.cc.umanitoba.ca 1199389794 25106 192.70.172.160 (3 Jan 2008 19:49:54 GMT)
X-Complaints-To: abuse@cc.umanitoba.ca
NNTP-Posting-Date: Thu, 3 Jan 2008 19:49:54 +0000 (UTC)
Originator: roberson@ibd.nrc-cnrc.gc.ca (Walter Roberson)
Xref: news.mathworks.com comp.soft-sys.matlab:444244


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