C＃配列の重複した操作を避ける最も効率的な方法は何ですか？

Question

配列内のすべての点のペア間の距離を計算する必要があります。ペアごとに1回しか行いません。私は十分に効率的であるか、よりよい方法がありますか？ここでの例では、私が取得しようとしているかを説明するために視覚と共に、次のとおり

例えば、第一のセグメントを-B、A-C、-Dを得ます。次にB-C、B-D;そして最後にC-D。言い換えれば、私たちは新しいアレイにA-Bが必要だが、B-Aは複製ではないからだ。これは、ポイントの何千で使用されますので

var pointsArray = new Point[4]; 

pointsArray[0] = new Point(0, 0); 
pointsArray[1] = new Point(10, 0); 
pointsArray[2] = new Point(10, 10); 
pointsArray[3] = new Point(0, 10); 

// using (n * (n-1))/2 to determine array size 
int distArraySize = (pointsArray.Length*(pointsArray.Length - 1))/2; 

var distanceArray = new double[distArraySize]; 

int distanceArrayIndex = 0; 

// Loop through points and get distances, never using same point pair twice 
for (int currentPointIndex = 0; currentPointIndex < pointsArray.Length - 1; currentPointIndex++) 
{ 
    for (int otherPointIndex = currentPointIndex + 1; 
      otherPointIndex < pointsArray.Length; 
      otherPointIndex++) 
    { 
     double xDistance = pointsArray[otherPointIndex].X - pointsArray[currentPointIndex].X; 
     double yDistance = pointsArray[otherPointIndex].Y - pointsArray[currentPointIndex].Y; 

     double distance = Math.Sqrt(Math.Pow(xDistance, 2) + Math.Pow(yDistance, 2)); 

     // Add distance to distanceArray 
     distanceArray[distanceArrayIndex] = distance; 

     distanceArrayIndex++; 
    } 
} 

、私は正確に寸法の配列はIEnumerableをの任意の並べ替えを使用するよりも効率的であると思っています。

Answer 1

ポイントがある場合、ポイントのすべてのペアのセットには、n *（n-1）/ 2要素が含まれます。それはあなたがやっている操作の数です。私が行う唯一の変更は、Parallel.ForEach（）を使って操作を並行して行うことです。

このような何かが（デバッグを必要とする）

 int distArraySize = (pointsArray.Length * (pointsArray.Length - 1))/2; 

     var distanceArray = new double[distArraySize]; 

     int numPoints = pointsArray.Length; 

     Parallel.ForEach<int>(Enumerable.Range(0, numPoints - 2), 
      currentPointIndex => 
      { 
       Parallel.ForEach<int>(Enumerable.Range(currentPointIndex + 1, numPoints - 2), 
        otherPointIndex => 
        { 
         double xDistance = pointsArray[otherPointIndex].X - pointsArray[currentPointIndex].X; 
         double yDistance = pointsArray[otherPointIndex].Y - pointsArray[currentPointIndex].Y; 
         double distance = Math.Sqrt(xDistance * xDistance + yDistance * yDistance); 
         int distanceArrayIndex = currentPointIndex * numPoints - (currentPointIndex * (currentPointIndex + 1)/2) + otherPointIndex - 1; 
         distanceArray[distanceArrayIndex] = distance; 
        }); 
      }); 

Answer 2

私は過去にこのような操作を実行するために持っていた、と私は高い数字クランチ操作へのあなたの即時の反応が速いかがなければならない」だと思いますこれを行うためのより効率的な方法です」。 私が考えることができるリモートで実行可能な解決策は、ペアをハッシュしてこのハッシュをHashSetに配置し、次に距離計算を行う前にHashSetをチェックすることだけです。しかし、最終的にはパフォーマンスが悪化する可能性があります。

あなたは解決策が良いです。 j0aqu1nが指摘しているように、あなたはおそらく何らかの方法で数値をクランチする必要があります。この場合、同じ計算を2回実行することはありません。

他の解決策があるかどうかは興味深いでしょう。

Answer 3

私にはうまく見えますが、バグはありませんか？

それぞれの内側の繰り返しは、最初の位置を除いて、前のものをほぼ完全に上書きします。それはありませんか？

つまり、distanceArray[otherPointIndex]で、otherPointIndexはcurrentPointIndex + 1からpointsArray.Length - 1に値を取得します。
あなたの例では、[0-6]の代わりに[0-3]の範囲になります。

Answer 4

Math.Pow(xDistance, 2)の代わりにxDistance*xDistanceを使用するのが少し速いと思います。 これ以外にも、常にすべての距離を計算する必要がある場合は、改善の余地があまりありません。 OTOHですべてを計算する必要がない場合は、必要に応じて遅延を計算することができます。