Drexel dragonThe Math ForumDonate to the Math Forum



Search All of the Math Forum:

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


Math Forum » Discussions » Software » comp.soft-sys.matlab

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

Advanced Search

Back to Topic List Back to Topic List Jump to Tree View Jump to Tree View   Messages: [ Previous | Next ]
Yair Altman

Posts: 1,352
Registered: 3/19/07
Re: fast way to get second output of min
Posted: Mar 7, 2014 5:13 AM
  Click to see the message monospaced in plain text Plain Text   Click to reply to this topic Reply

"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




Point your RSS reader here for a feed of the latest messages in this topic.

[Privacy Policy] [Terms of Use]

© Drexel University 1994-2014. All Rights Reserved.
The Math Forum is a research and educational enterprise of the Drexel University School of Education.