C# Need faster method to find the maximum double value from a sub array [duplicate]

Question

I need a faster method to find the maximum double value from a sub array.

This is how I do it now:

static double FindMax(double[] x, int startIndex, int endIndex)
{
    int i = startIndex;
    double max = x[i++];
    double value;
    while(i <= endIndex)
    {
        value = x[i++];
        if (value > max) max = value;
    }
    return max;
}

But it is a bit slow. I need a faster method. Any tips?

Answer 1

Raw while or for is likely the fastest version you can have in C# with single threaded code (the only thing you pay is boundary checks - unsafe may give you a bit more performance by avoiding bounds checks). Any LINQ on top of that would just slow things down.

Max is O(n) operation - if you need faster than that you need to use other data structures to store information. Sorted array would be the fastest (O(1) for max/min) but cost a lot to insert, heap or sort trees could be an option too.

Alternatively you can simply track max value of the array on all operations on it. You'll have to wrap array and pay a bit on every operation to keep "max" up to date all the time, but you'll get O(1) for max and keep all other operations on array at the same performance and preserve order.