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