Comment cette fonction C++ utilise-t-elle la mémorisation?

Question

#include <vector> 
std::vector<long int> as; 

long int a(size_t n){ 
    if(n==1) return 1; 
    if(n==2) return -2; 
    if(as.size()<n+1) 
    as.resize(n+1); 
    if(as[n]<=0) 
    { 
    as[n]=-4*a(n-1)-4*a(n-2); 
    } 
    return mod(as[n], 65535); 
} 

L'exemple de code ci-dessus utilisant la mémoisation pour calculer une formule récursive basée sur une entrée n. Je sais que cela utilise memoization, parce que j'ai écrit une fonction purement récursive qui utilise la même formule, mais celui-ci beaucoup, beaucoup plus rapide pour des valeurs beaucoup plus grandes de n. Je n'ai jamais utilisé de vecteurs auparavant, mais j'ai fait quelques recherches et je comprends leur concept. Je comprends que la mémorisation est supposée stocker chaque valeur calculée, de sorte qu'au lieu d'effectuer à nouveau les mêmes calculs, elle peut simplement récupérer ceux qui ont déjà été calculés.

Ma question est: comment est cette mémo, et comment ça marche? Je n'arrive pas à voir dans le code à quel point il vérifie si une valeur pour n existe déjà. En outre, je ne comprends pas le but de la if(as[n]<=0). Cette formule peut donner des valeurs positives et négatives, donc je ne suis pas sûr de ce que cette vérification recherche.

---

Merci, je pense que je suis proche de comprendre comment cela fonctionne, il est en fait un peu plus simple que je pensais qu'il était.

Je ne pense pas que les valeurs de la séquence ne peut jamais être 0, donc cela devrait fonctionner pour moi, je pense que n doit commencer à 1.

Toutefois, si nul était un nombre viable dans ma séquence , quelle est une autre façon de le résoudre? Par exemple, et si cinq ne pouvaient jamais apparaître? Aurais-je juste besoin de remplir mon vecteur avec cinq? Edit: Wow, j'ai eu beaucoup d'autres réponses tout en vérifiant le code et en tapant celui-ci. Merci pour l'aide tout le monde, je pense que je comprends maintenant.

Answer 1

if (as[n] <= 0) est la vérification. Si des valeurs valides peuvent être négatives comme vous le dites, alors vous avez besoin d'une sentinelle différente pour vérifier. Les valeurs valides peuvent-elles jamais être nulles? Si ce n'est pas le cas, faites simplement le test if (as[n] == 0). Cela rend votre code plus facile à écrire car, par défaut, les vecteurs int sont remplis de zéros.

Answer 2

Si la formule peut produire à la fois des valeurs positives et négatives, alors cette fonction a un bug sérieux. Le contrôle if(as[n]<=0) est supposé pour vérifier s'il avait déjà mis en cache cette valeur de calcul. Mais si la formule peut être négative, cette fonction recalcule cette valeur cachée ...

Ce qu'il voulait vraiment, c'était un vector<pair<bool, unsigned> >, où la booléenne indique si la valeur a été calculée ou non.

Answer 3

Le code semble être incorrectement vérifier est (comme [n] < = 0), et recalcule les valeurs négatives de la fonction (qui semblent être environ toutes les autres valeurs). Cela fait que l'échelle de travail est linéaire avec n au lieu de 2^n avec la solution récursive, de sorte qu'elle fonctionne beaucoup plus rapidement. Cependant, une meilleure vérification serait de tester si (comme [n] == 0), qui semble courir 3 fois plus vite sur mon système. Même si la fonction peut renvoyer 0, une valeur 0 signifie simplement que le calcul prendra un peu plus de temps (bien que si 0 est une valeur de retour fréquente, vous pouvez envisager un vecteur distinct indiquant si la valeur a été calculée ou non au lieu de utiliser un seul vecteur pour stocker la valeur de la fonction et si elle a été calculée)

Answer 4

Le code, tel qu'il est affiché, ne mémorise que 40% du temps (précisément lorsque la valeur mémorisée est positive). Comme Chris Jester-Young l'a souligné, une implémentation correcte vérifie à la place if(as[n]==0).Alternativement, on peut modifier le code memoization lui-même pour lire as[n]=mod(-4*a(n-1)-4*a(n-2),65535);

(Même le ==0 contrôle dépenserait effort lorsque la valeur memoized était 0. Heureusement, dans votre cas, cela ne se produit jamais!)

Answer 5

Il y a un bug dans ce code. Il continuera à recalculer les valeurs de as [n] pour as [n] < = 0. Il mémorisera les valeurs de a qui s'avèrent positives. Cela fonctionne beaucoup plus vite que le code sans memoization car il y a suffisamment de valeurs positives de as [] pour que la récursion se termine rapidement. Vous pourriez améliorer cela en utilisant une valeur supérieure à 65535 comme sentinal. Les nouvelles valeurs du vecteur sont initialisées à zéro lorsque le vecteur se développe.