3

だから、私が持っているとしましょうT、T = 1200。またA、Aは、数千のエントリを含む配列であり、これらはからの範囲の数値エントリですが1000-2000、のエントリは含まれていません1200。

最も近い隣人（最も近い値）を見つける最も速い方法は何ですか、それを天井にするとしましょう。そうすれば1201、ではなく1199、に一致しますA。

注：これはで実行されENTER_FRAMEます。

また、注意： A静的です。

4

6 に答える 6

3

また、単純なforループのVector.<int>代わりに使用して、実行するのも非常に高速です。Array

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

各値を読み取る必要があるため、複雑さは線形になります。これは、配列内で最小の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 に答える
1

配列はソートされているので、単純な二分探索（この回答で説明されているような）を適応させて、再帰的なステップでの左の細分割と右の細分割が「検索」している値を囲む「ピボット」を見つけることができます。

于 2012-04-04T16:20:35.613 に答える
0

私が持っていた考え...Aを並べ替え（静的なので、開始する前に1回だけ並べ替えることができます）、次に推測を開始するインデックスを推測します（たとえば、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 に答える