Permalink
Reply
I have written this simple bruteforce algorithm that finds max sum of subsequence in some sequence, both in C# and D. And when the size of array is 1000000 elements - D is 20 seconds lated. Why?
D code (algorithm):
'
public int solveBruteForce()
{
int currMax = arr[0], currSum;
foreach (_; arr)
{
currSum = 0;
foreach (int el; arr)
{
currSum += el;
currMax = max(currSum, currMax);
}
}
return currMax;
}
'
D code (measuring exec time):
'
double measureTime()
{
StopWatch sw;
sw.start();
solveDynamic();
double sec = (to!double(sw.peek.total!"msecs") / 1000) + (to!double(sw.peek.total!"usecs") / 1000000);
return sec;
}
'
C# code (alg):
'
int EachOther(int[] array)
{
int current_max = array[0];
for (int i = 0; i < array.Length; i++)
{
int subset_sum = 0;
for (int j = i; j < array.Length; j++)
{
subset_sum += array[j];
current_max = Math.Max(subset_sum, current_max);
}
}
return current_max;
}
'
C# code (time measuring):
'
Stopwatch stopwatch = new Stopwatch();
for (int cur_size = 1000; cur_size <= size_max; cur_size *= 10)
{
int[] array = GenArray(cur_size);
stopwatch.Start();
EachOther(array);
stopwatch.Stop();
double time = (double)stopwatch.ElapsedTicks / Stopwatch.Frequency;
Console.Write("{0, -10}|", string.Format("{0:f7}", time));
}
Console.WriteLine();
'
