Como isso ++ C memoization uso função?

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

A amostra de código anterior utilizando memoização para calcular uma fórmula de recorrência com base em alguns n entrada. Eu sei que isso usos memoization, porque eu ter escrito uma função puramente recursiva que usa a mesma fórmula, mas uma muito, muito mais rápido para valores muito maiores de n. Eu nunca usei vetores antes, mas eu fiz alguma pesquisa e eu entendo o conceito deles. Eu entendo que memoization é suposto para armazenar cada valor calculado, de modo que em vez de executar os mesmos cálculos de novo, ele pode simplesmente recuperar os que já foram calculados.

A minha pergunta é: como isso é memoization, e como ele funciona? Eu não consigo ver no código em que ponto ele verifica se um valor para n já existe. Além disso, eu não entendo o propósito da if(as[n]<=0). Esta fórmula pode render valores positivos e negativos, então eu não tenho certeza do que esta verificação está procurando.

---

Obrigado, eu acho que estou perto de entender como isso funciona, na verdade é um pouco mais simples do que eu pensava que era.

Eu não acho que os valores na seqüência pode nunca ser 0, então isso deve funcionar para mim, como eu acho que n tem que começar em 1.

No entanto, se for zero era um número viável na minha sequência, o que é uma outra maneira que eu poderia resolver isso? Por exemplo, o que acontece se cinco poderiam nunca aparecem? Será que eu só precisa preencher o meu vetor com fives?

Edit: Uau, eu tenho um monte de outras respostas durante a verificação de código e digitando este. Obrigado pela ajuda a todos, eu acho que entendo isso agora.

Answer 1

if (as[n] <= 0) é o cheque. Se os valores válidos pode ser negativo como você diz, então você precisa de uma sentinela diferente para verificar contra. Pode valores válidos sempre ser zero? Se não, então apenas fazer a if (as[n] == 0) teste. Isso torna seu código mais fácil de escrever, porque por vetores padrão de ints são preenchidos com zeros.

Answer 2

O código parece ser incorrectamente verificação é (como [n] <= 0), e recalcula os valores negativos da função (que parecem ser aproximadamente a cada outro valor). Isso faz com que a escala de trabalho de forma linear com n em vez de 2 ^ n com a solução recursiva, para que ele funcione muito mais rápido.

Ainda assim, uma melhor verificação seria testar se (como [n] == 0), que aparece para executar 3x mais rápido no meu sistema. Mesmo que a função pode retornar 0, um valor 0 significa apenas que vai demorar um pouco mais para computação (embora se 0 é um valor de retorno freqüente, você pode querer considerar um vetor separado que bandeiras se o valor foi calculado ou não, em vez de usando um único vector para armazenar o valor da função e se foi calculado)

Answer 3

Se a fórmula pode produzir tanto valores positivos e negativos, então esta função tem um erro sério. O if(as[n]<=0) cheque é deveria para estar verificando se ele já tinha em cache este valor de computação. Mas se a fórmula pode ser negativo esta função recalcula esse valor em cache um monte ...

O que realmente provavelmente queria era um vector<pair<bool, unsigned> >, onde o bool diz que se o valor foi calculado ou não.

Answer 4

O código, conforme publicado, apenas a memoizes cerca de 40% do tempo (precisamente quando o valor lembrado é positivo). Como Chris Jester-Young apontou, uma correcta aplicação, ao invés, verificar if(as[n]==0). Alternativamente, pode-se alterar o código memoization-se a ler as[n]=mod(-4*a(n-1)-4*a(n-2),65535);

(Mesmo a verificação ==0 gastaria esforço quando o valor memoized era 0. Felizmente, no seu caso, isso nunca acontece!)

Answer 5

Há um erro neste código. Ele irá continuar para recalcular os valores de como [n] para que [n] <= 0. Vai memoize os valores de um que acabam por ser positivo. Ele funciona muito mais rápido do que o código sem a memoization porque existem valores positivos suficientes de como [] para que a recursividade é encerrado rapidamente. Você poderia melhorar isso usando um valor superior a 65535 como uma sentinela. Os novos valores do vector são inicializados a zero quando se expande vetor.