アレイ処理ループを最適化する

Question

私はプログラミングのパズルを取り組んでいますが、私はちょっと困惑しています。問題は、2次元計画上のディスクの交差の数を数えることです。 xは常に0で、yは配列のインデックスです。要素の半径は配列要素に格納されます。要素の数が少ない要素ではパフォーマンスは問題ありませんが、10,000,000のパフォーマンスのような多数の要素が悪いです。私は現在、配列を処理するために2つのネストされたforループを使用しています。

誰かが助けてくれれば幸いです。私は私に与えられたデータ構造に縛られており、それらを変更することはできません。私は整数を扱っているので、ディスクが別のディスクと交差していて、中心点が同じy軸上にある場合の計算です。以下は

はコードです：あなたが大規模な数字で、したがって、悪い速度をディスクの各ペアをテストしているので、

int number_of_intersections (int A[], int n) 
{ 
int base = 0; 
int inc = 0; 
int intersect = 0; 
int maxrad = 0; 
int x; 

if (n>1) 
{ 
    for (base=0;base<(n-1);base++) 
    { 
    inc = base+1; 
    do 
    { 
    if (inc - base <= (A[base] + A[inc])) 
    {          
    intersect ++; 
    if (!(intersect^10000000)) 
    { 
     return -1; 
    } 
    } 
    inC++; 
    } while (inc < n); 
    } 
} 

return intersect; 
} 

は

Answer 1

あなたのアプローチは、O（N^2）でお時間をいただき、ありがとうございますのディスク。

私は私の頭の上から漸近的により良いパフォーマンスを得るための方法を考えることはできませんが、あなたが作ることができる1つの最適化があります。

あなたは半径pの要素pにいるとします。明らかに、p - mに位置する全てのディスクは、y = mでディスクによって覆われる中心を有する。< = y < = p + m。したがって、ディスクよりも遠く離れた場所で作業するだけで済みます。

Answer 2

コメントに指摘されているように、これは実際には1次元の問題です。実際には、間隔[x、y]はディスクx = center - radiusとy = center + radiusのxとxの最小座標に対応する交差区間の問題です。

xとyの点に沿って左から右に移動することを考えてみましょう。ディスクへの2つのポインタ（1つはxポイント用、もう1つはyポイント用）を保持してソートせずに行うことができます。データ構造を使用して、現在のポインタの下のディスクを追跡します。 xポイントが表示されたら、ポイントのディスクと現在のすべてのディスクとの交差点を認識し、それを現在のディスクにします。 yポイントが表示されたら、そのポイントのディスクを現在のディスクから削除します。

Answer 3

あなたのコードは早すぎる最適化のような臭いがあります。文の場合、それは（外側のループは、n = 1 <で実行されません）あまりとにかくあなたを助けにはなりませんよう

は、外側を取り除きます。

そこに魔法の定数（10000000）を取り外し、ビットいじるのトリックを（私は仮定）。これは、（少なくとも一定の変数でなければならない）全てで柔軟、読み取ることは困難ではないです、そしてロジックはあまり代わり==のXORを用いて表現されます。

あなたのdo-whileループをfor-loopを読みやすいように交換することがあります。 （@Philipポッターにより示唆されるように）

は今、あなたのコードが遅くなるではないがより鮮明になります。たぶんあなたは既にコードと括弧のいくつかの行を保存していることを理解しているかもしれません。そのため他の記事を参照してください -

は今で読み取り可能なコードで、あなたは最終的に前に隠された大きな最適化に開放されています。

注：巧妙な最適化のトリックを早めに行わないでください。彼らはあなたをしませんいずれか良いです。

編集：手始めに;-)

int number_of_intersections (int A[], int n) 
{ 
    int intersect = 0; 
    const int maxIntersections = 10000000;  

    for (int base = 0; base < n-1; base++) 
    { 
     for(int inc = base+1; inc < n; inc++) 
     { 
      if (inc - base <= A[base] + A[inc]) 
      {          
       intersect ++; 
       if (intersect == maxIntersections) return -1; 
      } 
     } 
    } 

    return intersect; 
}