11

配列内のポイントのすべてのペア間の距離を計算する必要があり、ペアごとに1回だけ実行したい. 私が思いついたものは十分に効率的ですか、それとももっと良い方法がありますか? これは、私が取得しようとしているものを説明するためのビジュアルとともに、例です。

コードの目的の図

たとえば、最初にセグメント AB、AC、AD を取得します。次にBC、BD。そして最後にCD。言い換えれば、新しい配列に AB が必要ですが、BA は重複するため、BA は必要ありません。

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 を使用するよりも効率的であると考えています。

4

4 に答える 4

3

n 個の点がある場合、点のすべてのペアのセットには 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;
                    });
            });
于 2012-05-14T12:24:14.080 に答える
0

私は過去にこのような操作を実行しなければなりませんでしたが、大量のクランチ操作に対するあなたの即時の反応は、「これを行うためのより高速で効率的な方法があるに違いない」であると思います. 私が考えることができる唯一の他のリモートで実行可能なソリューションは、ペアをハッシュし、このハッシュを HashSet に配置し、距離計算を行う前に HashSet をチェックすることです。ただし、これは最終的にはパフォーマンスが低下する可能性があります。

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

これに対する他の解決策があるかどうかを確認することは興味深いでしょう。

于 2012-05-14T12:30:12.570 に答える
0

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

于 2012-05-14T12:42:33.740 に答える
0

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

内側の反復のそれぞれは、最初の位置を除いて、前の反復をほぼ完全に上書きします。そうじゃない？

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

于 2012-05-14T12:34:59.907 に答える