Search All of the Math Forum:
Views expressed in these public forums are not endorsed by
NCTM or The Math Forum.



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 forloop 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:K11)+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:end1)+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



