Проблемы с ctime и время работы функции работы

У меня возникли проблемы с разработкой времени для выполнения двух моих функций maxsubarray. (Справа в нижней части кода) Выход он дает мне:Проблемы с ctime и время работы функции работы

Inputsize: 101 Time using Brute Force:0 Time Using DivandCon: 12

правильно во второй раз я использую часы(), но для первой разности 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

источник

2015-08-18 Xaryu

@chux изменен! thankyou – Xaryu

«... вывод его дает мне правильно ...» Предложите опубликовать вывод (и форматировать код). – chux

В моем компиляторе (MSVC 2015) функция BruteForce встроена и работает ДЕЙСТВИТЕЛЬНО быстро. Я считаю, что «меньше одного такта» - правильное время! –

Возвращение значения из BruteForce и maxSubArraySum никогда не используются, и это дает компилятору много Lattitude, когда речь идет об их оптимизации.

На моей машине, например, использование clang -O3 уменьшает вызов до BruteForce к векторной копии и ничего больше.

Один способа заставить оценки этих функций, чтобы записать свои результаты в летучие переменные:

volatile int mb, md; 
// ... 
    mb = BruteForce(array, n); 
    // ... 
    md = maxSubArraySum(array, 0, n-1);

В переменных являются летучими, значение задается в правой части заданий должно быть сохранено , несмотря на отсутствие каких-либо других побочных эффектов, что мешает компилятору оптимизировать вычисление.

источник

2015-08-18 20:24:14 halfflat

О, я вижу, теперь я сделал это с моими модификациями к моему коду (опубликовано выше) im gettign значение для 'BruteForce', но' 0' и '1' для' maxSubArraySum' и 'Kedane'. Может ли это работать, скажем, используя значения 'mb' и т. Д., Печатая их в файл, чтобы я их использовал? – Xaryu

Без дальнейших испытаний, я предполагаю, что вы просто получаете очень маленькие тайминги для двух других функций. Прежде чем искать более экзотические решения, я бы поставил их в цикл синхронизации, например. 'volatile int m; А = часы(); for (int i = 0; i <1000; ++ i) m = the_function(); В = часы(); ' – halfflat

Проблемы с ctime и время работы функции работы

ответ

Смежные вопросы