在C#数组中，避免重复操作的最有效方法是什么？

Question

我需要计算数组中每对点之间的距离，并且只想执行一次。我想知道我想出来的方法是否足够高效，或者是否有更好的方法？这里有一个示例，以及一个图形来解释我想要获得什么：

例如，首先获取A-B、A-C、A-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更有效。

- Stonetip

---

这看起来不错。既高效又可行。你是想将这个贴子发在代码审核(Code Review)板块吗？http://codereview.stackexchange.com/ - yamen

@yamen 我不知道有这个选项。我能把这个问题移动到那里吗？谢谢！ - Stonetip

我的感觉是这是最好的方法；假设所有点都是唯一的，那么从点集中生成所有组合的逻辑上最好的方法是在整个集合上迭代一次，然后在每次迭代中从该点开始迭代其余部分。因此，您永远不会生成组合“A，B”和“B，A”。也就是说，这假定您绝对需要存储距离，并且确实不能仅依靠按需计算它们。但这超出了您问题的范围。 - Andras Zoltan

@AndrasZoltan 是的，在现实世界中使用的点将是唯一的。目前还不确定我们是否会存储距离以进行进一步的计算，或者只保留在某个范围内的距离。在后一种情况下，我可能会将距离添加到List<double>中。 - Stonetip

Answer 1

如果你有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;
                    });
            });

- j0aqu1n

---

谢谢您的建议。我会尝试自己实现，但如果有与我的示例相关的示例，当然会很感激。 - Stonetip

注意：当点的数量很大且性能至关重要时，将此代码从简单的for循环更改为Parallel.ForEach是有道理的。否则，这只是不必要的复杂性。此外，在将元素分配给数组之前，此代码需要使用lock(distanceArray)来避免线程问题。 - j0aqu1n

Answer 2

我过去曾经执行过这样的操作，我认为你对高计算量操作的直接反应是“一定有更快或更有效的方法来完成这个任务”。

我能想到的唯一其他可行的解决方案是将这对数据进行哈希处理，并将此哈希放入 HashSet 中，在进行距离计算之前检查 HashSet。然而，这可能最终会导致性能更差。

你的解决方案很好。正如 j0aqu1n 指出的那样，你可能不得不以某种方式计算这些数字，在这种情况下，你从未执行相同的计算。

如果有其他解决方案，那将会很有趣。

- Rob

Answer 3

看起来不错，但是你没有bug吗？

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

也就是说，在distanceArray [otherPointIndex]中，otherPointIndex的值从currentPointIndex + 1到pointsArray.Length - 1。在你的例子中，这将范围在[0-3]而不是[0-6]。

- ANeves

---

是的，我确实遇到了一个错误，但我认为那不是问题所在。记住，我使用0-3（分数）来获取六个片段。你的问题让我意识到我搞乱了距离数组。它需要自己的增量器。谢谢。 - Stonetip

Answer 4

我认为，使用xDistance*xDistance比使用Math.Pow(xDistance, 2)要快一些。 除此之外，如果你确实需要计算所有距离，那么改进的空间不大。 但是，如果有时候你不需要计算所有距离，可以在需要时懒惰地计算距离。

- Henrik

---

我会在大数据集上尝试一下，效果应该很明显。我敢打赌你是对的。有趣的是，我字面上地将 x^2 翻译为 Math.Pow 而不是像你建议的那样操作。 - Stonetip