1

この検索方法を最適化する方法はありますか?

for (var i=0;i<dots.length;i++) {
        var blist = [];
        for (var n=0;n<dots.length;n++) {
            if (dots[n][1]>(dots[i][1]-90) 
            && dots[n][1]<(dots[i][1]+90) 
            && dots[n][2]>(dots[i][2]-90) 
            && dots[n][2]<(dots[i][2]+90)) {
                if (!(n === i)) blist.push(n);
            }
        }

dots[x][1]は x 座標、dots[x][2]は y 座標です。

1000 個のドットがあり、各ドットを囲むドットを見つける必要があるため、結果は

if (dots[n][1]>(dots[i][1]-90) 
&& dots[n][1]<(dots[i][1]+90) 
&& dots[n][2]>(dots[i][2]-90) 
&& dots[n][2]<(dots[i][2]+90))

1秒間に100万回実行されているので、これを最適化する方法はありますか?

4

3 に答える 3

1

おそらく、このようなドットのデータ構造を使用してみてください

var Dot = function(){
 var x = 0;
 var y = 0;
 var Up;
 var Right;
 var Left;
 var Down;

 function init(xVal,yVal)
 {
  x = xVal;
  y = yVal;
 }

 function GetUp()
 {
  return Up;
 }

 function SetUp(UpDot)
 {
  Up = UpDot;
 }

 return 
 {
  init: init,
  GetUp: GetUp,
  SetUp: SetUp
 };
};

そして、このように使用します

var Dots = [];
var firstDot = new Dot();
Dots.push(firstDot);
var secondDot = new Dot();
secondDot.init(0,90);
secondDot.SetUp(firstDot);
Dots.push(secondDot);

明らかに、状況に合わせてさらに追加して構成する必要があります。ただし、これにより、ドットを繰り返し処理し、天気をチェックすることで、近くのドットが存在し、時刻がO（n ^ 2）ではなくO（n）になり、900,000回のチェックが節約されました。

于 2012-12-11T00:27:50.550 に答える
0

これが解決策のスケッチです。それは私には明らかではありませんが、TravisJが提案したのと同じ考えかもしれません。これは実際には単なるスケッチであり、実装するにはかなりのコードが必要になります。

スペースを90ユニットx90ユニットのセクションに分割する場合、特定のセクションのドットは、そのセクションのドット、またはそのセクションの8つの隣接するセクションの1つのドットに十分に近づくことができます。これにより、比較する必要のあるペアの数を大幅に減らすことができます。もちろん、コストはアルゴリズムの複雑さです。

  • まず、グリッドセクションを表すデータ構造を作成します。それらの高さと幅はおそらく問題ではない後縁を除いて90に固定されるため、それらはおそらく左上隅だけで表すことができます。長方形の表面を想定すると、それぞれに3つ、5つ、または8つの隣接要素（それぞれコーナー、エッジ、内部セクション）があります。
  • Math.floor(something / 90)ドットをループして、ドットが存在するセクションを決定します。グリッド全体が0から始まる場合、これは、いくつかの操作を使用して、比較的簡単なはずです。
  • セクションごとに、それ自体とその隣接する各セクションで上記のループを実行して、一致するセットを見つけます。私の以前の回答からのループの短縮バージョンを使用できます。
  • さらに最適化するために、チェックするネイバーの数を減らすこともできます。Section3,7がSection3,8と比較する場合、Section3,8がSection3,7とも比較する理由はありません。したがって、ネイバーの特定のサブセットのみをチェックします。たとえば、セクション番号のxおよびyコンポーネントが自分のサブセット以上であるサブセットのみをチェックします。

私は頭の中を除いて、これをテストしていません。動作するはずですが、コードを書こうとはしていません。そして、コードは簡単ではありません。数週間の作業ではないと思いますが、数分でまとめることもできません。

速度が大幅に向上する可能性があると思いますが、それは一致の数、セクションの数に対するドットの数によって異なります。

于 2012-12-12T13:40:29.923 に答える
0

時間を半分に短縮する 1 つの方法は、各ペアを再確認しないことです。

for (var i = 0, len = dots.length; i < len - 1; i++) {
    var blist = [];
    for (var n = i + 1; n < len; n++) {
        if (dots[n][1]>(dots[i][1]-90) 
        && dots[n][1]<(dots[i][1]+90) 
        && dots[n][2]>(dots[i][2]-90) 
        && dots[n][2]<(dots[i][2]+90)) {
            blist.push(i);
            blist.push(n);
        }
    }
}

ループ境界の変更に注意してください。これにより、各ペアを 1 回だけチェックして、チェックをスキップ(n === i)できます。

dot.lengthおそらく大したことではありませんが、タイトなループのために行う価値があります。

それでも、50% 以上の改善になるはずです。それは役立つかもしれませんが、この種の問題に必要となる可能性があるのは桁違いの変化ではありません.

于 2012-12-11T12:15:52.777 に答える