Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <stdio.h>
- #include <stdlib.h>
- long long TimeValue=0;
- unsigned long long time_RDTSC(){
- union ticks{
- unsigned long long tx;
- struct dblword { long tl,th; } dw; // little endian
- } t;
- asm("rdtsc\n": "=a"(t.dw.tl),"=d"(t.dw.th));
- return t.tx;
- } // for x86 only!
- void time_start() { TimeValue=time_RDTSC(); }
- long long time_stop() { return time_RDTSC()-TimeValue; }
- void swap(int *a, int *b){
- int c = *a;
- *a = *b;
- *b = c;
- }
- void Snuffle(int array[], int n){
- int i;
- for (i = 0; i < n; i++)
- swap(array + i, array + (rand() % n));
- }
- void ForwardInit(int array[], int n){
- int i;
- array[n-1] = 0;
- for(i = 0; i < n -1; i++)
- array[i]=i+1;
- }
- void BackwardInit(int array[], int n){
- int i;
- array[0] = n-1;
- for (i = 0; i < n; i++)
- array[i+1] = i;
- }
- void RandomInit(int array[], int n){
- int i;
- int *TempArray;
- TempArray = (int *)calloc(n, sizeof(int));
- ForwardInit(TempArray, n);
- Snuffle(TempArray, n);
- for(i = 0; i < n; i++)
- array[TempArray[i]] = TempArray[i+1];
- array[TempArray[n-1]] = TempArray[0];
- free(TempArray);
- }
- long long CalculateSum(int array[], int n){
- long long sum = 0;
- long long x = array[0];
- int count = 0;
- while(count < n){
- sum+=array[x];
- x = array[x];
- if (x==array[0])
- count++;
- }
- return sum;
- }
- int main(){
- int cycles = 10;
- int n=10;
- long long sum;
- long long time;
- int i;
- int *array;
- for(n = 1024/sizeof(int); n <1024*1024/(sizeof(int)); n+=1024/sizeof(int)){
- array = (int *)calloc(n, sizeof(int));
- CalculateSum(array, 1);
- ForwardInit(array, n);
- time_start();
- sum = CalculateSum(array, cycles);
- time = time_stop();
- printf("%lld ", time/(n*sizeof(int)));
- printf("%lld ", sum);
- BackwardInit(array, n);
- time_start();
- sum = CalculateSum(array, cycles);
- time = time_stop();
- printf("%lld ", time/(n*sizeof(int)));
- printf("%lld ", sum);
- RandomInit(array, n);
- time_start();
- sum = CalculateSum(array, cycles);
- time = time_stop();
- printf("%d %lld ", n, time/(n*sizeof(int)));
- printf("%lld\n", sum);
- free(array);
- }
- for(;n < 4*1024*1024/(sizeof(int)); n+=256*1024/sizeof(int)){
- array = (int *)calloc(n, sizeof(int));
- CalculateSum(array, 1);
- ForwardInit(array, n);
- time_start();
- sum = CalculateSum(array, cycles);
- time = time_stop();
- printf("%lld ", time/(n*sizeof(int)));
- printf("%lld ", sum);
- BackwardInit(array, n);
- time_start();
- sum = CalculateSum(array, cycles);
- time = time_stop();
- printf("%lld ", time/(n*sizeof(int)));
- printf("%lld ", sum);
- RandomInit(array, n);
- time_start();
- sum = CalculateSum(array, cycles);
- time = time_stop();
- printf("%d %lld ", n, time/(n*sizeof(int)));
- printf("%lld\n", sum);
- free(array);
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement