¿Cómo utiliza esta función C ++ la memorización?

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

El ejemplo de código anterior utilizando la memorización para calcular una fórmula recursiva basada en alguna entrada n. Sé que esto usa la memorización, porque he escrito una función puramente recursiva que usa la misma fórmula, pero esta mucho, mucho más rápido para valores mucho mayores de if(as[n]<=0). Nunca he usado vectores antes, pero he investigado un poco y entiendo el concepto de ellos. Entiendo que se supone que la memorización almacena cada valor calculado, de modo que en lugar de realizar los mismos cálculos nuevamente, simplemente puede recuperar los que ya se han calculado.

Mi pregunta es: ¿cómo es esta memorización y cómo funciona? Parece que no puedo ver en el código en qué punto verifica si ya existe un valor para n. Además, no entiendo el propósito de <=>. Esta fórmula puede arrojar valores positivos y negativos, por lo que no estoy seguro de lo que está buscando esta verificación.

---

Gracias, creo que estoy cerca de entender cómo funciona esto, en realidad es un poco más simple de lo que pensaba.

No creo que los valores en la secuencia puedan ser 0, así que esto debería funcionar para mí, ya que creo que n tiene que comenzar en 1.

Sin embargo, si cero era un número viable en mi secuencia, ¿de qué otra manera podría resolverlo? Por ejemplo, ¿qué pasa si cinco nunca podrían aparecer? ¿Necesitaría llenar mi vector con cinco?

Editar: Wow, recibí muchas otras respuestas mientras comprobaba el código y escribía esta. Gracias por la ayuda a todos, creo que lo entiendo ahora.

Answer 1

if (as[n] <= 0) es el cheque. Si los valores válidos pueden ser negativos como usted dice, entonces necesita un centinela diferente para comparar. ¿Pueden los valores válidos ser alguna vez cero? Si no es así, simplemente haga la prueba if (as[n] == 0). Esto hace que su código sea más fácil de escribir, porque por defecto los vectores de int s están llenos de ceros.

Answer 2

El código parece estar comprobando incorrectamente es (como [n] < = 0) y recalcula los valores negativos de la función (que parecen ser aproximadamente cualquier otro valor). Esto hace que el trabajo escale linealmente con n en lugar de 2 ^ n con la solución recursiva, por lo que se ejecuta mucho más rápido.

Aún así, una mejor comprobación sería probar si (como [n] == 0), que parece ejecutarse 3 veces más rápido en mi sistema. Incluso si la función puede devolver 0, un valor de 0 solo significa que tomará un poco más de tiempo calcular (aunque si 0 es un valor de retorno frecuente, es posible que desee considerar un vector separado que indique si el valor se ha calculado o no en lugar de usando un solo vector para almacenar el valor de la función y si se ha calculado)

Answer 3

Si la fórmula puede producir valores positivos y negativos, entonces esta función tiene un error grave. La comprobación if(as[n]<=0) se supone que está comprobando si ya había almacenado en caché este valor de cálculo. Pero si la fórmula puede ser negativa, esta función recalcula mucho este valor en caché ...

Lo que probablemente quería era un vector<pair<bool, unsigned> >, donde el bool dice si el valor ha sido calculado o no.

Answer 4

El código, tal como se publicó, solo memoriza aproximadamente el 40% del tiempo (precisamente cuando el valor recordado es positivo). Como señaló Chris Jester-Young, una implementación correcta verificaría en su lugar if(as[n]==0). Alternativamente, uno puede cambiar el código de memorización para leer as[n]=mod(-4*a(n-1)-4*a(n-2),65535);

(¡Incluso la comprobación ==0 gastaría esfuerzo cuando el valor memorizado fuera 0. Por suerte, en su caso, esto nunca sucede!)

Answer 5

Hay un error en este código. Continuará recalculando los valores de as [n] para as [n] & Lt; = 0. Memorizará los valores de a que resulten positivos. Funciona mucho más rápido que el código sin la memorización porque hay suficientes valores positivos de as [] para que la recursión finalice rápidamente. Podría mejorar esto utilizando un valor mayor que 65535 como un sentinal. Los nuevos valores del vector se inicializan a cero cuando el vector se expande.