AS3 math: nearest neighbor in an array
So let's say I have T
, T = 1200
. I also have A
, A
- an array containing 1000 entries and these are numeric entries that range from 1000-2000
but do not contain an entry for 1200
.
What's the fastest way to find the nearest neighbor (closest value), let's say we put it, so it will match 1201
, not 1199
in A
.
Note: this will run on ENTER_FRAME
.
Also note: A
is static.
source to share
If you want to run this on every event ENTER_FRAME
, you will probably benefit from some additional optimization.
If you are keeping track of records as they are written to an array, you don't need to sort them.
For example, you will have an array where T
is the index, and it will have an array object with all the array indices A
that hold that value. you can also put the index of the closest value as part of that object, so when you retrieve this every frame, you only need to access that value, not search.
Of course, it would help if you read a lot more than you write, because recreating an object is quite expensive, so it really depends on the usage.
You can also view linked lists, for certain operations they are quite fast (slower when sorting)
source to share
It's also very quick to use Vector.<int>
instead of Array
and make a simple for loop:
var vector:Vector.<int> = new <int>[ 0,1,2, /*....*/ 2000];
function seekNextLower( searchNumber:int ) : int {
for (var i:int = vector.length-1; i >= 0; i--) {
if (vector[i] <= searchNumber) return vector[i];
}
}
function seekNextHigher( searchNumber:int ) : int {
for (var i:int = 0; i < vector.length; i++) {
if (vector[i] >= searchNumber) return vector[i];
}
}
Using any array methods will be more expensive than iterating with Vector.<int>
- it has been optimized for this kind of operation.
source to share
You have to read each value, so the complexity will be linear. This is very similar to looking for the smallest int in an array.
var closestIndex:uint;
var closestDistance:uint = uint.MAX_VALUE;
var currentDistance:uint;
var arrayLength:uint = A.length;
for (var index:int = 0; index<arrayLength; index++)
{
currentDistance = Math.abs(T - A[index]);
if (currentDistance < closestDistance ||
(currentDistance == closestDistance && A[index] > T)) //between two values with the same distance, prefers the one larger than T
{
closestDistance = currentDistance;
closestIndex = index;
}
}
return T[closestIndex];
source to share
Since your array is sorted, you can adapt a simple binary search (such as explained in this answer ) to find "pivot" where the left subdivision and right-subdivision in the recursive step parenthesis are the value you are looking for.
source to share
Just a thought I had ... Sort A (starting from its static you can just sort it once before you start) and then think about which index to start guessing (say A is length 100, you want 1200, 100 * (200/1000) = 20), so guess from this guess and then if A [guess] is above 1200, check the value against A [guess-1]. If it's even higher, keep going down until you find the one higher and the other lower. Once you find that determine which is closer. if your initial guess was too low, keep going up.
This will not be great and may not be the best performance, but it would be much better than checking each value, and it will work well if A is evenly distributed between 1000 and 2000.
Good luck!
source to share