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

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'échantillon de code ci-dessus utilisant la mémorisation pour calculer une formule récursive basée sur une entrée n. Je sais que cela utilise la mémoisation, car j’ai écrit une fonction purement récursive qui utilise la même formule, mais celle-ci est beaucoup plus rapide pour les valeurs beaucoup plus grandes de if(as[n]<=0). Je n'ai jamais utilisé de vecteurs auparavant, mais j'ai effectué des recherches et j'en comprends le concept. Je comprends que la mémorisation est supposée stocker chaque valeur calculée, de sorte qu’au lieu de refaire les mêmes calculs, elle puisse simplement récupérer celles qui ont déjà été calculées.

Ma question est la suivante: comment se passe cette mémorisation et comment fonctionne-t-elle? Je n'arrive pas à voir dans le code à quel point il vérifie si une valeur pour n existe déjà. De plus, je ne comprends pas le but de la <=>. Cette formule peut générer des valeurs positives et négatives, je ne suis donc pas sûr de ce que cette vérification recherche.

Merci, je pense que je suis sur le point de comprendre comment cela fonctionne. C'est en fait un peu plus simple que je ne le pensais.

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

Cependant, si zéro est un nombre viable dans ma séquence, comment puis-je le résoudre? Par exemple, si cinq ne pouvaient jamais apparaître? Aurais-je juste besoin de remplir mon vecteur de cinq ans?

Edit: Wow, j'ai eu beaucoup d'autres réponses tout en vérifiant le code et en tapant celui-ci. Merci à tous pour votre aide, je pense que je le comprends maintenant.

Answer 1

if (as[n] <= 0) est le chèque. Si les valeurs valides peuvent être négatives, comme vous le dites, il vous faut alors une sentinelle différente. Les valeurs valides peuvent-elles être égales à zéro? Sinon, faites simplement le test if (as[n] == 0). Cela rend votre code plus facile à écrire car, par défaut, les vecteurs de int s sont remplis de zéros.

Answer 2

Le code semble vérifier incorrectement (comme [n] < = 0) et recalcule les valeurs négatives de la fonction (qui semblent être approximativement toutes les autres valeurs). Cela rend le travail évolutif de manière linéaire avec n au lieu de 2 ^ n avec la solution récursive, de sorte qu'il s'exécute beaucoup plus rapidement.

Néanmoins, une meilleure vérification consisterait à vérifier si (comme [n] == 0), qui semble fonctionner 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 soit une valeur de retour fréquente, vous voudrez peut-être envisager un vecteur séparé indiquant si la valeur a été calculée ou non à la place de en utilisant un seul vecteur pour stocker la valeur de la fonction et si elle a été calculée)

Answer 3

Si la formule peut produire à la fois des valeurs positives et négatives, cette fonction présente un problème grave. La vérification if(as[n]<=0) est supposée vérifier si elle a déjà mis en cache cette valeur de calcul. Mais si la formule peut être négative, cette fonction recalcule cette valeur en cache beaucoup ...

Ce qu’elle souhaitait sans doute, c’était un vector<pair<bool, unsigned> >, où la valeur booléenne indiquait si la valeur avait été calculée ou non.

Answer 4

Le code, tel que posté, ne mémorise que 40% du temps environ (précisément lorsque la valeur mémorisée est positive). Comme le souligne Chris Jester-Young, une mise en œuvre correcte vérifierait plutôt if(as[n]==0). Alternativement, on peut changer le code de mémoization lui-même pour lire as[n]=mod(-4*a(n-1)-4*a(n-2),65535);

(Même la ==0 vérification nécessitait des efforts lorsque la valeur mémo était égale à 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 [n] & Lt; = 0. Il mémorisera les valeurs de a qui s'avèrent positives. Cela fonctionne beaucoup plus rapidement que le code sans la mémorisation, car il y a suffisamment de valeurs positives de as [] pour que la récursivité se termine rapidement. Vous pouvez améliorer cela en utilisant une valeur supérieure à 65535 en tant que sentinelle. Les nouvelles valeurs du vecteur sont initialisées à zéro lorsque le vecteur se développe.