Path: news.mathworks.com!not-for-mail
From: "Yair Altman" <altmanyDEL@gmailDEL.comDEL>
Newsgroups: comp.soft-sys.matlab
Subject: Re: fast way to get second output of min
Date: Fri, 7 Mar 2014 10:13:07 +0000 (UTC)
Organization: TACT Computer Systems Ltd
Lines: 36
Message-ID: <lfc63j$2mf$1@newscl01ah.mathworks.com>
References: <lfat6s$te$1@newscl01ah.mathworks.com> <lfbtln$df6$1@newscl01ah.mathworks.com>
Reply-To: "Yair Altman" <altmanyDEL@gmailDEL.comDEL>
NNTP-Posting-Host: rubyext-06-ls.mathworks.com
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 8bit
X-Trace: newscl01ah.mathworks.com 1394187187 2767 172.20.102.182 (7 Mar 2014 10:13:07 GMT)
X-Complaints-To: news@mathworks.com
NNTP-Posting-Date: Fri, 7 Mar 2014 10:13:07 +0000 (UTC)
X-Newsreader: MATLAB Central Newsreader 642467
Xref: news.mathworks.com comp.soft-sys.matlab:810420

"Roger Stafford" wrote in message <lfbtln$df6$1@newscl01ah.mathworks.com>...
> "Christian " <proechri@umich.edu> wrote in message <lfat6s$te$1@newscl01ah.mathworks.com>...
> > I'm looking for a faster way for the following code:
> > 
> >   for k1=1:K1
> >      for k21=1:K2
> >         for k22=1:K2
> >            [~, xind(k1,k21,k22)] = min(abs(yp(k1,k21,k22)-x)); %nearest neighbor of yp in x 
> >         end
> >       end
> >    end
> > 
> > where x is a vector of dimension 1:K1.
> - - - - - - - - -
>   It seems to me inefficient to have the 'min' function repeatedly scan over all of the x elements inside the innermost for-loop for every element in yp.  If you first sort x and then use 'histc' appropriately to find the nearest value of x, it ought to go much faster.  Seeking a nearest element in a sorted list of n elements can be done in O(log(n)) as opposed to O(n), which I believe is the way 'histc' works.
> 
>   Try the following.  The p vector below serves to transform the indices relative to the sorted x2 back to those relative to the original x.  I assume here that x is a column vector.  If it is a row vector, make the obvious change in the second argument in 'histc'.  I also assume that all the elements in x and yp are finite.
> 
>  [x2,p] = sort(x);
>  [~,xind] = histc(yp,[-inf;(x2(1:K1-1)+x2(2:K1))/2;inf]); % Use x2 midpoints
>  xind = reshape(p(xind),size(yp));
> 
> Roger Stafford


Minor correction to Roger's excellent answer:

   [x2,p] = sort(x);
   [~,xind] = histc(yp,[-inf;(x2(1:end-1)+x2(2:end))/2;inf]); % Use x2 midpoints
   xind = reshape(p(xind),size(yp));

i.e., use end (not K1), for the x2 midpoints in the call to histc

Yair Altman 
http://UndocumentedMatlab.com