3

所以假设我有T，T = 1200。我还有A,A是一个包含 1000 个条目的数组，这些是数字条目，范围从1000-2000但不包括1200.

找到最近邻居（最接近的值）的最快方法是什么，假设我们 ceil 它，所以它会匹配1201，而不是1199in A。

注意：这将在ENTER_FRAME.

另请注意： A是静态的。

4

6 回答 6

3

Vector.<int>使用而不是Array做一个简单的for循环也非常快：

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];
    }
}

使用任何数组方法都将比迭代更昂贵Vector.<int>- 它针对这种操作进行了优化。

于 2012-04-04T16:34:47.793 回答
2

如果您希望在每个ENTER_FRAME事件上运行它，您可能会从一些额外的优化中受益。

如果您在将条目写入数组时跟踪它们，则不必对它们进行排序。

例如，您有一个数组，其中T的索引，它会有一个对象，该对象包含一个数组，该数组的所有索引都包含A该值。您还可以将最接近的值的索引作为该对象的一部分，因此当您每帧检索它时，您只需要访问该值，而不是搜索。

当然，这只有在你读的比写的多时才有帮助，因为重新创建对象非常昂贵，所以它真的取决于使用情况。

您可能还想查看链表，对于某些操作，它们要快得多（虽然排序较慢）

于 2012-04-04T16:06:12.897 回答
1

由于您的数组已排序，因此您可以采用简单的二进制搜索（例如在此答案中解释）以找到“枢轴”，其中左细分和右细分在递归步骤中括号您正在“搜索”的值。

于 2012-04-04T16:20:35.613 回答
1

您必须读取每个值，因此复杂性将是线性的。这很像在数组中找到最小的 int。

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];
于 2012-04-04T15:47:23.963 回答
0

只是我的一个想法......对A进行排序（因为它是静态的，你可以在开始之前对其进行一次排序），然后猜测开始猜测的索引（比如A的长度为100，你想要1200、100* (200/1000) = 20) 所以从那个猜测开始猜测，然后如果 A[guess] 高于 1200，则检查 A[guess-1] 处的值。如果它仍然更高，请继续向下，直到找到一个更高的和一个更低的。一旦你发现确定什么更接近。如果您最初的猜测太低，请继续向上。

这不会很好，也可能不是最好的性能，但它比检查每个值要好得多，并且如果 A 在 1000 和 2000 之间均匀分布，它将工作得很好。

祝你好运！

于 2012-04-04T16:21:55.150 回答
0 
public function nearestNumber(value:Number,list:Array):Number{
    var currentNumber:Number = list[0];
    for (var i:int = 0; i < list.length; i++) {
        if (Math.abs(value - list[i]) < Math.abs(value - currentNumber)){
            currentNumber = list[i];
        }
    }
    return currentNumber;
}
于 2015-02-11T16:32:41.923 回答