Search All of the Math Forum:

Views expressed in these public forums are not endorsed by NCTM or The Math Forum.

Notice: We are no longer accepting new posts, but the forums will continue to be readable.

Topic: fast way to get second output of min
Replies: 5   Last Post: Mar 7, 2014 10:07 AM

 Messages: [ Previous | Next ]
 Yair Altman Posts: 1,407 Registered: 3/19/07
Re: fast way to get second output of min
Posted: Mar 7, 2014 5:13 AM

"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

Date Subject Author
3/6/14 Christian
3/6/14 dpb
3/6/14 Christian
3/7/14 Roger Stafford
3/7/14 Yair Altman
3/7/14 Christian