performance - sintaxis - recursividad java

¿Hay alguna manera de acelerar la recursión recordando los nodos secundarios? (18)

El problema con este código es que generará un error de desbordamiento de pila para cualquier número mayor que 15 (en la mayoría de las computadoras).

De Verdad? ¿Qué computadora estás usando? Le está tomando mucho tiempo a los 44, pero la pila no se está desbordando. De hecho, obtendrá un valor mayor que el que puede contener un entero (~ 4 mil millones sin signo, ~ 2 mil millones con signo) antes de que la pila vaya a sobre flujo (Fibbonaci (46)).

Sin embargo, esto funcionaría para lo que quieras hacer (se ejecuta rápidamente)

class Program { public static readonly Dictionary<int,int> Items = new Dictionary<int,int>(); static void Main(string[] args) { Console.WriteLine(Fibbonacci(46).ToString()); Console.ReadLine(); } public static int Fibbonacci(int number) { if (number == 1 || number == 0) { return 1; } var minus2 = number - 2; var minus1 = number - 1; if (!Items.ContainsKey(minus2)) { Items.Add(minus2, Fibbonacci(minus2)); } if (!Items.ContainsKey(minus1)) { Items.Add(minus1, Fibbonacci(minus1)); } return (Items[minus2] + Items[minus1]); } }

Por ejemplo, observe el código que calcula el n-ésimo número de Fibonacci:

fib(int n) { if(n==0 || n==1) return 1; return fib(n-1) + fib(n-2); }

El problema con este código es que generará un error de desbordamiento de pila para cualquier número mayor que 15 (en la mayoría de las computadoras).

Supongamos que estamos calculando fib (10). En este proceso, digamos que fib (5) se calcula muchas veces. ¿Hay alguna forma de almacenar esto en la memoria para una recuperación rápida y así aumentar la velocidad de recursión?

Estoy buscando una técnica genérica que pueda usarse en casi todos los problemas.

¿Es este un ejemplo elegido deliberadamente? (por ejemplo, un caso extremo que quiere probar)

Como actualmente es O (1.6 ^ n), solo quiero asegurarme de que estás buscando respuestas para manejar el caso general de este problema (valores de almacenamiento en caché, etc.) y no solo de escribir accidentalmente código deficiente: D

En cuanto a este caso específico, podría tener algo similar a:

var cache = []; function fib(n) { if (n < 2) return 1; if (cache.length > n) return cache[n]; var result = fib(n - 2) + fib(n - 1); cache[n] = result; return result; }

Que degenera a O (n) en el peor de los casos: D

[Editar: * no es igual a +: D]

[Sin embargo, otra edición: la versión de Haskell (porque soy un masoquista o algo así)

fibs = 1:1:(zipWith (+) fibs (tail fibs)) fib n = fibs !! n

]

¿Qué lenguaje es este? No desborda nada en c ... Además, puedes intentar crear una tabla de búsqueda en el montón, o usar un mapa

@ESRogs:

std::map searchup es O (log n ) lo que hace que sea lento aquí. Mejor usa un vector.

vector<unsigned int> fib_cache; fib_cache.push_back(1); fib_cache.push_back(1); unsigned int fib(unsigned int n) { if (fib_cache.size() <= n) fib_cache.push_back(fib(n - 1) + fib(n - 2)); return fib_cache[n]; }

De acuerdo con wikipedia Fib (0) debería ser 0 pero no importa.

Aquí hay una solución simple de C # para ciclo:

ulong Fib(int n) { ulong fib = 1; // value of fib(i) ulong fib1 = 1; // value of fib(i-1) ulong fib2 = 0; // value of fib(i-2) for (int i = 0; i < n; i++) { fib = fib1 + fib2; fib2 = fib1; fib1 = fib; } return fib; }

Es un truco bastante común convertir la recursividad a la recursividad de la cola y luego al bucle. Para más detalles, ver por ejemplo esta conferencia (ppt).

Esto se llama memorización y hay un artículo muy bueno acerca de las memorias que Matthew Podwysocki publicó estos días. Utiliza Fibonacci para ejemplificarlo. Y muestra el código en C # también. Léelo aquí .

Intente usar un mapa, n es la clave y su correspondiente número de Fibonacci es el valor.

@Pablo

Gracias por la info. No lo sabía. Del enlace de Wikipedia que mencionaste:

Esta técnica de guardar valores que ya han sido calculados se llama memorización

Sí, ya miré el código (+1). :)

Sí, tu idea es correcta. Esto se llama programación dinámica . Por lo general, es un intercambio de tiempo de ejecución de memoria común.

En el caso de fibo, ni siquiera necesita almacenar todo en caché:

[editar] El autor de la pregunta parece estar buscando un método general para almacenar en caché en lugar de un método para calcular Fibonacci. Busca en wikipedia o mira el código del otro póster para obtener esta respuesta. Esas respuestas son lineales en tiempo y memoria.

** Aquí hay un algoritmo de tiempo lineal O (n), constante en la memoria **

in OCaml: let rec fibo n = let rec aux = fun | 0 -> (1,1) | n -> let (cur, prec) = aux (n-1) in (cur+prec, cur) let (cur,prec) = aux n in prec;; in C++: int fibo(int n) { if (n == 0 ) return 1; if (n == 1 ) return 1; int p = fibo(0); int c = fibo(1); int buff = 0; for (int i=1; i < n; ++i) { buff = c; c = p+c; p = buff; }; return c; };

Esto se realiza en tiempo lineal. ¡Pero el registro es realmente posible! El programa de Roo también es lineal, pero mucho más lento, y usa memoria.

Aquí está el algoritmo de registro O (log (n))

Ahora, para el algoritmo de tiempo de registro (camino mucho más rápido), aquí hay un método: si sabes u (n), u (n-1), calculando u (n + 1), u (n) se puede hacer aplicando una matriz:

| u(n+1) | = | 1 1 | | u(n) | | u(n) | | 1 0 | | u(n-1) |

Para que tengas:

| u(n) | = | 1 1 |^(n-1) | u(1) | = | 1 1 |^(n-1) | 1 | | u(n-1) | | 1 0 | | u(0) | | 1 0 | | 1 |

La computación de la exponencial de la matriz tiene una complejidad logarítmica. Simplemente implemente recursivamente la idea:

M^(0) = Id M^(2p+1) = (M^2p) * M M^(2p) = (M^p) * (M^p) // of course don''t compute M^p twice here.

También puede diagonalizarlo (no es difícil), encontrará el número de oro y su conjugado en su valor propio, y el resultado le dará una fórmula matemática EXACTA para usted (n). Contiene los poderes de esos valores propios, de modo que la complejidad seguirá siendo logarítmica.

Fibo a menudo se toma como un ejemplo para ilustrar la programación dinámica, pero como ve, no es realmente pertinente.

@John: No creo que tenga nada que ver con hacer con hash.

@ John2: Un mapa es un poco general ¿no crees? Para el caso de Fibonacci, todas las teclas son contiguas, por lo que un vector es apropiado, una vez más hay maneras mucho más rápidas de calcular la secuencia de fibo, ver la muestra de mi código de allí.

Si está usando C # y puede usar PostSharp , aquí hay un aspecto simple de memorización para su código:

[Serializable] public class MemoizeAttribute : PostSharp.Laos.OnMethodBoundaryAspect, IEqualityComparer<Object[]> { private Dictionary<Object[], Object> _Cache; public MemoizeAttribute() { _Cache = new Dictionary<object[], object>(this); } public override void OnEntry(PostSharp.Laos.MethodExecutionEventArgs eventArgs) { Object[] arguments = eventArgs.GetReadOnlyArgumentArray(); if (_Cache.ContainsKey(arguments)) { eventArgs.ReturnValue = _Cache[arguments]; eventArgs.FlowBehavior = FlowBehavior.Return; } } public override void OnExit(MethodExecutionEventArgs eventArgs) { if (eventArgs.Exception != null) return; _Cache[eventArgs.GetReadOnlyArgumentArray()] = eventArgs.ReturnValue; } #region IEqualityComparer<object[]> Members public bool Equals(object[] x, object[] y) { if (Object.ReferenceEquals(x, y)) return true; if (x == null || y == null) return false; if (x.Length != y.Length) return false; for (Int32 index = 0, len = x.Length; index < len; index++) if (Comparer.Default.Compare(x[index], y[index]) != 0) return false; return true; } public int GetHashCode(object[] obj) { Int32 hash = 23; foreach (Object o in obj) { hash *= 37; if (o != null) hash += o.GetHashCode(); } return hash; } #endregion }

Aquí hay una implementación de ejemplo de Fibonacci que lo usa:

[Memoize] private Int32 Fibonacci(Int32 n) { if (n <= 1) return 1; else return Fibonacci(n - 2) + Fibonacci(n - 1); }

Si está utilizando un idioma con funciones de primera clase como Scheme, puede agregar memoria sin cambiar el algoritmo inicial:

(define (memoize fn) (letrec ((get (lambda (query) ''(#f))) (set (lambda (query value) (let ((old-get get)) (set! get (lambda (q) (if (equal? q query) (cons #t value) (old-get q)))))))) (lambda args (let ((val (get args))) (if (car val) (cdr val) (let ((ret (apply fn args))) (set args ret) ret)))))) (define fib (memoize (lambda (x) (if (< x 2) x (+ (fib (- x 1)) (fib (- x 2)))))))

El primer bloque proporciona una función de memorización y el segundo bloque es la secuencia de fibonacci que usa esa instalación. Esto ahora tiene un tiempo de ejecución O (n) (en oposición a O (2 ^ n) para el algoritmo sin memoria).

Nota: la función de memorización proporcionada utiliza una cadena de cierres para buscar invocaciones previas. En el peor de los casos, esto puede ser O (n). En este caso, sin embargo, los valores deseados están siempre en la parte superior de la cadena, lo que garantiza la búsqueda O (1).

el almacenamiento en caché generalmente es una buena idea para este tipo de cosas. Dado que los números de Fibonacci son constantes, puede almacenar en caché el resultado una vez que lo haya calculado. Un ejemplo rápido de c / pseudocódigo

class fibstorage { bool has-result(int n) { return fibresults.contains(n); } int get-result(int n) { return fibresult.find(n).value; } void add-result(int n, int v) { fibresults.add(n,v); } map<int, int> fibresults; } fib(int n ) { if(n==0 || n==1) return 1; if (fibstorage.has-result(n)) { return fibstorage.get-result(n-1); } return ( (fibstorage.has-result(n-1) ? fibstorage.get-result(n-1) : fib(n-1) ) + (fibstorage.has-result(n-2) ? fibstorage.get-result(n-2) : fib(n-2) ) ); } calcfib(n) { v = fib(n); fibstorage.add-result(n,v); }

Esto sería bastante lento, ya que cada recursividad resulta en 3 búsquedas, sin embargo, esto debería ilustrar la idea general

Memorización rápida y sucia en C ++:

Cualquier método recursivo type1 foo(type2 bar) { ... } se memoriza fácilmente con map<type2, type1> M

// your original method int fib(int n) { if(n==0 || n==1) return 1; return fib(n-1) + fib(n-2); } // with memoization map<int, int> M = map<int, int>(); int fib(int n) { if(n==0 || n==1) return 1; // only compute the value for fib(n) if we haven''t before if(M.count(n) == 0) M[n] = fib(n-1) + fib(n-2); return M[n]; }

EDITAR: @Konrad Rudolph
Konrad señala que std :: map no es la estructura de datos más rápida que podríamos usar aquí. Es cierto, un vector<something> debería ser más rápido que un map<int, something> (aunque podría requerir más memoria si las entradas a las llamadas recursivas de la función no fueran enteros consecutivos como lo son en este caso), pero mapas son convenientes para usar en general.

Otros han respondido bien y con precisión a su pregunta: usted está buscando la memorización.

Los lenguajes de programación con optimización de cola de llamada (principalmente idiomas funcionales) pueden hacer ciertos casos de recursión sin desbordamiento de pila. No se aplica directamente a su definición de Fibonacci, aunque hay trucos ...

El fraseo de su pregunta me hizo pensar en una idea interesante. Evitar el desbordamiento de la pila de una función recursiva pura almacenando solo un subconjunto de los marcos de la pila y reconstruyendo cuando sea necesario. Solo realmente útil en algunos casos. Si su algoritmo solo depende condicionalmente del contexto en lugar de la devolución, y / o está optimizando la memoria, no la velocidad.

Como han indicado otros carteles, la memorización es una forma estándar de cambiar la velocidad de la memoria, aquí hay un pseudo código para implementar la memorización de cualquier función (siempre que la función no tenga efectos secundarios):

Código de función inicial:

function (parameters) body (with recursive calls to calculate result) return result

Esto debería transformarse para

function (parameters) key = serialized parameters to string if (cache[key] does not exist) { body (with recursive calls to calculate result) cache[key] = result } return cache[key]

Mathematica tiene una manera particularmente ingeniosa de hacer memoizaciones, basándose en el hecho de que los hash y las llamadas a funciones usan la misma sintaxis:

fib[0] = 1; fib[1] = 1; fib[n_] := fib[n] = fib[n-1] + fib[n-2]

Eso es. Se almacena en caché (memoizes) fib [0] y fib [1] fuera del bate y almacena en caché el resto según sea necesario. Las reglas para las llamadas a funciones de coincidencia de patrones son tales que siempre usa una definición más específica antes de una definición más general.

Otro recurso excelente para los programadores de C # para la recursividad, parciales, currying, memorización, y su tipo, es el blog de Wes Dyer, aunque no ha publicado en un tiempo. Explica bien la memoria, con ejemplos de código sólido aquí: http://blogs.msdn.com/wesdyer/archive/2007/01/26/function-memoization.aspx

Por cierto, Perl tiene un módulo de memoria que hace esto para cualquier función en el código que especifique.

# Compute Fibonacci numbers sub fib { my $n = shift; return $n if $n < 2; fib($n-1) + fib($n-2); }

Para memorizar esta función, todo lo que hace es comenzar su programa con

use Memoize; memoize(''fib''); # Rest of the fib function just like the original version. # Now fib is automagically much faster ;-)

@lassevk:

Esto es asombroso, exactamente en lo que había estado pensando en mi cabeza después de leer acerca de la memorización en Higher Order Perl . Dos cosas que creo que serían adiciones útiles:

Un parámetro opcional para especificar un método estático o miembro que se usa para generar la clave de la memoria caché.
Una forma opcional de cambiar el objeto de caché para que pueda usar un disco o caché respaldado por una base de datos.

No estoy seguro de cómo hacer este tipo de cosas con los atributos (o si son posibles con este tipo de implementación), pero planeo tratar de averiguarlo.

(Fuera de tema: estaba tratando de publicar esto como un comentario, pero no me di cuenta de que los comentarios tienen una longitud tan corta permitida, así que esto no encaja realmente como una ''respuesta'')