11

我需要计算数组中每对点之间的距离，并且每对只需要计算一次。我想出的方法是否足够有效或有更好的方法？这是一个示例，以及解释我想要获得的内容的视觉效果：

代码用途图

例如，首先获取分段 AB、AC、AD；然后是 BC、BD；最后，CD。换句话说，我们希望 AB 在我们的新数组中，但不是 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 指出的那样，您可能不得不以一种或另一种方式处理数字，在这种情况下，您永远不会两次执行相同的计算。

看看是否有其他解决方案将会很有趣。

于 2012-05-14T12:30:12.570 回答
0

对我来说看起来不错，但你没有错误吗？

每个内部迭代都将几乎完全覆盖前一个迭代，除了它的第一个位置。不会吗？

也就是说，在distanceArray[otherPointIndex]otherPointIndex 中从currentPointIndex + 1to获取值pointsArray.Length - 1。
在您的示例中，这将在 [0-3] 而不是 [0-6] 范围内。

于 2012-05-14T12:34:59.907 回答
0

我认为，使用它xDistance*xDistance而不是Math.Pow(xDistance, 2). 除此之外，如果你真的总是需要计算所有的距离，那就没有太大的改进空间了。如果，OTOH，您有时不需要计算全部，您可以在需要时懒惰地计算距离。

于 2012-05-14T12:42:33.740 回答