Page 1 of 1

Best way to determine which array item is closest to a value

Posted: 10 Jan 2013 21:27
by Traxus
This is a hard one to explain but lets say I've got an array of values that share no rhythm with one another, a:

Code: Select all

decl a;

a[1]=500;
a[2]=750;
a[3]=1000;
a[4]=2500;
a[5]=4500;

Now I've got another value, b, and I want to know which item within a has the value closest value...

Code: Select all

decl b;
decl c;

b = 550;
c = getclosest(a, b); //should yeild a[1] or 500

b = 874;
c = getclosest(a, b); //should yeild a[2] or 750

What is the best definition for 'getclosest()'? Am I stuck writing a loop with a conditional?

Re: Best way to determine which array item is closest to a v

Posted: 11 Jan 2013 22:34
by kisslorand
Something like this:

Code: Select all

decl index;
decl closeness;
index=0;
closeness=abs(a[0]-b);
for (i=0; i<sizeof(a); i++)
   if (abs(a[i]-b) < closeness)
   {
      closeness=abs(a[i]-b);
      index=i;
   }
return(a[index]);
This algo finds the first element which is closest to "b" if you have two of them (like 250 and 750 compared to 500), if you want to find the latest, you should put "<=" in the if condition.

Re: Best way to determine which array item is closest to a v

Posted: 14 Jan 2013 18:31
by Traxus
Thanks, that's what I had in mind, I was just wondering if there was a less expensive way to do it as I was considering employing this in an onframe script which could get hairy especially with larger arrays.

Re: Best way to determine which array item is closest to a v

Posted: 14 Jan 2013 22:51
by kisslorand
For the infos you gave, that's the only solution. You have a generic solution for a generic problem. If your array is arranged, you can try the bubble algorithm, if not arranged, you should verify closeness upon every array element change... and so on.

Re: Best way to determine which array item is closest to a v

Posted: 15 Jan 2013 04:20
by Macciza
Hi

If you expect the value to sometimes be identical you could add

if(firstof((a/b)==1)!=sizeof(a))return (a[firstof((a/b)==1)]); // if val matches return it . ..

after the initial declarations to return the matching value without iterating . . .

MM

Re: Best way to determine which array item is closest to a v

Posted: 15 Jan 2013 18:53
by Traxus
Thanks again guys

Still bouncing this around my head, I was hoping for some magic inverse of php/c++ array_key_exists() but the now that I think about it, iterating is still the cheapest and only way.

I might have to forego this as running it on frame sounds like more of a headache than it is worth, and at best i would be running it on expression which would be tied to the x value of a knob that could be firing the script pretty rapidly anyway...

Still toying with the idea of inverting the array to something like this:

Code: Select all

decl a;

a[500]=1;
a[750]=1;
a[1000]=1;
a[2500]=1;
a[4500]=1;

And then, as x changes, checking if the array key is set to 1, or if it is null/0... That way when x passes a value that exists I can flag that as the 'closest' value even though it isn't technically the closest (but at worse is the second closest value which may be enough for my application)