Path: news.mathworks.com!not-for-mail
From: "Christian " <proechri@umich.edu>
Newsgroups: comp.soft-sys.matlab
Subject: Re: fast way to get second output of min
Date: Fri, 7 Mar 2014 15:07:08 +0000 (UTC)
Organization: The MathWorks, Inc.
Lines: 41
Message-ID: <lfcnas$gjq$1@newscl01ah.mathworks.com>
References: <lfat6s$te$1@newscl01ah.mathworks.com> <lfbtln$df6$1@newscl01ah.mathworks.com> <lfc63j$2mf$1@newscl01ah.mathworks.com>
Reply-To: "Christian " <proechri@umich.edu>
NNTP-Posting-Host: rubyext-04-ls.mathworks.com
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 8bit
X-Trace: newscl01ah.mathworks.com 1394204828 17018 172.20.102.180 (7 Mar 2014 15:07:08 GMT)
X-Complaints-To: news@mathworks.com
NNTP-Posting-Date: Fri, 7 Mar 2014 15:07:08 +0000 (UTC)
X-Newsreader: MATLAB Central Newsreader 3858030
Xref: news.mathworks.com comp.soft-sys.matlab:810438

That's wonderful!
My x vector already is sorted and strictly monotonically increasing so I could skip line 1 and 3. The normal matlab file now requires 5.5 seconds compared to 43 before, and the mex file is actually down to 3.5 seconds. There are some minor other operations in the code that take up the chunk of the calculation time. So I might post another question on that topic.
For histc I know that it's not available on gpu. But I think I've already asked for a manual workaround for histc, so I might want to revive that thread.   

"Yair Altman" wrote in message <lfc63j$2mf$1@newscl01ah.mathworks.com>...
> "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 
>