Wie funktioniert das C ++ Funktion Gebrauch memoization?

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

Die obige Codebeispiel memoization unter Verwendung einer Rekursionsformel auf einige Eingangs n zu berechnen. Ich weiß, dass diese memoization verwendet, weil ich eine rein rekursive Funktion geschrieben habe, die die gleiche Formel verwendet, aber dies viel, viel schneller für viel größere Werte von n. Ich habe Vektoren noch nie benutzt, aber ich habe einige der Forschung getan, und ich verstehe das Konzept von ihnen. Ich verstehe, dass memoization soll jeder berechneten Wert speichern, so dass stattdessen die gleichen Berechnungen immer wieder durchzuführen, kann sie einfach diejenigen abzurufen, die bereits berechnet wurden.

Meine Frage ist: wie diese memoization ist und wie funktioniert es? Ich kann nicht auf die in den Code zu sehen scheinen, zeigen Sie es überprüft, ob ein Wert für n ist bereits vorhanden. Auch verstehe ich nicht den Zweck des if(as[n]<=0). Diese Formel kann positive und negative Werte ergeben, so dass ich bin mir nicht sicher, was diese Prüfung für sucht.

---

Danke, ich glaube, ich bin in der Nähe zu verstehen, wie dies funktioniert, es ist eigentlich ein bisschen einfacher, als ich dachte, es ist.

Ich glaube nicht, dass die Werte in der Folge immer 0 sein können, so sollte dies für mich arbeiten, wie ich n auf 1 starten denken hat

Wenn jedoch Null eine brauchbare Zahl in meiner Sequenz war, was ist eine andere Art, wie ich es lösen könnte? Zum Beispiel könnte was passiert, wenn fünf nie erscheinen? Würde ich nur muss meine Vektor mit Fünfer füllen?

Edit: Wow, ich habe viele andere Antworten, während Code überprüft und diese eine Eingabe. Danke für die Hilfe an alle, ich glaube, ich verstehe es jetzt.

Answer 1

if (as[n] <= 0) das Einchecken. Wenn gültige Werte negativ sein kann, wie Sie sagen, dann müssen Sie einen anderen Wächter zu überprüfen gegen. Kann gültige Werte immer gleich Null sein? Wenn nicht, dann stellen Sie einfach den Test if (as[n] == 0). Dies macht den Code leichter zu schreiben, da standardmäßig Vektoren ints werden mit Nullen aufgefüllt.

Answer 2

erscheint der Code falsch ist, werden überprüft (als [n] <= 0), und berechnet erneut die negativen Werte der Funktion (die ungefähr alle anderen Wert zu sein scheinen). Das macht die Arbeit Skala linear mit n anstelle von 2 ^ n mit der rekursiven Lösung, so dass es läuft viel schneller.

Still, eine bessere Kontrolle wäre zu prüfen, ob (wie [n] == 0), die 3x schneller auf meinem System zu laufen scheint. Auch wenn die Funktion 0 zurückgeben kann, ein Wert 0 bedeutet nur, wird es etwas länger dauern, zu berechnen (obwohl, wenn 0 ein häufiger Rückgabewert ist, möchten Sie vielleicht einen separaten Vektor betrachten, die Fahnen, ob der Wert berechnet wurde oder nicht statt unter Verwendung eines einzelnen Vektors der Funktion des Wert zu speichern und ob es berechnet)

wurde

Answer 3

Wenn die Formel sowohl positive als auch negative Werte ergeben kann dann hat diese Funktion einen schwerwiegenden Fehler. Die Prüfung if(as[n]<=0) ist sollte prüft werden, wenn es bereits diesen Wert der Berechnung zwischengespeichert hat. Aber wenn die Formel negativ sein kann diese Funktion neu berechnet diese im Cache gespeicherten Wert alot ...

Was es wirklich wahrscheinlich wollte ein vector<pair<bool, unsigned> > war, wo der Bool sagt, wenn der Wert berechnet wurde oder nicht.

Answer 4

Der Code, wie geschrieben, nur memoizes etwa 40% der Zeit (genau dann, wenn die Erinnerung Wert positiv ist). Wie Chris Jester-Young wies darauf hin, eine korrekte Umsetzung würde stattdessen if(as[n]==0) überprüfen. Alternativ kann man den memoization Code selbst ändern as[n]=mod(-4*a(n-1)-4*a(n-2),65535); lesen

(Selbst die ==0 Kontrolle würde Mühe aufwenden, wenn der memoized Wert 0. Zum Glück ist, in Ihrem Fall geschieht dies nie!)

Answer 5

Es gibt einen Fehler in diesem Code. Es wird weiterhin die Werte als [n] für so [n] <= 0. Es wird memoize die Werte ein, die erweisen sich als positiv neu zu berechnen. Es funktioniert viel schneller als Code ohne memoization weil es genügend positive Werte sind als [], so dass die Rekursion schnell beendet wird. Man könnte dies verbessern, indem ein Wert von mehr als 65535 als sentinal verwenden. Die neuen Werte des Vektors auf Null initialisiert werden, wenn der Vektor erweitert.