In che modo questa funzione C ++ utilizza la memoizzazione?

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'esempio di codice sopra riportato utilizza la memoization per calcolare una formula ricorsiva basata su alcuni input n. So che questo utilizza la memoizzazione, perché ho scritto una funzione puramente ricorsiva che utilizza la stessa formula, ma questa molto, molto più velocemente per valori molto più grandi di if(as[n]<=0). Non ho mai usato vettori prima, ma ho fatto qualche ricerca e capisco il loro concetto. Comprendo che si suppone che la memoizzazione memorizzi ogni valore calcolato, in modo che invece di eseguire nuovamente gli stessi calcoli, possa semplicemente recuperare quelli che sono già stati calcolati.

La mia domanda è: come è questa memoization e come funziona? Non riesco a vedere nel codice a quel punto controlla se esiste già un valore per n. Inoltre, non capisco lo scopo di <=>. Questa formula può produrre valori positivi e negativi, quindi non sono sicuro di cosa stia cercando questo controllo.

---

Grazie, penso di essere vicino a capire come funziona, in realtà è un po 'più semplice di quanto pensassi.

Non credo che i valori nella sequenza possano mai essere 0, quindi questo dovrebbe funzionare per me, poiché penso che n debba iniziare da 1.

Tuttavia, se zero era un numero valido nella mia sequenza, qual è un altro modo in cui potrei risolverlo? Ad esempio, cosa accadrebbe se cinque non potessero mai apparire? Avrei solo bisogno di riempire il mio vettore con cinque?

Modifica: Wow, ho ricevuto molte altre risposte mentre controllavo il codice e scrivevo questo. Grazie per l'aiuto a tutti, penso di capirlo ora.

Answer 1

if (as[n] <= 0) è il segno di spunta. Se i valori validi possono essere negativi come dici tu, allora hai bisogno di una sentinella diversa per verificare. I valori validi possono mai essere zero? In caso contrario, esegui il test if (as[n] == 0). Ciò semplifica la scrittura del codice, perché per impostazione predefinita i vettori di int s sono riempiti con zero.

Answer 2

Sembra che il codice stia verificando in modo errato (come [n] < = 0) e ricalcola i valori negativi della funzione (che sembrano essere approssimativamente ogni altro valore). Questo rende la scala di lavoro linearmente con n invece di 2 ^ n con la soluzione ricorsiva, quindi corre molto più velocemente.

Tuttavia, un controllo migliore sarebbe verificare se (come [n] == 0), che sembra funzionare 3 volte più veloce sul mio sistema. Anche se la funzione può restituire 0, un valore 0 significa che ci vorrà un po 'più tempo per il calcolo (anche se se 0 è un valore di ritorno frequente, potresti voler considerare un vettore separato che indica se il valore è stato calcolato o no invece di utilizzando un singolo vettore per memorizzare il valore della funzione e se è stato calcolato)

Answer 3

Se la formula può produrre sia valori positivi che negativi, questa funzione presenta un bug grave. Il controllo if(as[n]<=0) è supposto per verificare se aveva già memorizzato nella cache questo valore di calcolo. Ma se la formula può essere negativa questa funzione ricalcola molto questo valore memorizzato nella cache ...

Quello che probabilmente desiderava era un vector<pair<bool, unsigned> >, dove il bool dice se il valore è stato calcolato o meno.

Answer 4

Il codice, come pubblicato, memorizza solo circa il 40% delle volte (proprio quando il valore memorizzato è positivo). Come ha sottolineato Chris Jester-Young, un'implementazione corretta dovrebbe invece controllare if(as[n]==0). In alternativa, è possibile modificare il codice di memoization stesso in as[n]=mod(-4*a(n-1)-4*a(n-2),65535);

(Anche il controllo ==0 farebbe fatica se il valore memorizzato era 0. Fortunatamente, nel tuo caso, ciò non accade mai!)

Answer 5

C'è un bug in questo codice. Continuerà a ricalcolare i valori di come [n] per come [n] & Lt; = 0. Memorizzerà i valori di a che risultano positivi. Funziona molto più velocemente del codice senza la memoization perché ci sono abbastanza valori positivi di as [] in modo che la ricorsione venga terminata rapidamente. È possibile migliorare ciò utilizzando un valore maggiore di 65535 come sentinella. I nuovi valori del vettore vengono inizializzati su zero quando il vettore si espande.