• Sign Up
• Login
• API
• FAQ
• Tools
• Archive
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.
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!

Top