0votos

Carrera de "¡Baja la escalera!" en C

por josejuan hace 5 años

Hay muchas oportunidades de optimización agresiva en este problema. Con un único procesador, prácticamente se dobla el nº de filas procesadas respecto la mejor versión anterior Haskell usando 8 cores. ¿Se podrá mejorar usando MP?.

Una variante que convierte al popular juguete en una carrera de la que debes calcular las mejores rutas de los corredores.

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
89
90
91
92
93
94
95
96
/* 
    Representaremos el árbol como un array 1D 
 
          3,0, 
         2,7,0, 
        4,5,8,9 
 
    Entonces, el índice (en base 0) del primer 
    número de la fila `r` (en base 0) si el 
    árbol tiene `w` corredores será 
 
        n w + n (n - 1) / 2 
 
*/ 
#include <stdio.h> 
#include <stdlib.h> 
#include <time.h> 
 
#define byte unsigned char 
 
#define IWR(w, r) ((r) * (w) + (((r) * ((r) - 1)) >> 1)) 
 
int * computeCosts( byte *pcosts // costes parciales 
                  , int w        // nº corredores (o fila inicial base 0) 
                  , int R        // max nº de fila (base 0) 
                  ) { 
    int i = IWR(w, R); // última posición en que se actualizó el coste 
    int j = i; // última posición de la que se tomó el coste 
    int *tcosts = (int *) malloc(sizeof(int) * i); 
    int iw = R + 1; // anchura de la fila en que se actualizan los costes 
    int u; 
    for(u = 0, --i; u < iw; u++, i--) 
        tcosts[i] = pcosts[i]; 
    while(--iw >= w) { 
        int b = tcosts[--j]; 
        for(u = 0; u < iw; u++, i--) { 
            int a = tcosts[--j]; 
            tcosts[i] = pcosts[i] + (a ^ ((b ^ a) & -(b < a))); 
            b = a; 
    return tcosts; 
 
byte * randomTree(int w, int R) { 
    int i, maxr = IWR(w, R); 
    byte *pcosts = (byte *) malloc(sizeof(byte) * maxr); 
    for(i = 0; i < maxr; i++) 
        pcosts[i] = rand() % 10; 
    return pcosts; 
 
void printTree(byte *pcosts, int w, int R) { 
    int r, i = 0, j = w; 
    for(r = 0; r < R; j += w + ++r) { 
        int s = R - r; 
        while(--s) putchar(' '); 
        while(i < j) printf("%i,", (int) pcosts[i++]); 
        putchar('\n'); 
void printCostsTree(int *tcosts, int w, int R) { 
    int r, i = 0, j = w; 
    for(r = 0; r < R; j += w + ++r) { 
        int s = R - r; 
        while(--s) printf("  "); 
        while(i < j) printf("% 4i,", (int) tcosts[i++]); 
        putchar('\n'); 
void printCostsRunners(int *tcosts, int w) { 
    int i; 
    for(i = 0; i < w; i++) printf("%i, ", tcosts[i]); 
 
int main(int argc, char **argv) { 
    srand(1); 
    int w = atoi(argv[1]), r = atoi(argv[2]); 
    byte *tree = randomTree(w, r); 
    //printTree(tree, w, r); 
    struct timespec ti, tf; 
    clock_gettime(CLOCK_PROCESS_CPUTIME_ID, &ti); 
    int *costs = computeCosts(tree, w, r); 
    clock_gettime(CLOCK_PROCESS_CPUTIME_ID, &tf); 
    printCostsRunners(costs, w); 
    //printCostsTree(costs, w, r); 
    printf("\n%lld ns\n", (int64_t) tf.tv_sec * 1000000000 + (int64_t) tf.tv_nsec - (int64_t) ti.tv_sec * 1000000000 + (int64_t) ti.tv_nsec); 
   return 0; 
 
/* 
$ time -f "%E, %M" ./tri 2 40000 
81187, 81188,  
3029344018 ns 
0:09.65, 3907040 
*/ 

Comenta la solución

Tienes que identificarte para poder publicar tu comentario.