0votos

Simplicidad y eficiencia en C

por josejuan hace 6 años

Me ha costado un poco porque hace mucho que no programo en C, pero se puede implementar fácilmente lazy en cualquier lenguaje. He elegido C porque probablemente sea de los más complicados (y aún así no me parece largo). Por ejemplo, en javascript es directo si usamos clausuras. El rendimiento casi TRIPLICA al de haskell (se ha dicho que la eficiencia era importante).

Definir simple y eficientemente la función f tal que f(x,y,z) = y, si x <= y; f(x,y,z) = f(f(x-1,y,z),f(y-1,z,x),f(z-1,x,y)), en caso contrario.

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
#include <stdio.h> 
#include <stdlib.h> 
 
typedef struct _arg arg; 
 
typedef struct _args { 
    arg *x; 
    arg *y; 
    arg *z; 
} args; 
 
typedef struct _arg { 
    char computed; 
    long (*compute)(args *); 
    args *params; 
} arg; 
 
long get_arg(arg *p); 
 
args *do_args(arg *x, arg *y, arg *z) { 
    args *a = (args *) malloc(sizeof(args)); 
    a->x = x; 
    a->y = y; 
    a->z = z; 
    return a; 
 
arg *do_arg(long (*func)(args *), args *p) { 
    arg *a = (arg *) malloc(sizeof(arg)); 
    a->computed = 0; 
    a->compute = func; 
    a->params = p; 
    return a; 
 
long c(args *p) { 
    return (long) p->x; 
 
long s(args *p) { 
    return get_arg(p->x) - 1; 
 
long get_arg(arg *p) { 
    if(p->computed) 
        return (long) p->params; 
    long r = p->compute(p->params); 
    p->computed = 1; 
    p->params = (args *) r; 
    return r; 
 
#define DO_S(A) do_arg(s, do_args(A, NULL, NULL)) 
#define DO_C(A) do_arg(c, do_args((arg *) (A), NULL, NULL)) 
 
// la definición de "f", salvo las transformaciones "a lazy" no está alterada en absoluto. 
long f(args *p) { 
    long _x = get_arg(p->x); 
    long _y = get_arg(p->y); 
    if(_x <= _y) return _y; 
    return f(do_args( 
        do_arg(f, do_args(DO_C(_x - 1), DO_C(_y), p->z )), 
        do_arg(f, do_args(DO_C(_y - 1), p->z, DO_C(_x))), 
        do_arg(f, do_args(DO_S(p->z), DO_C(_x), DO_C(_y))) 
    )); 
 
int main(int argc, char **argv) { 
    long n = atoi(argv[1]); 
    printf("%i\n", (int) f(do_args(DO_C(n), DO_C(0), DO_C(n + 1)))); 
    return 0; 
1 comentario
0votos

Escrito por josejuan hace 6 años

Me olvidé de la ejecución (en la misma máquina que haskell)

$ /usr/bin/time -f "Mem: %M, Time: %E" ./a.out 600000
600001
Mem: 441132, Time: 0:01.01

Comenta la solución

Tienes que identificarte para poder publicar tu comentario.