Ich weiß, wie man in Python leicht Memoization macht, aber ich brauche einen schnelleren Weg, sie zu berechnen, also benutze ich C ++. Ich habe jedoch keine Ahnung, wie man memotisiert. Ich verstehe, dass es darum geht, Werte in einem Array oder Vektor zu speichern und dann beim Abrufen nach dem Wert zu suchen, aber es wäre wirklich hilfreich zu sehen, wie das gemacht wird, damit ich seine Geschwindigkeit testen kann.
Nun, die wahrscheinlichste Art und Weise, wie ich das in C ++ machen kann, ist wahrscheinlich, ein Funktionsobjekt zu verwenden, um die Memo-Werte zu speichern. Ich nehme an, das ist wahrscheinlich etwas ähnlich zu deinem Python-Dekorateur, obwohl ich noch nie wirklich Python gemacht habe. Der Code würde ungefähr so aussehen:
%Vor%Der Code definiert eine Template-Klasse, die einen Typnamen und einen Funktionszeiger übernimmt, der Funktionsoperator wird dann für die Klasse definiert, damit er aufgerufen werden kann. Der Funktionsoperator nimmt einen Eingabewert auf, prüft, ob dieser Wert in einer Map enthalten ist, und gibt ihn entweder einfach aus der Map zurück oder berechnet ihn (mithilfe des Funktionszeigers), fügt ihn der Map hinzu und gibt ihn zurück.
Nehmen wir an, Sie definieren eine Verarbeitungsfunktion wie zB:
%Vor%Sie würden den Code wie folgt verwenden:
%Vor%Wir definieren also eine Instanz der mem-Klasse, die unseren Werttyp und die Verarbeitungsfunktion als Template-Parameter verwendet, und nennen diese Klasse einfach als Funktion.
Nur zum Spaß, hier ist ein kleiner generischer Memoizer, den ich vor einiger Zeit geschrieben habe. Es erfordert natürlich variadic Vorlagen:
%Vor%Ich bin mir nicht ganz sicher, ob ich die rvalue-forwardiness richtig verstanden habe, denn es ist schon lange her, dass ich das geschrieben habe. Wie auch immer, hier ist ein Testfall:
%Vor%Niemand außer einem Studenten, der eine Rekursion lernt, würde auf diese Weise Faktoren berechnen.
Memoization ist eine sehr gute Idee, besonders wenn Sie die Methode wiederholt aufrufen. Warum gute Arbeit wegwerfen?
Eine weitere Überlegung ist eine bessere Methode zur Berechnung von Faktoren: Verwenden Sie den natürlichen Logarithmus der Gamma-Funktion. Es hält länger gegen Überlauf, weil Sie einen doppelten Wert zurückgeben. Das natürliche Protokoll wird langsamer als der Wert wachsen. Wenn Sie Kombinationen berechnen, ändert das natürliche Protokoll Multiplikation und Division in Addition und Subtraktion.
Aber schreiben Sie auf jeden Fall für jede Implementierung, die Sie verwenden. Wenn Sie es in C ++ schreiben, würde ich empfehlen, ein std:map mit dem Argument x als Schlüssel und ln(gamma(x)) als Wert zu verwenden.
Tut mir leid, es ist zu lange her, seit ich C ++ und STL geschrieben habe. Ich würde lieber eine Hash-Map mit O(1) Lesezugriffszeit verwenden, um über die Schlüssel in O(n) iterieren zu müssen.
Ich verlasse mich gerne auf Lambda Capture wie in (uses std=c++14 )