Discover MakerZone

MATLAB and Simulink resources for Arduino, LEGO, and Raspberry Pi

Learn more

Discover what MATLAB® can do for your career.

Opportunities for recent engineering grads.

Apply Today

Thread Subject:
Fastest way to match the closest value in a vector.

Subject: Fastest way to match the closest value in a vector.

From: Keith Barth

Date: 14 Apr, 2012 01:37:07

Message: 1 of 6

Suppose I have a vector x in ascending order that is evenly spaced. (e.g., x=linspace(0,90,N) )

Suppose x(i)=<y<x(i+1). What is the fastest way to find i?

Thanks so much in advance!!!!! :)

Subject: Fastest way to match the closest value in a vector.

From: Roger Stafford

Date: 14 Apr, 2012 04:08:20

Message: 2 of 6

"Keith Barth" <denrick888@gmail.com> wrote in message <jmakc3$61e$1@newscl01ah.mathworks.com>...
> Suppose I have a vector x in ascending order that is evenly spaced. (e.g., x=linspace(0,90,N) )
>
> Suppose x(i)=<y<x(i+1). What is the fastest way to find i?
- - - - - - - - -
  If x is evenly-spaced and ascending, then the formula

 i = floor((y-x(1))/(x(n)-x(1))*(n-1)+1);

will usually give you the correct 'i' for x(i) <= y < x(i+1) in just one step. However, if it misses due to round off error, you can easily correct it in only one more step by adding or subtracting 1 to i as needed.

Roger Stafford

Subject: Fastest way to match the closest value in a vector.

From: Doug Schwarz

Date: 14 Apr, 2012 05:22:18

Message: 3 of 6

In article <jmakc3$61e$1@newscl01ah.mathworks.com>,
 "Keith Barth" <denrick888@gmail.com> wrote:

> Suppose I have a vector x in ascending order that is evenly spaced. (e.g.,
> x=linspace(0,90,N) )
>
> Suppose x(i)=<y<x(i+1). What is the fastest way to find i?
>
> Thanks so much in advance!!!!! :)

Try Roger's method, but if there are many such y values (i.e., y is a
vector) then this works rather well:

[~,i] = histc(y,x);

It also doesn't require x to be evenly spaced.

--
Doug Schwarz
dmschwarz&ieee,org
Make obvious changes to get real email address.

Subject: Fastest way to match the closest value in a vector.

From: Roger Stafford

Date: 14 Apr, 2012 06:13:10

Message: 4 of 6

Doug Schwarz <see@sig.for.address.edu> wrote in message <see-A63A9D.01221814042012@news.eternal-september.org>...
> Try Roger's method, but if there are many such y values (i.e., y is a
> vector) then this works rather well:
>
> [~,i] = histc(y,x);
>
> It also doesn't require x to be evenly spaced.
- - - - - - - - - - -
  Hi Doug. The reason I suggested that method rather than using 'histc' was to avoid having to wait on either the binary search that 'histc' may perform for each element of a vector or some kind of sort operation. (I don't actually know what algorithm 'histc' uses.) Being able to locate the right index in only one step, or rarely in two steps, gives a linear order complexity which I am certain 'histc' is incapable of and is a possibility hard to turn down.

  However, if the evenly-spaced property is discarded, then 'histc' almost certainly becomes the right way to do the problem.

Roger Stafford

Subject: Fastest way to match the closest value in a vector.

From: Doug Schwarz

Date: 14 Apr, 2012 12:40:45

Message: 5 of 6

In article <jmb4hm$7nn$1@newscl01ah.mathworks.com>,
 "Roger Stafford" <ellieandrogerxyzzy@mindspring.com.invalid> wrote:

> Doug Schwarz <see@sig.for.address.edu> wrote in message
> <see-A63A9D.01221814042012@news.eternal-september.org>...
> > Try Roger's method, but if there are many such y values (i.e., y is a
> > vector) then this works rather well:
> >
> > [~,i] = histc(y,x);
> >
> > It also doesn't require x to be evenly spaced.
> - - - - - - - - - - -
> Hi Doug. The reason I suggested that method rather than using 'histc' was
> to avoid having to wait on either the binary search that 'histc' may
> perform for each element of a vector or some kind of sort operation. (I
> don't actually know what algorithm 'histc' uses.) Being able to locate the
> right index in only one step, or rarely in two steps, gives a linear order
> complexity which I am certain 'histc' is incapable of and is a possibility
> hard to turn down.
>
> However, if the evenly-spaced property is discarded, then 'histc' almost
> certainly becomes the right way to do the problem.
>
> Roger Stafford

Hi Roger,

I agree completely which is why I suggested the OP try both methods. He
should time them in his program to see how they perform. Even with the
search, histc might be faster because it's implemented at a low level.
I assume it does not do a sort because it requires that x be
monotonically non-decreasing, though it does detect if that's not the
case. Anyway, there are enough uncertainties that, if time is critical
(and when is it not?), the competing methods should be timed.

Also, as you know, many times people follow up the original question
with something like, "Okay, thanks, what if the vector isn't evenly
spaced?" :-)

Regards,
Doug

--
Doug Schwarz
dmschwarz&ieee,org
Make obvious changes to get real email address.

Subject: Fastest way to match the closest value in a vector.

From: Roger Stafford

Date: 14 Apr, 2012 17:25:18

Message: 6 of 6

"Keith Barth" <denrick888@gmail.com> wrote in message <jmakc3$61e$1@newscl01ah.mathworks.com>...
> Suppose I have a vector x in ascending order that is evenly spaced. (e.g., x=linspace(0,90,N) )
>
> Suppose x(i)=<y<x(i+1). What is the fastest way to find i?
>
> Thanks so much in advance!!!!! :)
- - - - - - - - - -
  Here is the form I would recommend for use with y as a vector, assuming that x and y are either both row vectors or both column vectors (and of course assuming that x is evenly-spaced and ascending):

 n = length(x);
 ix = round((y-x(1))*((n-1)/(x(n)-x(1)))+1);
 ix = ix - (y<x(ix));

Note that with this change from 'floor' to 'round' it is only necessary to correct 'ix' downwards.

  Keith, if you want to make the comparison with 'histc' that Doug is recommending, I would advise using a large value for n (along with y being a long vector.) With the lengths of x and y being n and m respectively, I would surmise that 'histc' will be an order(m*log(n)) algorithm, whereas the above procedure is clearly order(m). Therefore large values of n would presumably make this difference evident.

Roger Stafford

Tags for this Thread

What are tags?

A tag is like a keyword or category label associated with each thread. Tags make it easier for you to find threads of interest.

Anyone can tag a thread. Tags are public and visible to everyone.

Contact us