0votos

Sucesion Aritmetica en C

por josejuan hace 4 años

La versión anterior paralelada en mi máquina 0,15 segundos.

Determinar cuantos números de un Conjunto están en sucesión aritmética.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
#include <stdio.h> 
#include <stdlib.h> 
#include <time.h> 
#include <sys/time.h> 
#include <omp.h> 
 
int cmpfunc(const void * a, const void * b) { 
   return ( *(int*)a - *(int*)b ); 
 
int main(int argc, char **argv) { 
 
  srand((unsigned) time(NULL)); 
 
  int n = atoi(argv[1]); // nº de nºs 
  int h = atoi(argv[2]); // homogeneidad (dominio nºs) 
 
  int *m = (int *) malloc(sizeof(int) * n); 
 
    int i; 
    for(i = 0; i < n; i++) 
      m[i] = rand() % h; 
 
  // ordenamos O(n log n) 
  qsort(m, n, sizeof(int), cmpfunc); 
 
  struct timespec t1, t2; 
  clock_gettime(CLOCK_MONOTONIC,  &t1); 
 
  int counter = 0; 
#pragma omp parallel 
  { // para cada par búsqueda dicotómica candidato O(n^2 log n) 
    int a, b; 
    int th  = omp_get_thread_num();   
    int nth = omp_get_num_threads();   
    printf("Thread %i / %i\n", th, nth);   
    for(a = th; a < n - 3; a += nth) { 
      for(b = a + 1; b < n - 2; b++) { 
        int ba = m[b] + m[a]; 
        int u = b + 1, v = n - 1; 
        while(u <= v) { 
          int w = (u + v) >> 1; 
          if(m[w] == ba) break; 
          if(m[w] <  ba) u = w + 1; 
          if(m[w] >  ba) v = w - 1; 
        if(u <= v) 
          counter++; // espero que atómica ;P 
  printf("%i tripletes\n", counter); 
 
  clock_gettime(CLOCK_MONOTONIC,  &t2); 
  double t = (t2.tv_sec - t1.tv_sec) + (double) (t2.tv_nsec - t1.tv_nsec) * 1e-9; 
  fprintf(stderr, "Seconds: %f\n", t); 
 
  return 0; 
 
/* 
 
[josejuan@centella Solveet]$ cat /proc/cpuinfo | grep -i '\(cpu M\|model name\)' | head -n 2 
model name      : AMD Phenom(tm) II X6 1045T Processor 
cpu MHz         : 2700.000 
[josejuan@centella Solveet]$ export OMP_NUM_THREADS=14 
[josejuan@centella Solveet]$ gcc -O3 -fopenmp 3arit.c && ./a.out 7000 10000000 
Thread 1 / 14 
Thread 5 / 14 
Thread 0 / 14 
Thread 6 / 14 
Thread 2 / 14 
Thread 7 / 14 
Thread 8 / 14 
Thread 9 / 14 
Thread 10 / 14 
Thread 11 / 14 
Thread 3 / 14 
Thread 12 / 14 
Thread 13 / 14 
Thread 4 / 14 
9888 tripletes 
Seconds: 0.153841 
 
 
*/ 

Comenta la solución

Tienes que identificarte para poder publicar tu comentario.