Esiste un modo per accelerare la ricorsione ricordando i nodi figlio?

Question

Per esempio Guarda il codice che calcola l'n-esimo numero di Fibonacci:

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

Il problema con questo codice è che genererà un errore di overflow dello stack per qualsiasi numero maggiore di 15 (nella maggior parte dei computer).

Supponiamo di calcolare fib(10).In questo processo, diciamo che fib(5) viene calcolato molte volte.Esiste un modo per archiviarlo in memoria per un recupero rapido e quindi aumentare la velocità di ricorsione?

Sto cercando una tecnica generica che possa essere utilizzata in quasi tutti i problemi.

Answer 1

Sì, la tua intuizione è corretta.Questo è chiamato programmazione dinamica.Di solito si tratta di un compromesso comune in termini di runtime della memoria.

Nel caso di fibo, non è nemmeno necessario memorizzare nella cache tutto:

[modifica] L'autore della domanda sembra essere alla ricerca di un metodo generale per memorizzare nella cache piuttosto che un metodo per calcolare Fibonacci.Cerca su Wikipedia o guarda il codice dell'altro utente per ottenere questa risposta.Queste risposte sono lineari nel tempo e nella memoria.

**Ecco un algoritmo in tempo lineare O(n), costante in 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;
};

Questo viene eseguito in tempo lineare.Ma il log è effettivamente possibile !!!Anche il programma di Roo è lineare, ma molto più lento e utilizza memoria.

Ecco l'algoritmo di log O(log(n))

Ora per l'algoritmo log-time (molto molto più veloce), ecco un metodo:Se conosci u(n), u(n-1), il calcolo di u(n+1), u(n) può essere eseguito applicando una matrice:

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

In modo che tu abbia:

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

Il calcolo dell'esponenziale della matrice ha una complessità logaritmica.Basta implementare ricorsivamente l'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.

Puoi anche semplicemente diagonalizzarlo (non troppo difficile), troverai il numero d'oro e il suo coniugato nel suo autovalore e il risultato ti darà una formula matematica ESATTA per u(n).Contiene potenze di quegli autovalori, quindi la complessità sarà ancora logaritmica.

Fibo viene spesso preso come esempio per illustrare la Programmazione Dinamica, ma come vedi non è realmente pertinente.

@John:Non penso che abbia nulla a che fare con l'hashish.

@Giovanni2:Una mappa è un po' generica, non credi?Nel caso di Fibonacci, tutte le chiavi sono contigue in modo che un vettore sia appropriato, ancora una volta ci sono modi molto più veloci per calcolare la sequenza fibo, vedi il mio esempio di codice laggiù.

Answer 2

Questa si chiama memorizzazione e c'è un ottimo articolo sulla memorizzazione Matteo Podwysocki pubblicato in questi giorni.Usa Fibonacci per esemplificarlo.E mostra anche il codice in C#.Leggilo Qui.

Answer 3

Se stai usando C# e puoi usare PostSharp, ecco un semplice aspetto di memorizzazione per il tuo codice:

[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
}

Ecco un esempio di implementazione di Fibonacci che lo utilizza:

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

Answer 4

Memoizzazione rapida e sporca in C++:

Qualsiasi metodo ricorsivo type1 foo(type2 bar) { ... } è facilmente memorizzabile 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];
}

MODIFICARE:@Konrad Rodolfo
Konrad sottolinea che std::map non è la struttura dati più veloce che potremmo usare qui.È vero, a vector<something> dovrebbe essere più veloce di a map<int, something> (anche se potrebbe richiedere più memoria se gli input per le chiamate ricorsive della funzione non fossero interi consecutivi come in questo caso), ma le mappe sono convenienti da usare in generale.

Answer 5

Secondo Wikipedia Fib(0) dovrebbe essere 0 ma non ha importanza.

Ecco una semplice soluzione 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;
}

È un trucco abbastanza comune convertire la ricorsione ricorsione della coda e poi eseguire il loop.Per maggiori dettagli vedere ad esempio questo conferenza (pp).

Answer 6

Che lingua è questa?Non trabocca nulla in c...Inoltre, puoi provare a creare una tabella di ricerca nell'heap o utilizzare una mappa

Answer 7

la memorizzazione nella cache è generalmente una buona idea per questo genere di cose.Poiché i numeri di Fibonacci sono costanti, puoi memorizzare nella cache il risultato una volta calcolato.Un rapido esempio di c/pseudocodice

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

Ciò sarebbe piuttosto lento, poiché ogni ricorsione risulta in 3 ricerche, tuttavia ciò dovrebbe illustrare l'idea generale

Answer 8

Si tratta di un esempio scelto deliberatamente?(per esempio.un caso estremo che vuoi testare)

Dato che attualmente è O (1.6 ^ n), voglio solo assicurarmi che tu stia solo cercando risposte sulla gestione del caso generale di questo problema (caching dei valori, ecc.) e non solo scrivendo accidentalmente codice scadente: D

Guardando questo caso specifico potresti avere qualcosa sulla falsariga di:

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

Che degenera in O(n) nel caso peggiore :D

[Modificare:*non è uguale a + :D]

[Ancora un'altra modifica:la versione Haskell (perché sono masochista o qualcosa del genere)

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

]

Answer 9

Prova a utilizzare una mappa, n è la chiave e il numero di Fibonacci corrispondente è il valore.

@Paolo

Grazie per le informazioni.Non lo sapevo.Dal Collegamento aWikipedia hai nominato:

Questa tecnica di salvataggio dei valori che sono già stati calcolati si chiama Memorizzazione

Sì, ho già guardato il codice (+1).:)

Answer 10

@ESRogs:

std::map la ricerca è O(tronco d'albero N) che lo rende lento qui.Meglio usare un vettore.

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

Altri hanno risposto bene e accuratamente alla tua domanda: stai cercando la memorizzazione.

Linguaggi di programmazione con ottimizzazione delle chiamate in coda (per lo più linguaggi funzionali) possono eseguire determinati casi di ricorsione senza overflow dello stack.Non si applica direttamente alla tua definizione di Fibonacci, anche se ci sono dei trucchi...

La formulazione della tua domanda mi ha fatto venire in mente un'idea interessante..Evitare l'overflow dello stack di una funzione ricorsiva pura memorizzando solo un sottoinsieme degli stack frame e ricostruendolo quando necessario.Davvero utile solo in pochi casi.Se il tuo algoritmo si basa solo in modo condizionale sul contesto anziché sul ritorno e/o stai ottimizzando per la memoria e non per la velocità.

Answer 12

Mathematica ha un modo particolarmente ingegnoso per eseguire la memorizzazione, basandosi sul fatto che gli hash e le chiamate di funzione utilizzano la stessa sintassi:

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

Questo è tutto.Memorizza nella cache (memoizza) fib[0] e fib[1] fin dall'inizio e memorizza nella cache il resto secondo necessità.Le regole per le chiamate alle funzioni di corrispondenza dei modelli sono tali che utilizza sempre una definizione più specifica prima di una definizione più generale.

Answer 13

Un'altra risorsa eccellente per i programmatori C# per ricorsione, partial, currying, memorizzazione e simili è il blog di Wes Dyer, anche se non pubblica post da un po'.Spiega bene la memorizzazione, con solidi esempi di codice qui:http://blogs.msdn.com/wesdyer/archive/2007/01/26/function-memoization.aspx

Answer 14

Il problema con questo codice è che genererà un errore di overflow dello stack per qualsiasi numero maggiore di 15 (nella maggior parte dei computer).

Veramente?Che computer stai utilizzando?Ci vuole molto tempo a 44, ma lo stack non è traboccante.In effetti, otterrai un valore più grande di quello che un numero intero può contenere (~ 4 miliardi senza segno, ~ 2 miliardi con segno) prima che lo stack trabocchi (Fibbonaci(46)).

Questo funzionerebbe per quello che vuoi fare però (funziona velocemente)

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

Se stai utilizzando un linguaggio con funzioni di prima classe come Scheme, puoi aggiungere la memorizzazione senza modificare l'algoritmo iniziale:

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

Il primo blocco fornisce una funzionalità di memorizzazione e il secondo blocco è la sequenza di Fibonacci che utilizza tale funzionalità.Questo ora ha un runtime O(n) (al contrario di O(2^n) per l'algoritmo senza memorizzazione).

Nota:la funzione di memorizzazione fornita utilizza una catena di chiusure per cercare invocazioni precedenti.Nel peggiore dei casi può essere O(n).In questo caso, tuttavia, i valori desiderati sono sempre in cima alla catena, garantendo la ricerca O(1).

Answer 16

Come hanno indicato altri poster, memorizzazione è un modo standard per scambiare memoria con velocità, ecco uno pseudo codice per implementare la memorizzazione per qualsiasi funzione (a condizione che la funzione non abbia effetti collaterali):

Codice funzione iniziale:

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

Questo dovrebbe essere trasformato in

 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

A proposito, Perl ha un file memorizzare modulo che esegue questa operazione per qualsiasi funzione specificata nel codice.

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

Per memorizzare questa funzione è sufficiente avviare il programma

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

Answer 18

@lassevk:

È fantastico, esattamente quello a cui stavo pensando nella mia testa dopo aver letto della memorizzazione Perl di ordine superiore.Due cose che penso sarebbero utili aggiunte:

1. Un parametro facoltativo per specificare un metodo statico o membro utilizzato per generare la chiave per la cache.
2. Un modo facoltativo per modificare l'oggetto cache in modo da poter utilizzare una cache supportata da un disco o da un database.

Non sono sicuro di come fare questo genere di cose con gli attributi (o se siano possibili con questo tipo di implementazione), ma ho intenzione di provare a capirlo.

(Fuori tema:Stavo cercando di pubblicarlo come commento, ma non mi ero reso conto che i commenti hanno una lunghezza consentita così breve, quindi non si adatta davvero come "risposta")