Каков наиболее эффективный способ избежать дублирования операций в массиве С#?

Мне нужно рассчитать расстояния между каждой парой точек в массиве и только делать это один раз за пару. Является ли то, что я придумал достаточно эффективно, или есть лучший способ? Вот пример, а также визуальное объяснение того, что я пытаюсь получить:

например, сначала получить сегменты 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.

Ответы

Ответ 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;
                    });
            });

Ответ 2

Мне приходилось выполнять такие операции в прошлом, и я думаю, что ваша немедленная реакция на операции с большим количеством ошибок - "должен быть более быстрый или более эффективный способ сделать это". Единственное другое даже удаленное решение, о котором я могу думать, - это хэш-пара и помещать этот хэш в HashSet, а затем проверить HashSet перед выполнением вычисления расстояния. Однако это, скорее всего, в конечном итоге ухудшится для производительности.

Вы - хорошее решение. Как указывает j0aqu1n, вам, вероятно, придется так или иначе перебить числа, и в этом случае вы никогда не будете выполнять один и тот же расчет дважды.

Будет интересно посмотреть, есть ли другие решения для этого.

Ответ 3

Выглядит хорошо, но у вас нет ошибки?

Каждая из внутренних итераций будет перезаписывать предыдущую почти полностью, за исключением ее первой позиции. Не правда ли?

То есть, в distanceArray[otherPointIndex] otherPointIndex получает значения от currentPointIndex + 1 до pointsArray.Length - 1.
В вашем примере это будет находиться на [0-3] вместо [0-6].

Ответ 4

Я думаю, немного быстрее использовать xDistance*xDistance вместо Math.Pow(xDistance, 2). Кроме того, если вам действительно нужно рассчитать все расстояния, нет места для улучшения. Если, OTOH, вам иногда не нужно вычислять все, вы могли бы рассчитать расстояния лениво, когда это необходимо.