quadrants.c

// 4 квадранта (определить в каком из них точка [a,b])
#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <string.h>
#include <limits.h>

#include <locale.h>

#include <sys/time.h>

long long
mtime()
{
  struct timeval t;

  gettimeofday(&t, NULL);
  long long mt = (long long)t.tv_sec * 1000 + t.tv_usec / 1000;
  return mt;
}

int
main (int ac, char *av[])
{
  double a = 10, b = -10, dx = 1000, dy = 2000;
  uint64_t *pa = (void *)&a, *pb = (void *)&b;

#if 0
  printf ("0x%016llx 0x%016llx\n", (long long)*pa, (long long)*pb);

  for (double a = 1; a > -2; a -= 2)
    for (double b = 1; b > -2; b -= 2) {
      uint64_t *pa = (void *)&a, *pb = (void *)&b;
      int qn = ((*pa >> 62) & 2) | (*pb >> 63);
      printf("[%f , %f] qn = %d\n", a, b, qn);
    }

#endif

  int n = atoi(av[1] ? av[1] : "10000000"), k = 10;
  int qn, cnt[4] = {0};
  srand(0);
  long long start = mtime();
  for (int i = 0; i < n; i++) {
    a = rand() - INT_MAX / 2;
    b = rand() - INT_MAX / 2;
    a += dx; b += dy;
    qn = ((*pa >> 62) & 2) | (*pb >> 63);
    cnt[qn]++;
  }
  printf ("shift: %lld (msec) n: %d [%d %d %d %d]\n",
      mtime() - start, n, cnt[0], cnt[1], cnt[2], cnt[3]);

  memset(cnt, 0, sizeof(cnt));
  srand(0);
  start = mtime();
  for (int i = 0; i < n; i++) {
    a = rand() - INT_MAX / 2;
    b = rand() - INT_MAX / 2;
    if ( a < -dx)
      if (b < -dy)
    qn = 3;
      else
    qn = 2;
    else
      if (b < -dy)
    qn = 1;
      else
    qn = 0;
    cnt[qn]++;
  }
  printf ("if: %lld (msec) n: %d [%d %d %d %d]\n",
      mtime() - start, n, cnt[0], cnt[1], cnt[2], cnt[3]);

  if (n > 40000000) {
    puts("no memory");
    exit(1);
  }

  puts ("=== in mem ===");
  int sum = 0;
  double *x = malloc(n * sizeof(*x)), *y = malloc(n * sizeof(*y));
  char *q = malloc(n);

  srand(0);
  for (int i = 0; i < n; i++) {
    x[i] = rand() - INT_MAX / 2;
    y[i] = rand() - INT_MAX / 2;
  }

  start = mtime();
  for (int j = 0; j < k; j++) {
    for (int i = 0; i < n; i++) {
      pa = (typeof(pa))(x + i);
      pb = (typeof(pa))(y + i);
      q[i] = ((*pa >> 62) & 2) | (*pb >> 63);
    }
    if (q[n - j - 1] == 2)
      sum++;
  }
  printf ("shift place: %lld (msec) n: %d\n",
      mtime() - start, n * k);

  start = mtime();
  pa = (typeof(pa))&a;
  pb = (typeof(pa))&b;
  for (int j = 0; j < k; j++) {
    for (int i = 0; i < n; i++) {
      a = x[i] + dx; b = y[i] + dy;
      q[i] = ((*pa >> 62) & 2) | (*pb >> 63);
    }
    if (q[n - j - 1] == 2)
      sum++;
  }
  printf ("shift vars: %lld (msec) n: %d\n",
      mtime() - start, n * k);

  start = mtime();
  for (int j = 0; j < k; j++) {
    for (int i = 0; i < n; i++) {
    if ( x[i] < -dx)
      if (y[i] < -dy)
    q[i] = 3;
      else
    q[i] = 2;
    else
      if (y[i] < -dy)
    q[i] = 1;
      else
    q[i] = 0;
    }
    if (q[n - j - 1] == 2)
      sum++;
  }
  printf ("if: %lld (msec) n: %d\n",
      mtime() - start, n * k);

  for (int i = 0; i < n; i++)
    sum += q[i];

  printf ("sum = %d\n", sum);
  return 0;
}



#if 0
avp@avp-ubu1:hashcode$ ./a.out 100000000
shift: 1947 (msec) n: 100000000 [25003993 24997380 24993591 25005036]
if: 2282 (msec) n: 100000000 [25003993 24997380 24993591 25005036]
no memory
avp@avp-ubu1:hashcode$ ./a.out 100000000
shift: 1871 (msec) n: 100000000 [25003993 24997380 24993591 25005036]
if: 2398 (msec) n: 100000000 [25003993 24997380 24993591 25005036]
no memory
avp@avp-ubu1:hashcode$ ./a.out 10000000
shift: 197 (msec) n: 10000000 [2500381 2500853 2498320 2500446]
if: 221 (msec) n: 10000000 [2500381 2500853 2498320 2500446]
=== in mem ===
shift place: 143 (msec) n: 100000000
shift vars: 222 (msec) n: 100000000
if: 513 (msec) n: 100000000
sum = 14998834
avp@avp-ubu1:hashcode$ ./a.out 10000000
shift: 281 (msec) n: 10000000 [2500381 2500853 2498320 2500446]
if: 227 (msec) n: 10000000 [2500381 2500853 2498320 2500446]
=== in mem ===
shift place: 143 (msec) n: 100000000
shift vars: 217 (msec) n: 100000000
if: 513 (msec) n: 100000000
sum = 14998834
avp@avp-ubu1:hashcode$ ./a.out 10000000
shift: 204 (msec) n: 10000000 [2500381 2500853 2498320 2500446]
if: 220 (msec) n: 10000000 [2500381 2500853 2498320 2500446]
=== in mem ===
shift place: 140 (msec) n: 100000000
shift vars: 216 (msec) n: 100000000
if: 517 (msec) n: 100000000
sum = 14998834
avp@avp-ubu1:hashcode$

#endif