1votos

Simplicidad y eficiencia en JavaScript

por josejuan hace 6 años

Ya que he comentado lo de javascript, aquí va lazy mediante cierres.

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
function k(n) {return function() {return n}} 
function f(x, y, z) { 
    var X = x(), Y = y(); 
    if(X <= Y) 
        return Y; 
    var x = k(X), y = k(Y); 
    return f( 
        function() {return f(k(X - 1), y, z)}, 
        function() {return f(k(Y - 1), z, x)}, 
        function() {return f(k(z() - 1), x, y)} 
    ); 
 
var n = 5000; 
console.log(f(k(n), k(0), k(n + 1))); 
4 comentarios
0votos

Escrito por jneira hace 6 años

Un par de dudas:
  • La linea "var x = k(X), y = k(Y);" podria quitarse sin afectar de ninguna manera negativa a la funcion ¿no?
  • He observado que en los parametros has usado una funcion anonima en lugar de k siendo que en principio parecen hacer lo mismo. Sin embargo al cambiarlas por la llamada a k lanza el stackoverflow antes (con 5000 por ejemplo).
1votos

Escrito por josejuan hace 6 años

1. depende de lo que pongas, pero el argumento 'x' (igualmente con 'y') podría tener múltiples niveles de recursión, al redefinirla a la "función constante", me aseguro que únicamente tienen un nivel (como total siempre se evalúan). Fíjate en "f(k(X - 1)..." si tú dejaras "f(k(x() - 1)..." estás añadiendo múltiples veces la evaluación de x(). Dejando X e Y tenemos cacheado ese cómputo (pero luego hay que meter en k para que sean funciones, claro).

2. no hacen lo mismo, precisamente el lazy se consigue así, si usas k, estás evaluando en el momento, pues k es "la función constante", la función anónima en cada argumento, crea el contexto de cada nivel de recursión sin evaluarlo (hasta que sea llamada).
0votos

Escrito por josejuan hace 6 años

El [1] no está bien explicado, pero fíjate que en "return f(" el primer argumento es una función que a su vez llama a... si no cacheas el resultado, esa función se evalúa varias veces (pero sólo hasta llegar a un nivel que lo redefina como "k(X - 1)" o "k(Y - 1)" o "k(z() - 1)" ).

De todos modos, comentando esa redefinición, ¡más rápido!, pero yo lo atribuyo a que el coste de crear esas dos funciones constantes en cada nivel es mayor que evaluar la función a 2 o 3 niveles (que es el que se produce como mucho al "bailar" los argumentos).
0votos

Escrito por jneira hace 6 años

2. joe, claro, en que esaba yo pensando

Comenta la solución

Tienes que identificarte para poder publicar tu comentario.