Как оптимизировать алгоритм с Эвклидовым расстоянием?

Question

[Sneiksus]

public static char[,] fields = new char[10000, 10000]; // содержит 't'  и 'r' символы
List<Tuple<int, int, double>> tuples = new List<Tuple<int, int, double>>();
        for (int i = 0; i < 10000; i++)
        {
            for (int r = 0; r < 10000; r++)
            {
                if (fields[i, r] != 't')
                    tuples.Add(Tuple.Create(i, r, Math.Sqrt(Math.Pow(i - x, 2) + Math.Pow(r - y, 2))));
            }
        }

Происходит поиск дистанции с каждой точкой в матрице для заданых координат. Работает очень медленно, какие есть возможности оптимизации?

UPD: чтобы не считать дистанцию для точек два раза, поменял

int r = 0

на

int r = i

, но сильного эффекта это не дало.

UPD2: нельзя ли это ускорить аппаратно? Например использовав GPU?

Comments

[Wataru]

Это часть какой-то задачи. Давайте исходную задачу, потому что эту часть особо не наоптимизируешь. Все равно придется по всем клеткам пройтись, чтобы найти там t.

Ну, хранить квадрат расстояния и не использовать pow чтобы счет в целых числах шел, ускорит в пару раз, но не принципиально.

[Sneiksus]

Wataru, Использую этот код для реализации классификатора knn алгоритма. Сначала матрица случчайно наполняется символами 'r' 'g' 'b' - какой-то цвет, 't' цвета нет. И уже в классификаторе еще раз определяю цвет для каждого rgb и сравниваю насколько он точно работает

[Alexandroppolus]

Sneiksus, а заполнение матрицы тоже происходит в таком вложенном цикле?

[Sneiksus]

Alexandroppolus, Да

Answer 1

[GavriKos]

Ну про квадрат расстояния уже сказали.
Далее - tuples проинициализируйте каким то количеством. Потому что на Add при аллокации съедите много времени.
Ну перебор конечно конский - посчитайте количество итераций, их многовато как то ) Но тут вряд ли что то сделаешь, хз. Надо читать задачу. Может можно ограничить эти итерации.
Дальше. Не видно где меняется x и что это такое, но выглядт так что Math.Pow(i - x, 2) можно вычислить до внутреннего цикла.

Я бы еще попробовал убрать Create у тупли - тоже аллокация.

НАсчет ГПУ. У вас кроме корня (который не нужен) судя по всему нет дробных чисел (хотя мы не знаем что такое x и y) - поэтому именно использование ГПУ тут не даст космического прироста. А вот второй цикл похоже можно распараллелить. На чем параллелить - без разницы

Answer 2

[Александр Ананьев]

Не ищите расстояние, ищите квадрат расстояния.

Comments

[Sneiksus]

Это как?

[GavriKos]

Sneiksus, Если вам нужно просто сравнить расстояния - типа находится ли предмет на определенном расстоянии - то можно сравнивать квадраты расстояний - и не вычислять корень. Корень - дорогая операция

[mayton2019]

Физики рассказывали. Что если у них есть задача сильного и слабого взаимодействия множества частиц в пространстве (в данном случае - на плоскости) - то они строят вокруг частиц дополнительные структуры данных QuadTree/OctalTree и дальше считают сильное взаимодействие только для частиц которые лежат внутри некого минимального квадрата (куба). Прочие - игнорируют.

Я к тому - как оптимизировать на знании того куда дальше пойдет эта информация.