¿Existe alguna forma de acelerar la recursividad recordando nodos secundarios?

Question

Por ejemplo, mire el código que calcula el número de Fibonacci N-th:

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 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 recursividad?

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

Answer 1

Sí, tu idea es correcta.Se llama programación dinámica.Suele ser una compensación común en el tiempo de ejecución de la memoria.

En el caso de Fibo, ni siquiera necesitas 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.Busque en Wikipedia o mire el código del otro cartel para obtener esta respuesta.Esas respuestas son lineales en el tiempo y la 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 iniciar sesión 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 (mucho más rápido), aquí hay un método:Si conoce u(n), u(n-1), puede calcular u(n+1), u(n) 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 |

Calcular 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 puedes simplemente diagonalizarlo (no es demasiado difícil), encontrarás el número de oro y su conjugado en su valor propio, y el resultado te dará una fórmula matemática EXACTA para u(n).Contiene potencias de esos valores propios, por lo que la complejidad seguirá siendo logarítmica.

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

@John:No creo que tenga nada que ver con el hachís.

@Juan2:Un mapa es un poco general ¿no crees?Para el caso de Fibonacci, todas las claves son contiguas para que un vector sea apropiado; una vez más, hay formas mucho más rápidas de calcular la secuencia de Fibo; consulte mi ejemplo de código allí.

Answer 2

Esto se llama memorización y hay un artículo muy bueno sobre memorización. Mateo Podwysocki publicado estos días.Utiliza Fibonacci para ejemplificarlo.Y también muestra el código en C#.Léelo aquí.

Answer 3

Si estás usando C# y puedes usar PostSharp, aquí hay un aspecto de memorización simple 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 un ejemplo de implementación de Fibonacci usándolo:

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

Answer 4

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í.Eso 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 números enteros consecutivos como lo son en este caso), pero los mapas son convenientes de usar en general.

Answer 5

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

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

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 para convertir la recursividad en recursión de cola y luego hacer un bucle.Para obtener más detalles, consulte, por ejemplo, este conferencia (ppt).

Answer 6

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

Answer 7

El almacenamiento en caché suele ser una buena idea para este tipo de cosas.Dado que los números de Fibonacci son constantes, puedes almacenar en caché el resultado una vez que lo hayas 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 da como resultado 3 búsquedas; sin embargo, esto debería ilustrar la idea general.

Answer 8

¿Es este un ejemplo elegido deliberadamente?(p.ej.un caso extremo que quieres probar)

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

Al observar este caso específico, podría tener algo como:

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 ]

[Otra edición más:la versión de Haskell (porque soy masoquista o algo así)

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

]

Answer 9

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

@Pablo

Gracias por la info.No lo sabía.Desde el enlace de wikipedia Mencionaste:

Esta técnica de ahorro de valores que ya se han calculado se llama memoización

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

Answer 10

@ESRogs:

std::map la búsqueda es oh(registro norte) lo que lo hace 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];
}

Answer 11

Otros han respondido bien y con precisión a tu pregunta: estás buscando memorización.

Lenguajes de programación con optimización de llamadas de cola (en su mayoría lenguajes funcionales) pueden hacer ciertos casos de recursividad sin desbordamiento de pila.No se aplica directamente a su definición de Fibonacci, aunque existen trucos.

La redacción de tu 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 reconstruyéndolos cuando sea necesario.Sólo es realmente útil en unos pocos casos.Si su algoritmo solo se basa condicionalmente en el contexto en lugar del retorno, y/o está optimizando la memoria, no la velocidad.

Answer 12

Mathematica tiene una forma particularmente hábil de memorizar, 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 todo.Almacena en caché (memoriza) fib[0] y fib[1] desde el principio 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 utiliza una definición más específica antes de una definición más general.

Answer 13

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

Answer 14

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).

¿En realidad?¿Qué computadora estás usando?Tarda mucho en 44, pero la pila no se desborda.De hecho, obtendrá un valor mayor que el que puede contener un número entero (~4 mil millones sin signo, ~2 mil millones con signo) antes de que la pila se desborde (Fibbonaci(46)).

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

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]);
    }
}

Answer 15

Si estás usando un lenguaje con funciones de primera clase como Scheme, puedes agregar memorización 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 utiliza esa función.Esto ahora tiene un tiempo de ejecución O(n) (a diferencia de O(2^n) para el algoritmo sin memorización).

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

Answer 16

Como han indicado otros carteles, memorización es una forma estándar de intercambiar memoria por velocidad, aquí hay un pseudocó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 en

 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]

Answer 17

Por cierto, Perl tiene un memorizar módulo que hace esto para cualquier función en su 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 debes hacer es iniciar tu programa con

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

Answer 18

@lassevk:

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

1. Un parámetro opcional para especificar un método estático o miembro que se utiliza para generar la clave para la memoria caché.
2. Una forma opcional de cambiar el objeto de la caché para poder utilizar una caché respaldada por un disco o 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 intentar descubrirlo.

(Fuera de contexto:Estaba intentando publicar esto como un comentario, pero no me di cuenta de que los comentarios tienen una longitud permitida tan corta, por lo que esto realmente no encaja como una "respuesta")