Advertisement
AlexMatveev

Untitled

Oct 7th, 2012
1,319
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C 2.79 KB | None | 0 0
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3.  
  4. long long TimeValue=0;
  5.  
  6. unsigned long long time_RDTSC(){
  7.   union ticks{
  8.     unsigned long long tx;
  9.     struct dblword { long tl,th; } dw; // little endian
  10.   } t;
  11.   asm("rdtsc\n": "=a"(t.dw.tl),"=d"(t.dw.th));
  12.   return t.tx;
  13. } // for x86 only!
  14.  
  15. void time_start() { TimeValue=time_RDTSC(); }
  16.  
  17. long long time_stop() { return time_RDTSC()-TimeValue; }
  18.  
  19. void swap(int *a, int *b){
  20.     int c = *a;
  21.     *a = *b;
  22.     *b = c;
  23. }
  24. void Snuffle(int array[], int n){
  25.     int i;
  26.     for (i = 0; i < n; i++)
  27.         swap(array + i, array + (rand() % n));
  28. }
  29.  
  30. void ForwardInit(int array[], int n){
  31.     int i;
  32.     array[n-1] = 0;
  33.     for(i = 0; i < n -1; i++)
  34.         array[i]=i+1;
  35. }
  36.  
  37. void BackwardInit(int array[], int n){
  38.     int i;
  39.     array[0] = n-1;
  40.     for (i = 0; i < n; i++)
  41.         array[i+1] = i;
  42. }
  43.  
  44. void RandomInit(int array[],  int n){
  45.     int i;
  46.     int *TempArray;
  47.     TempArray = (int *)calloc(n,  sizeof(int));
  48.     ForwardInit(TempArray, n);
  49.     Snuffle(TempArray, n);
  50.     for(i = 0; i < n; i++)
  51.         array[TempArray[i]] = TempArray[i+1];
  52.     array[TempArray[n-1]] = TempArray[0];
  53.     free(TempArray);
  54. }
  55.  
  56. long long CalculateSum(int array[], int n){
  57.     long long sum = 0;
  58.     long long x = array[0];
  59.     int count = 0;
  60.     while(count < n){
  61.       sum+=array[x];
  62.       x = array[x];
  63.       if (x==array[0])
  64.         count++;
  65.     }
  66.     return sum;
  67. }
  68.  
  69. int main(){
  70.     int cycles = 10;
  71.     int n=10;
  72.     long long sum;
  73.     long long time;
  74.     int i;
  75.     int *array;
  76.     for(n = 1024/sizeof(int); n <1024*1024/(sizeof(int)); n+=1024/sizeof(int)){
  77.         array = (int *)calloc(n, sizeof(int));
  78.    
  79.         CalculateSum(array,  1);
  80.  
  81.         ForwardInit(array, n);
  82.         time_start();
  83.         sum = CalculateSum(array, cycles);
  84.         time = time_stop();
  85.         printf("%lld ",  time/(n*sizeof(int)));
  86.         printf("%lld ", sum);
  87.  
  88.         BackwardInit(array, n);
  89.         time_start();
  90.         sum = CalculateSum(array, cycles);
  91.         time = time_stop();
  92.         printf("%lld ",  time/(n*sizeof(int)));
  93.         printf("%lld ", sum);
  94.  
  95.         RandomInit(array, n);
  96.         time_start();
  97.         sum = CalculateSum(array, cycles);
  98.         time = time_stop();
  99.         printf("%d %lld ",  n, time/(n*sizeof(int)));
  100.         printf("%lld\n", sum);
  101.  
  102.         free(array);
  103.     }
  104.     for(;n < 4*1024*1024/(sizeof(int)); n+=256*1024/sizeof(int)){
  105.         array = (int *)calloc(n, sizeof(int));
  106.    
  107.         CalculateSum(array,  1);
  108.  
  109.         ForwardInit(array, n);
  110.         time_start();
  111.         sum = CalculateSum(array, cycles);
  112.         time = time_stop();
  113.         printf("%lld ",  time/(n*sizeof(int)));
  114.         printf("%lld ", sum);
  115.  
  116.         BackwardInit(array, n);
  117.         time_start();
  118.         sum = CalculateSum(array, cycles);
  119.         time = time_stop();
  120.         printf("%lld ",  time/(n*sizeof(int)));
  121.         printf("%lld ", sum);
  122.  
  123.         RandomInit(array, n);
  124.         time_start();
  125.         sum = CalculateSum(array, cycles);
  126.         time = time_stop();
  127.         printf("%d %lld ",  n, time/(n*sizeof(int)));
  128.         printf("%lld\n", sum);
  129.  
  130.         free(array);
  131.     }
  132.     return 0;
  133. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement