How to optimize euclidian algorithm?-CodePudding

I need to calculate euclidian distance for every point in matrix and store it into the List. But it works too slow. How can I get it faster?

public static char[,] fields = new char[10000, 10000]; // it contains different count of 't' and 'r' symbols
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))));
            }
        }

CodePudding user response：

Ok, here is another hint which might help - use specific squared function instead of generic Pow

double Squared(int x) => (double)(x*x);

so code would be

Math.Sqrt(Squared(i - x)   Squared(r - y))

And another optimization might be realized if your use of the result might be converted to dealing with distance squared. E.g. comparison far/near could be easily done with distance squared. Then, you could save on computing square root of distance squared.

UPDATE

You could save one conversion operation if you do Squared all integers and convert to doubles later just before taking square root

Along the lines

int Squared(int x) => (x*x);

and

Math.Sqrt((double)(Squared(i - x)   Squared(r - y)));

CodePudding user response：

You could pre-calculate each of the squares, so each squaring calculation is performed 10000 times instead of 10000*10000 times.

public static double[] preCalcSquares(int n) {
    double[] pre=new double[10000];
    for (int i = 0; i < 10000; i  )
    {
        pre[i]=(i-n)*(i-n);
    }
    return pre;
}

. . .
double[] xSquares=preCalcSquares(x);
double[] ySquares=preCalcSquares(y);
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(xSquares[i]   ySquares[r])));
    }
}