Возникли проблемы с ctime и отработкой времени выполнения функции
У меня проблемы с отработкой времени для запуска двух функций maxsubarray. (справа внизу кода) Вывод, который он мне дает:
Inputsize: 101 Time using Brute Force:0 Time Using DivandCon: 12
Во второй раз я использую Clock(), но для первой разницы diff1 это просто дает мне 0 а я не уверен почему?
Изменить: пересмотренный код.
Edit2: добавлен вывод.
#include <iostream>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <limits.h>
using namespace std;
int Kedane(int a[], int size)
{
int max_so_far = 0, max_ending_here = 0;
int i;
for(i = 0; i < size; i++)
{
max_ending_here = max_ending_here + a[i];
if(max_ending_here < 0)
max_ending_here = 0;
if(max_so_far < max_ending_here)
max_so_far = max_ending_here;
}
return max_so_far;
}
int BruteForce(int array[],int n)
{
int sum,ret=0;
for(int j=-1;j<=n-2;j++)
{
sum=0;
for(int k=j+1;k<+n-1;k++)
{
sum+=array[k];
if(sum>ret)
{
ret=sum;
}
}
}
return ret;
}
//------------------------------------------------------
// FUNCTION WHICH FINDS MAX OF 2 INTS
int max(int a, int b) { return (a > b)? a : b; }
// FUNCTION WHICH FINDS MAX OF 3 NUMBERS
// CALL MAX FUNCT FOR 2 VARIS TWICE!
int max(int a, int b, int c) { return max(max(a, b), c); }
// WORKS OUT FROM MIDDLE+1->RIGHT THE MAX SUM &
// THE MAX SUM FROM MIDDLE->LEFT + RETURNS SUM OF THESE
int maxCrossingSum(int arr[], int l, int m, int h)
{
int sum = 0; // LEFT OF MID
int LEFTsum = INT_MIN; // INITIALLISES SUM TO LOWEST POSSIBLE INT
for (int i = m; i >= l; i--)
{
sum = sum + arr[i];
if (sum > LEFTsum)
LEFTsum = sum;
}
sum = 0; // RIGHT OF MID
int RIGHTsum = INT_MIN;
for (int i = m+1; i <= h; i++)
{
sum = sum + arr[i];
if (sum > RIGHTsum)
RIGHTsum = sum;
}
// RETURN SUM OF BOTH LEFT AND RIGHT SIDE MAX'S
return LEFTsum + RIGHTsum;
}
// Returns sum of maxium sum subarray in aa[l..h]
int maxSubArraySum(int arr[], int l, int h)
{
// Base Case: Only one element
if (l == h)
return arr[l];
// Find middle point
int m = (l + h)/2;
/* Return maximum of following three possible cases
a) Maximum subarray sum in left half
b) Maximum subarray sum in right half
c) Maximum subarray sum such that the subarray crosses the midpoint */
return max(maxSubArraySum(arr, l, m),
maxSubArraySum(arr, m+1, h),
maxCrossingSum(arr, l, m, h));
}
// DRIVER
int main(void)
{
std::srand (time(NULL));
// CODE TO FILL ARRAY WITH RANDOMS [-50;50]
int size=30000;
int array[size];
for(int i=0;i<=size;i++)
{
array[i]=(std::rand() % 100) -50;
}
// TIMING VARI'S
clock_t t1,t2;
clock_t A,B;
clock_t K1,K2;
volatile int mb, md, qq;
//VARYING ELEMENTS IN THE ARRAY
for(int n=101;n<size;n=n+100)
{
t1=clock();
mb=BruteForce(array,n);
t2=clock();
A=clock();
md=maxSubArraySum(array, 0, n-1) ;
B=clock();
K1=clock();
qq=Kedane(array, n);
K2=clock();
cout<< n << "," << (double)t2-(double)t1 << ","<<(double)B-(double)A << ","<<(double)K2-(double)K1<<endl;
}
return 0;
}
101,0,0,0
201,0,0,0
301,1,0,0
401,0,0,0
501,0,0,0
601,0,0,0
701,0,0,0
801,1,0,0
901,1,0,0
1001,0,0,0
1101,1,0,0
1201,1,0,0
1301,0,0,0
1401,1,0,0
1501,1,0,0
1601,2,0,0
1701,1,0,0
1801,2,0,0
1901,1,1,0
2001,1,0,0
2101,2,0,0
2201,3,0,0
2301,2,0,0
2401,3,0,0
2501,3,0,0
2601,3,0,0
2701,4,0,0
2801,4,0,0
2901,4,0,0
3001,4,0,0
3101,4,0,0
3201,5,0,0
3301,5,0,0
3401,6,0,0
3501,5,0,0
3601,6,0,0
3701,6,0,0
3801,8,0,0
3901,7,0,0
4001,8,0,0
4101,7,0,0
4201,10,1,0
4301,9,0,0
4401,8,0,0
4501,9,0,0
4601,10,0,0
4701,11,0,0
4801,11,0,0
4901,11,0,0
5001,12,0,1
5101,11,1,0
5201,13,0,0
5301,13,0,0
5401,15,0,0
5501,14,0,0
5601,16,0,0
5701,15,0,0
5801,15,1,0
5901,16,0,0
6001,17,0,0
6101,18,0,0
6201,18,0,0
6301,19,0,0
6401,21,0,0
6501,19,0,0
6601,21,1,0
6701,20,0,0
6801,22,0,0
6901,23,0,0
7001,22,0,0
7101,24,0,0
7201,26,0,0
7301,26,0,0
7401,24,1,0
7501,26,0,0
7601,27,0,0
7701,28,0,0
7801,28,0,0
7901,30,0,0
8001,29,0,0
8101,31,0,0
8201,31,1,0
8301,35,0,0
8401,33,0,0
8501,35,0,0
8601,35,1,0
8701,35,0,0
8801,36,1,0
8901,37,0,0
9001,38,0,0
9101,39,0,0
9201,41,1,0
9301,40,0,0
9401,41,0,0
9501,42,0,0
9601,45,0,0
9701,45,0,0
9801,44,0,0
9901,47,0,0
10001,47,0,0
10101,48,0,0
10201,50,0,0
10301,51,0,0
10401,50,0,0
10501,51,0,0
10601,53,0,0
10701,55,0,0
10801,54,0,0
10901,56,0,0
11001,57,0,0
11101,56,0,0
11201,60,0,0
11301,60,0,0
11401,61,1,0
11501,61,1,0
11601,63,0,0
11701,62,1,0
11801,66,1,0
11901,65,0,0
12001,68,1,0
12101,68,0,0
12201,70,0,0
12301,71,0,0
12401,72,0,0
12501,73,1,0
12601,73,1,0
12701,76,0,0
12801,77,0,0
12901,78,1,0
13001,79,1,0
13101,80,0,0
13201,83,0,0
13301,82,0,0
13401,86,0,0
13501,85,1,0
13601,86,0,0
13701,89,0,0
13801,90,0,1
13901,90,0,0
14001,91,0,0
14101,97,0,0
14201,93,0,0
14301,96,0,0
14401,99,0,0
14501,100,0,0
14601,101,0,0
14701,101,0,0
14801,103,1,0
14901,104,0,0
15001,107,0,0
15101,108,0,0
15201,109,0,0
15301,109,0,0
15401,114,0,0
15501,114,0,0
15601,115,0,0
15701,116,0,0
15801,119,0,0
15901,118,0,0
16001,124,0,0
16101,123,1,0
16201,123,1,0
16301,125,0,0
16401,127,1,0
16501,128,1,0
16601,131,0,0
16701,132,0,0
16801,134,0,0
16901,134,1,0
17001,135,1,0
17101,139,0,0
17201,139,0,0
17301,140,1,0
17401,143,0,0
17501,145,0,0
17601,147,0,0
17701,147,0,0
17801,150,1,0
17901,152,1,0
18001,153,0,0
18101,155,0,0
18201,157,0,0
18301,157,1,0
18401,160,0,0
18501,160,1,0
18601,163,1,0
18701,165,0,0
18801,169,0,0
18901,171,0,1
19001,170,1,0
19101,173,1,0
19201,178,0,0
19301,175,1,0
19401,176,1,0
19501,180,0,0
19601,180,1,0
19701,182,1,0
19801,184,0,0
19901,187,1,0
20001,188,1,0
20101,191,0,0
20201,192,1,0
20301,193,1,0
20401,195,0,0
20501,199,0,0
20601,200,0,0
20701,201,0,0
20801,209,1,0
20901,210,0,0
21001,206,0,0
21101,210,0,0
21201,210,0,0
21301,213,0,0
21401,215,1,0
21501,217,1,0
21601,218,1,0
21701,221,1,0
21801,222,1,0
21901,226,1,0
22001,225,1,0
22101,229,0,0
22201,232,0,0
22301,233,1,0
22401,234,1,0
22501,237,1,0
22601,238,0,1
22701,243,0,0
22801,242,1,0
22901,246,1,0
23001,246,0,0
23101,250,1,0
23201,250,1,0
23301,254,1,0
23401,254,0,0
23501,259,0,1
23601,260,1,0
23701,263,1,0
23801,268,0,0
23901,266,1,0
24001,271,0,0
24101,272,1,0
24201,274,1,0
24301,280,0,1
24401,279,0,0
24501,281,0,0
24601,285,0,0
24701,288,0,0
24801,289,0,0
24901,293,0,0
25001,295,1,0
25101,299,1,0
25201,299,1,0
25301,302,0,0
25401,305,1,0
25501,307,0,0
25601,310,1,0
25701,315,0,0
25801,312,1,0
25901,315,0,0
26001,320,1,0
26101,320,0,0
26201,322,0,0
26301,327,1,0
26401,329,0,0
26501,332,1,0
26601,339,1,0
26701,334,1,0
26801,337,0,0
26901,340,0,0
27001,341,1,0
27101,342,1,0
27201,347,0,0
27301,348,1,0
27401,351,1,0
27501,353,0,0
27601,356,1,0
27701,360,0,1
27801,361,1,0
27901,362,1,0
28001,366,1,0
28101,370,0,1
28201,372,0,0
28301,375,1,0
28401,377,1,0
28501,380,0,0
28601,384,1,0
28701,384,0,0
28801,388,1,0
28901,391,1,0
29001,392,1,0
29101,399,1,0
29201,399,0,0
29301,404,1,0
29401,405,0,0
29501,409,1,0
29601,412,2,0
29701,412,1,0
29801,422,1,0
29901,419,1,0
1 ответ
Возвращаемые значения из BruteForce а также maxSubArraySum никогда не используются, и это дает компилятору большую свободу действий, когда речь заходит об их оптимизации.
На моей машине, например, использование clang -O3 уменьшает вызов BruteForce в векторную копию и ничего больше.
Один из методов принудительного вычисления этих функций - записать их результаты в переменные:
volatile int mb, md;
// ...
mb = BruteForce(array, n);
// ...
md = maxSubArraySum(array, 0, n-1);
Поскольку переменные изменчивы, значение, заданное правой частью присваиваний, должно быть сохранено, несмотря на отсутствие каких-либо других побочных эффектов, которые не позволяют компилятору оптимизировать вычисления.