Existe-t-il un moyen d'accélérer la récursivité en mémorisant les nœuds enfants ?

Question

Par exemple, consultez le code qui calcule le numéro N-Th Fibonacci:

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

Le problème avec ce code est qu'il générera une erreur de débordement de pile pour tout nombre supérieur à 15 (dans la plupart des ordinateurs).

Supposons que nous calculons fib(10).Dans ce processus, disons que fib(5) est calculé plusieurs fois.Existe-t-il un moyen de stocker cela en mémoire pour une récupération rapide et ainsi augmenter la vitesse de récursion ?

Je recherche une technique générique pouvant être utilisée dans presque tous les problèmes.

Answer 1

Oui, votre idée est correcte.C'est appelé programmation dynamique.Il s’agit généralement d’un compromis courant en matière d’exécution de la mémoire.

Dans le cas de Fibo, vous n'avez même pas besoin de tout mettre en cache :

Modifier] L'auteur de la question semble être à la recherche d'une méthode générale pour se cacher plutôt qu'une méthode pour calculer les fibonacci.Recherchez sur Wikipédia ou regardez le code de l'autre affiche pour obtenir cette réponse.Ces réponses sont linéaires dans le temps et la mémoire.

**Voici un algorithme en temps linéaire O(n), constant en mémoire **

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

Cela fonctionne en temps linéaire.Mais la journalisation est effectivement possible !!!Le programme de Roo est également linéaire, mais beaucoup plus lent et utilise de la mémoire.

Voici l'algorithme de journal O(log(n))

Maintenant, pour l'algorithme de journalisation (beaucoup plus rapide), voici une méthode :Si vous connaissez u(n), u(n-1), le calcul de u(n+1), u(n) peut être effectué en appliquant une matrice :

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

Pour que vous ayez :

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

Le calcul de l'exponentielle de la matrice a une complexité logarithmique.Implémentez simplement de manière récursive l’idée :

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

Vous pouvez aussi simplement le diagonaliser (pas trop difficile), vous trouverez le nombre d'or et son conjugué dans sa valeur propre, et le résultat vous donnera une formule mathématique EXACTE pour u(n).Il contient les puissances de ces valeurs propres, de sorte que la complexité sera toujours logarithmique.

Fibo est souvent pris comme exemple pour illustrer la Programmation Dynamique, mais comme vous le voyez, ce n'est pas vraiment pertinent.

@John:Je ne pense pas que cela ait quelque chose à voir avec le hasch.

@Jean2 :Une carte, c'est un peu général, vous ne trouvez pas ?Pour le cas de Fibonacci, toutes les clés sont contiguës pour qu'un vecteur soit approprié, encore une fois il existe des moyens beaucoup plus rapides de calculer la séquence fibo, voir mon exemple de code là-bas.

Answer 2

C'est ce qu'on appelle la mémorisation et il existe un très bon article sur la mémorisation. Matthieu Podwysocki posté ces jours-ci.Il utilise Fibonacci pour l'illustrer.Et affiche également le code en C#.Lis le ici.

Answer 3

Si vous utilisez C# et pouvez utiliser PostSharp, voici un aspect simple de mémorisation de votre code :

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

Voici un exemple d'implémentation de Fibonacci qui l'utilise :

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

Answer 4

Mémorisation rapide et sale en C++ :

Toute méthode récursive type1 foo(type2 bar) { ... } est facilement mémorisé avec 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];
}

MODIFIER:@Konrad Rudolph
Konrad souligne que std::map n'est pas la structure de données la plus rapide que nous pourrions utiliser ici.C'est vrai, un vector<something> devrait être plus rapide qu'un map<int, something> (bien que cela puisse nécessiter plus de mémoire si les entrées des appels récursifs de la fonction n'étaient pas des entiers consécutifs comme c'est le cas dans ce cas), mais les cartes sont généralement pratiques à utiliser.

Answer 5

Selon Wikipédia Fib(0) devrait être 0 mais cela n'a pas d'importance.

Voici une solution C# simple avec for cycle :

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

C'est une astuce assez courante pour convertir la récursion en récursivité de la queue puis faire une boucle.Pour plus de détails, voir par exemple ceci conférence (ppt).

Answer 6

Quelle langue est-ce?Ça ne déborde rien en c...Vous pouvez également essayer de créer une table de recherche sur le tas ou utiliser une carte

Answer 7

la mise en cache est généralement une bonne idée pour ce genre de chose.Puisque les nombres de Fibonacci sont constants, vous pouvez mettre le résultat en cache une fois que vous l'avez calculé.Un exemple rapide de c/pseudocode

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

Ce serait assez lent, car chaque récursion entraîne 3 recherches, mais cela devrait illustrer l'idée générale

Answer 8

Est-ce un exemple délibérément choisi ?(par exemple.un cas extrême que vous souhaitez tester)

Comme il est actuellement O(1.6^n), je veux juste m'assurer que vous cherchez simplement des réponses sur la gestion du cas général de ce problème (mise en cache des valeurs, etc.) et pas seulement en écrivant accidentellement un code médiocre :D

En regardant ce cas spécifique, vous pourriez avoir quelque chose du genre :

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

Ce qui dégénère en O(n) dans le pire des cas :D

[Modifier:* n'est pas égal à + :D ]

[Encore une autre modification :la version Haskell (parce que je suis masochiste ou quelque chose du genre)

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

]

Answer 9

Essayez d'utiliser une carte, n est la clé et son nombre de Fibonacci correspondant est la valeur.

@Paul

Merci pour l'info.Je ne le savais pas.Du Lien Wikipédia vous avez mentionné:

Cette technique de sauvegarde des valeurs qui ont déjà été calculées est appelée mémorisation

Ouais, j'ai déjà regardé le code (+1).:)

Answer 10

@ESRogs :

std::map la recherche est Ô(enregistrer n) ce qui le rend lent ici.Mieux vaut utiliser un vecteur.

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

D'autres ont répondu à votre question de manière précise et précise : vous recherchez une mémorisation.

Langages de programmation avec optimisation des appels de queue (principalement des langages fonctionnels) peuvent effectuer certains cas de récursion sans débordement de pile.Cela ne s'applique pas directement à votre définition de Fibonacci, bien qu'il existe des astuces.

La formulation de votre question m'a fait penser à une idée intéressante.Éviter le débordement de pile d'une fonction récursive pure en stockant uniquement un sous-ensemble des cadres de pile et en reconstruisant si nécessaire.Seulement vraiment utile dans quelques cas.Si votre algorithme ne s'appuie que de manière conditionnelle sur le contexte par opposition au retour, et/ou si vous optimisez la mémoire et non la vitesse.

Answer 12

Mathematica dispose d'une manière particulièrement astucieuse d'effectuer la mémorisation, en s'appuyant sur le fait que les hachages et les appels de fonction utilisent la même syntaxe :

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

C'est ça.Il met en cache (mémorise) fib[0] et fib[1] dès le départ et met en cache le reste si nécessaire.Les règles pour les appels de fonction de correspondance de modèles sont telles qu'elles utilisent toujours une définition plus spécifique avant une définition plus générale.

Answer 13

Une autre excellente ressource pour les programmeurs C# en matière de récursivité, de partiels, de curry, de mémorisation et autres est le blog de Wes Dyer, bien qu'il n'ait pas posté depuis un moment.Il explique bien la mémorisation, avec des exemples de code solides ici :http://blogs.msdn.com/wesdyer/archive/2007/01/26/function-memoization.aspx

Answer 14

Le problème avec ce code est qu'il générera une erreur de débordement de pile pour tout nombre supérieur à 15 (dans la plupart des ordinateurs).

Vraiment?Quel ordinateur utilisez-vous ?Cela prend beaucoup de temps à 44, mais la pile ne déborde pas.En fait, vous allez obtenir une valeur supérieure à ce qu'un entier peut contenir (~ 4 milliards non signés, ~ 2 milliards signés) avant que la pile ne déborde (Fibbonaci (46)).

Cela fonctionnerait pour ce que vous voulez faire (fonctionne rapidement)

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 vous utilisez un langage avec des fonctions de première classe comme Scheme, vous pouvez ajouter de la mémorisation sans changer l'algorithme initial :

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

Le premier bloc fournit une fonction de mémorisation et le deuxième bloc est la séquence de Fibonacci utilisant cette fonction.Celui-ci a désormais un runtime O(n) (par opposition à O(2^n) pour l'algorithme sans mémorisation).

Note:la fonction de mémorisation fournie utilise une chaîne de fermetures pour rechercher les invocations précédentes.Dans le pire des cas, cela peut être O(n).Dans ce cas, cependant, les valeurs souhaitées sont toujours en haut de la chaîne, garantissant ainsi la recherche O(1).

Answer 16

Comme d'autres affiches l'ont indiqué, mémorisation est un moyen standard d'échanger de la mémoire contre de la vitesse, voici un pseudo-code pour implémenter la mémorisation pour n'importe quelle fonction (à condition que la fonction n'ait pas d'effets secondaires) :

Code fonction initial :

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

Cela devrait être transformé 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

Au fait, Perl a un mémoriser module qui fait cela pour n’importe quelle fonction de votre code que vous spécifiez.

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

Afin de mémoriser cette fonction, il vous suffit de démarrer votre programme avec

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

Answer 18

@lassevk :

C'est génial, c'est exactement ce à quoi je pensais dans ma tête après avoir lu sur la mémorisation dans Perl d'ordre supérieur.Deux choses qui, à mon avis, seraient des ajouts utiles :

1. Paramètre facultatif pour spécifier une méthode statique ou membre utilisée pour générer la clé du cache.
2. Un moyen facultatif de modifier l'objet de cache afin que vous puissiez utiliser un cache sauvegardé sur un disque ou une base de données.

Je ne sais pas comment faire ce genre de chose avec les attributs (ou s'ils sont même possibles avec ce type d'implémentation), mais j'ai l'intention d'essayer de comprendre.

(Hors sujet:J'essayais de poster ceci sous forme de commentaire, mais je n'avais pas réalisé que les commentaires avaient une longueur autorisée si courte, donc cela ne correspond pas vraiment à une « réponse »)