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?
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.
Have a look at unsafe code. As far as I know, it lets you surpass bounds checking of built-in arrays, what would be faster.
Edit: This question has some answers that might be interesting.
Here is a slightly modified version of your code that performs faster (this is even faster than the unsafe/pointer code) ...
static double FindMaxFastest(double[] x, int startIndex, int endIndex)
{
int i = startIndex;
double max = double.MinValue;
do
{
if (max < x[i])
max = x[i];
} while (i++ < endIndex);
return max;
}
You can try unsafe/pointer math in C# but it won't gain you the boost you expect. unsafe can also even decrease performance as the compiler and runtime can't do some of its internal optimizations.
static unsafe double FixMaxFixed(double[] doubles, int startIndex, int endIndex)
{
var i = startIndex;
double max = double.MinValue;
fixed (double* p = doubles)
{
do
{
if (max < *(p + i))
max = *(p + i);
} while (i++ < endIndex);
}
return max;
}
... here is the test harness I used ...
static void Main()
{
var rnd = new Random();
var set = Enumerable.Range(0, 10000000).Select(i => rnd.NextDouble() * 100).ToArray();
var s = 50;
var e = 1000000;
var sw = new Stopwatch();
var r = new[] { new List<long>(), new List<long>(), new List<long>() };
for (var i = 0; i < 1000; i++)
{
sw.Restart();
FixMaxFixed(set, s, e);
sw.Stop();
r[0].Add(sw.ElapsedTicks);
sw.Restart();
FindMax(set, s, e);
sw.Stop();
r[1].Add(sw.ElapsedTicks);
sw.Restart();
FindMaxFastest(set, s, e);
sw.Stop();
r[2].Add(sw.ElapsedTicks);
}
//5721.785 6098.866 5432.225
Console.WriteLine(string.Join(" ", r.Select(i => i.Average())));
Console.Read();
}
... Using a Duff's device can really increase the performance (unrolling your loop) ...
(This runs in 50% of the time of my first example if the set is in descending order... 75% of the time if it is in ascending order)
static double FindMaxDuff(double[] x, int startIndex, int endIndex)
{
double max = x[startIndex];
switch ((endIndex - startIndex) % 10)
{
case 0:
if (max < x[startIndex++]) max = x[startIndex];
goto case 9;
case 9:
if (max < x[startIndex++]) max = x[startIndex];
goto case 8;
case 8:
if (max < x[startIndex++]) max = x[startIndex];
goto case 7;
case 7:
if (max < x[startIndex++]) max = x[startIndex];
goto case 6;
case 6:
if (max < x[startIndex++]) max = x[startIndex];
goto case 5;
case 5:
if (max < x[startIndex++]) max = x[startIndex];
goto case 4;
case 4:
if (max < x[startIndex++]) max = x[startIndex];
goto case 3;
case 3:
if (max < x[startIndex++]) max = x[startIndex];
goto case 2;
case 2:
if (max < x[startIndex++]) max = x[startIndex];
goto case 1;
case 1:
if (max < x[startIndex++]) max = x[startIndex];
break;
}
do
{
if (max < x[startIndex + 1]) max = x[startIndex + 1];
if (max < x[startIndex + 2]) max = x[startIndex + 2];
if (max < x[startIndex + 3]) max = x[startIndex + 3];
if (max < x[startIndex + 4]) max = x[startIndex + 4];
if (max < x[startIndex + 5]) max = x[startIndex + 5];
if (max < x[startIndex + 6]) max = x[startIndex + 6];
if (max < x[startIndex + 7]) max = x[startIndex + 7];
if (max < x[startIndex + 8]) max = x[startIndex + 8];
if (max < x[startIndex + 9]) max = x[startIndex + 9];
if (max < x[startIndex + 10]) max = x[startIndex + 10];
} while ((startIndex += 10) < endIndex);
return max;
}
That depends on the amount of element you have, there are some scenarios that your algorithm runs faster than others. For example, if you use the HeapSort, the order of sorting is O(n log n) and then pick in the maximum is O(1). Now you want the second max, you can mark the max with a boolean and again you can run the Heapsort for the same collection looking just the values that ar not marked. The order still the same. For references you can go here https://en.wikipedia.org/wiki/Heapsort
I think that the best computational complexity you'll get for an unsorted array is O(n).
You could maintain two copies of the array (one sorted, one unsorted) if you don't mind the extra complexity and memory consumption. (It would also incur some cost "up front" for creating the second array).
Otherwise, as others have indicated, you could parallelize this. That won't alter the computational complexity, but it could potentially improve the performance. Note the word "could" - parallelizing typically incurs some overhead too.
