SHARE
TWEET

quadrants.c

a guest Mar 24th, 2014 81 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. // 4 квадранта (определить в каком из них точка [a,b])
  2. #include <stdio.h>
  3. #include <stdlib.h>
  4. #include <stdint.h>
  5. #include <string.h>
  6. #include <limits.h>
  7.  
  8. #include <locale.h>
  9.  
  10. #include <sys/time.h>
  11.  
  12. long long
  13. mtime()
  14. {
  15.   struct timeval t;
  16.  
  17.   gettimeofday(&t, NULL);
  18.   long long mt = (long long)t.tv_sec * 1000 + t.tv_usec / 1000;
  19.   return mt;
  20. }
  21.  
  22. int
  23. main (int ac, char *av[])
  24. {
  25.   double a = 10, b = -10, dx = 1000, dy = 2000;
  26.   uint64_t *pa = (void *)&a, *pb = (void *)&b;
  27.  
  28. #if 0
  29.   printf ("0x%016llx 0x%016llx\n", (long long)*pa, (long long)*pb);
  30.  
  31.   for (double a = 1; a > -2; a -= 2)
  32.     for (double b = 1; b > -2; b -= 2) {
  33.       uint64_t *pa = (void *)&a, *pb = (void *)&b;
  34.       int qn = ((*pa >> 62) & 2) | (*pb >> 63);
  35.       printf("[%f , %f] qn = %d\n", a, b, qn);
  36.     }
  37.  
  38. #endif
  39.  
  40.   int n = atoi(av[1] ? av[1] : "10000000"), k = 10;
  41.   int qn, cnt[4] = {0};
  42.   srand(0);
  43.   long long start = mtime();
  44.   for (int i = 0; i < n; i++) {
  45.     a = rand() - INT_MAX / 2;
  46.     b = rand() - INT_MAX / 2;
  47.     a += dx; b += dy;
  48.     qn = ((*pa >> 62) & 2) | (*pb >> 63);
  49.     cnt[qn]++;
  50.   }
  51.   printf ("shift: %lld (msec) n: %d [%d %d %d %d]\n",
  52.           mtime() - start, n, cnt[0], cnt[1], cnt[2], cnt[3]);
  53.  
  54.   memset(cnt, 0, sizeof(cnt));
  55.   srand(0);
  56.   start = mtime();
  57.   for (int i = 0; i < n; i++) {
  58.     a = rand() - INT_MAX / 2;
  59.     b = rand() - INT_MAX / 2;
  60.     if ( a < -dx)
  61.       if (b < -dy)
  62.         qn = 3;
  63.       else
  64.         qn = 2;
  65.     else
  66.       if (b < -dy)
  67.         qn = 1;
  68.       else
  69.         qn = 0;
  70.     cnt[qn]++;
  71.   }
  72.   printf ("if: %lld (msec) n: %d [%d %d %d %d]\n",
  73.           mtime() - start, n, cnt[0], cnt[1], cnt[2], cnt[3]);
  74.      
  75.   if (n > 40000000) {
  76.     puts("no memory");
  77.     exit(1);
  78.   }
  79.  
  80.   puts ("=== in mem ===");
  81.   int sum = 0;
  82.   double *x = malloc(n * sizeof(*x)), *y = malloc(n * sizeof(*y));
  83.   char *q = malloc(n);
  84.  
  85.   srand(0);
  86.   for (int i = 0; i < n; i++) {
  87.     x[i] = rand() - INT_MAX / 2;
  88.     y[i] = rand() - INT_MAX / 2;
  89.   }
  90.  
  91.   start = mtime();
  92.   for (int j = 0; j < k; j++) {
  93.     for (int i = 0; i < n; i++) {
  94.       pa = (typeof(pa))(x + i);
  95.       pb = (typeof(pa))(y + i);
  96.       q[i] = ((*pa >> 62) & 2) | (*pb >> 63);
  97.     }
  98.     if (q[n - j - 1] == 2)
  99.       sum++;
  100.   }
  101.   printf ("shift place: %lld (msec) n: %d\n",
  102.           mtime() - start, n * k);
  103.  
  104.   start = mtime();
  105.   pa = (typeof(pa))&a;
  106.   pb = (typeof(pa))&b;
  107.   for (int j = 0; j < k; j++) {
  108.     for (int i = 0; i < n; i++) {
  109.       a = x[i] + dx; b = y[i] + dy;
  110.       q[i] = ((*pa >> 62) & 2) | (*pb >> 63);
  111.     }
  112.     if (q[n - j - 1] == 2)
  113.       sum++;
  114.   }
  115.   printf ("shift vars: %lld (msec) n: %d\n",
  116.           mtime() - start, n * k);
  117.  
  118.   start = mtime();
  119.   for (int j = 0; j < k; j++) {
  120.     for (int i = 0; i < n; i++) {
  121.     if ( x[i] < -dx)
  122.       if (y[i] < -dy)
  123.         q[i] = 3;
  124.       else
  125.         q[i] = 2;
  126.     else
  127.       if (y[i] < -dy)
  128.         q[i] = 1;
  129.       else
  130.         q[i] = 0;
  131.     }
  132.     if (q[n - j - 1] == 2)
  133.       sum++;
  134.   }
  135.   printf ("if: %lld (msec) n: %d\n",
  136.           mtime() - start, n * k);
  137.  
  138.   for (int i = 0; i < n; i++)
  139.     sum += q[i];
  140.  
  141.   printf ("sum = %d\n", sum);
  142.   return 0;
  143. }
  144.  
  145.  
  146.  
  147. #if 0
  148. avp@avp-ubu1:hashcode$ ./a.out 100000000
  149. shift: 1947 (msec) n: 100000000 [25003993 24997380 24993591 25005036]
  150. if: 2282 (msec) n: 100000000 [25003993 24997380 24993591 25005036]
  151. no memory
  152. avp@avp-ubu1:hashcode$ ./a.out 100000000
  153. shift: 1871 (msec) n: 100000000 [25003993 24997380 24993591 25005036]
  154. if: 2398 (msec) n: 100000000 [25003993 24997380 24993591 25005036]
  155. no memory
  156. avp@avp-ubu1:hashcode$ ./a.out 10000000
  157. shift: 197 (msec) n: 10000000 [2500381 2500853 2498320 2500446]
  158. if: 221 (msec) n: 10000000 [2500381 2500853 2498320 2500446]
  159. === in mem ===
  160. shift place: 143 (msec) n: 100000000
  161. shift vars: 222 (msec) n: 100000000
  162. if: 513 (msec) n: 100000000
  163. sum = 14998834
  164. avp@avp-ubu1:hashcode$ ./a.out 10000000
  165. shift: 281 (msec) n: 10000000 [2500381 2500853 2498320 2500446]
  166. if: 227 (msec) n: 10000000 [2500381 2500853 2498320 2500446]
  167. === in mem ===
  168. shift place: 143 (msec) n: 100000000
  169. shift vars: 217 (msec) n: 100000000
  170. if: 513 (msec) n: 100000000
  171. sum = 14998834
  172. avp@avp-ubu1:hashcode$ ./a.out 10000000
  173. shift: 204 (msec) n: 10000000 [2500381 2500853 2498320 2500446]
  174. if: 220 (msec) n: 10000000 [2500381 2500853 2498320 2500446]
  175. === in mem ===
  176. shift place: 140 (msec) n: 100000000
  177. shift vars: 216 (msec) n: 100000000
  178. if: 517 (msec) n: 100000000
  179. sum = 14998834
  180. avp@avp-ubu1:hashcode$
  181.  
  182. #endif
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!
 
Top