Gibt es eine Möglichkeit, die Rekursion zu beschleunigen, indem man sich untergeordnete Knoten merkt?
https://stackoverflow.com/questions/23962
-
09-06-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianFrage
Schauen Sie sich beispielsweise den Code an, der die N-te Fibonacci-Nummer berechnet:
fib(int n)
{
if(n==0 || n==1)
return 1;
return fib(n-1) + fib(n-2);
}
Das Problem mit diesem Code besteht darin, dass er bei jeder Zahl größer als 15 (auf den meisten Computern) einen Stapelüberlauffehler generiert.
Gehen wir davon aus, dass wir fib(10) berechnen.In diesem Prozess wird beispielsweise fib(5) häufig berechnet.Gibt es eine Möglichkeit, dies zum schnellen Abrufen im Speicher zu speichern und dadurch die Rekursionsgeschwindigkeit zu erhöhen?
Ich suche nach einer generischen Technik, die bei fast allen Problemen eingesetzt werden kann.
Lösung
Ja, deine Einsicht ist richtig.Das nennt man dynamische Programmierung.Es handelt sich normalerweise um einen allgemeinen Kompromiss zur Speicherlaufzeit.
Im Fall von Fibo müssen Sie nicht einmal alles zwischenspeichern:
bearbeiten] Der Autor der Frage scheint eher nach einer allgemeinen Methode zu suchen, um zu cache und eine Methode zur Berechnung von Fibonacci zu berechnen.Durchsuchen Sie Wikipedia oder sehen Sie sich den Code des anderen Posters an, um diese Antwort zu erhalten.Diese Antworten sind zeitlich und gedächtnislinear.
**Hier ist ein linearer Zeitalgorithmus O(n), konstant im Speicher **
in OCaml:
let rec fibo n =
let rec aux = fun
| 0 -> (1,1)
| n -> let (cur, prec) = aux (n-1) in (cur+prec, cur)
let (cur,prec) = aux n in prec;;
in C++:
int fibo(int n) {
if (n == 0 ) return 1;
if (n == 1 ) return 1;
int p = fibo(0);
int c = fibo(1);
int buff = 0;
for (int i=1; i < n; ++i) {
buff = c;
c = p+c;
p = buff;
};
return c;
};
Dies erfolgt in linearer Zeit.Aber loggen ist tatsächlich möglich!!!Roos Programm ist ebenfalls linear, aber viel langsamer und verbraucht Speicher.
Hier ist der Log-Algorithmus O(log(n))
Nun zum Log-Time-Algorithmus (viel, viel, viel schneller) ist hier eine Methode:Wenn Sie u(n), u(n-1) kennen, kann die Berechnung von u(n+1), u(n) durch Anwenden einer Matrix erfolgen:
| u(n+1) | = | 1 1 | | u(n) |
| u(n) | | 1 0 | | u(n-1) |
Damit Sie:
| u(n) | = | 1 1 |^(n-1) | u(1) | = | 1 1 |^(n-1) | 1 |
| u(n-1) | | 1 0 | | u(0) | | 1 0 | | 1 |
Die Berechnung der Exponentialfunktion der Matrix ist logarithmisch komplex.Implementieren Sie einfach rekursiv die Idee:
M^(0) = Id
M^(2p+1) = (M^2p) * M
M^(2p) = (M^p) * (M^p) // of course don't compute M^p twice here.
Sie können es auch einfach diagonalisieren (nicht allzu schwierig), dann finden Sie die Goldzahl und ihr Konjugat in ihrem Eigenwert und das Ergebnis wird Ihnen eine EXAKTE mathematische Formel für u(n) liefern.Es enthält Potenzen dieser Eigenwerte, sodass die Komplexität immer noch logarithmisch ist.
Fibo wird oft als Beispiel zur Veranschaulichung der dynamischen Programmierung herangezogen, aber wie Sie sehen, ist es nicht wirklich relevant.
@John:Ich glaube nicht, dass es etwas mit Haschisch zu tun hat.
@John2:Eine Karte ist etwas allgemein gehalten, finden Sie nicht?Im Fibonacci-Fall sind alle Schlüssel zusammenhängend, sodass ein Vektor geeignet ist. Auch hier gibt es viel schnellere Möglichkeiten, die Fibo-Sequenz zu berechnen, siehe mein Codebeispiel dort.
Andere Tipps
Dies nennt man Auswendiglernen und es gibt einen sehr guten Artikel über Auswendiglernen Matthew Podwysocki in diesen Tagen gepostet.Zur Veranschaulichung wird Fibonacci verwendet.Und zeigt den Code auch in C#.Lies es Hier.
Wenn Sie C# verwenden und verwenden können PostSharp, hier ist ein einfacher Memoisierungsaspekt für Ihren Code:
[Serializable]
public class MemoizeAttribute : PostSharp.Laos.OnMethodBoundaryAspect, IEqualityComparer<Object[]>
{
private Dictionary<Object[], Object> _Cache;
public MemoizeAttribute()
{
_Cache = new Dictionary<object[], object>(this);
}
public override void OnEntry(PostSharp.Laos.MethodExecutionEventArgs eventArgs)
{
Object[] arguments = eventArgs.GetReadOnlyArgumentArray();
if (_Cache.ContainsKey(arguments))
{
eventArgs.ReturnValue = _Cache[arguments];
eventArgs.FlowBehavior = FlowBehavior.Return;
}
}
public override void OnExit(MethodExecutionEventArgs eventArgs)
{
if (eventArgs.Exception != null)
return;
_Cache[eventArgs.GetReadOnlyArgumentArray()] = eventArgs.ReturnValue;
}
#region IEqualityComparer<object[]> Members
public bool Equals(object[] x, object[] y)
{
if (Object.ReferenceEquals(x, y))
return true;
if (x == null || y == null)
return false;
if (x.Length != y.Length)
return false;
for (Int32 index = 0, len = x.Length; index < len; index++)
if (Comparer.Default.Compare(x[index], y[index]) != 0)
return false;
return true;
}
public int GetHashCode(object[] obj)
{
Int32 hash = 23;
foreach (Object o in obj)
{
hash *= 37;
if (o != null)
hash += o.GetHashCode();
}
return hash;
}
#endregion
}
Hier ist eine Beispiel-Fibonacci-Implementierung, die es verwendet:
[Memoize]
private Int32 Fibonacci(Int32 n)
{
if (n <= 1)
return 1;
else
return Fibonacci(n - 2) + Fibonacci(n - 1);
}
Schnelles und schmutziges Auswendiglernen in C++:
Jede rekursive Methode type1 foo(type2 bar) { ... } lässt sich leicht auswendig lernen map<type2, type1> M.
// your original method
int fib(int n)
{
if(n==0 || n==1)
return 1;
return fib(n-1) + fib(n-2);
}
// with memoization
map<int, int> M = map<int, int>();
int fib(int n)
{
if(n==0 || n==1)
return 1;
// only compute the value for fib(n) if we haven't before
if(M.count(n) == 0)
M[n] = fib(n-1) + fib(n-2);
return M[n];
}
BEARBEITEN:@Konrad Rudolph
Konrad weist darauf hin, dass std::map nicht die schnellste Datenstruktur ist, die wir hier verwenden könnten.Das stimmt, a vector<something> sollte schneller sein als a map<int, something> (obwohl es möglicherweise mehr Speicher erfordert, wenn die Eingaben für die rekursiven Aufrufe der Funktion nicht wie in diesem Fall aufeinanderfolgende Ganzzahlen wären), aber Karten sind im Allgemeinen bequem zu verwenden.
Entsprechend Wikipedia Fib(0) sollte 0 sein, aber das spielt keine Rolle.
Hier ist eine einfache C#-Lösung mit for-Zyklus:
ulong Fib(int n)
{
ulong fib = 1; // value of fib(i)
ulong fib1 = 1; // value of fib(i-1)
ulong fib2 = 0; // value of fib(i-2)
for (int i = 0; i < n; i++)
{
fib = fib1 + fib2;
fib2 = fib1;
fib1 = fib;
}
return fib;
}
Es ist ein ziemlich häufiger Trick, Rekursion zu konvertieren Schwanzrekursion und dann zur Schleife.Weitere Einzelheiten finden Sie beispielsweise hier Vorlesung (ppt).
Welche Sprache ist das?Es läuft nichts in c über...Sie können auch versuchen, eine Nachschlagetabelle auf dem Heap zu erstellen oder eine Karte zu verwenden
Caching ist für solche Dinge im Allgemeinen eine gute Idee.Da die Fibonacci-Zahlen konstant sind, können Sie das Ergebnis nach der Berechnung zwischenspeichern.Ein kurzes C/Pseudocode-Beispiel
class fibstorage {
bool has-result(int n) { return fibresults.contains(n); }
int get-result(int n) { return fibresult.find(n).value; }
void add-result(int n, int v) { fibresults.add(n,v); }
map<int, int> fibresults;
}
fib(int n ) {
if(n==0 || n==1)
return 1;
if (fibstorage.has-result(n)) {
return fibstorage.get-result(n-1);
}
return ( (fibstorage.has-result(n-1) ? fibstorage.get-result(n-1) : fib(n-1) ) +
(fibstorage.has-result(n-2) ? fibstorage.get-result(n-2) : fib(n-2) )
);
}
calcfib(n) {
v = fib(n);
fibstorage.add-result(n,v);
}
Dies wäre ziemlich langsam, da jede Rekursion zu drei Suchvorgängen führt. Dies sollte jedoch die allgemeine Idee veranschaulichen
Ist das ein bewusst gewähltes Beispiel?(z.B.ein Extremfall, den Sie testen möchten)
Da es sich derzeit um O(1,6^n) handelt, möchte ich nur sicherstellen, dass Sie nur nach Antworten suchen, um den allgemeinen Fall dieses Problems zu lösen (Caching-Werte usw.) und nicht nur versehentlich schlechten Code zu schreiben :D
Wenn Sie sich diesen speziellen Fall ansehen, könnten Sie etwas in der Art haben:
var cache = [];
function fib(n) {
if (n < 2) return 1;
if (cache.length > n) return cache[n];
var result = fib(n - 2) + fib(n - 1);
cache[n] = result;
return result;
}
Was im schlimmsten Fall zu O(n) degeneriert :D
[Bearbeiten:* ist nicht gleich + :D ]
[Noch eine Änderung:die Haskell-Version (weil ich Masochist bin oder so)
fibs = 1:1:(zipWith (+) fibs (tail fibs))
fib n = fibs !! n
]
Versuchen Sie es mit einer Karte. n ist der Schlüssel und die entsprechende Fibonacci-Zahl ist der Wert.
@Paul
Danke für die Info.Das wusste ich nicht.Von dem Wikipedia-Link du erwähntest:
Diese bereits berechnete Technik zum Speichern von Werten wird als Memoisierung bezeichnet
Ja, ich habe mir den Code (+1) bereits angesehen.:) :)
@ESRogs:
std::map Nachschlagen ist Ö(Protokoll N), was es hier langsam macht.Verwenden Sie besser einen Vektor.
vector<unsigned int> fib_cache;
fib_cache.push_back(1);
fib_cache.push_back(1);
unsigned int fib(unsigned int n) {
if (fib_cache.size() <= n)
fib_cache.push_back(fib(n - 1) + fib(n - 2));
return fib_cache[n];
}
Andere haben Ihre Frage gut und genau beantwortet – Sie suchen nach Auswendiglernen.
Programmiersprachen mit Tail-Call-Optimierung (hauptsächlich funktionale Sprachen) können bestimmte Fälle der Rekursion ohne Stapelüberlauf durchführen.Es trifft nicht direkt auf Ihre Definition von Fibonacci zu, obwohl es Tricks gibt.
Die Formulierung Ihrer Frage brachte mich auf eine interessante Idee.Vermeidung eines Stapelüberlaufs einer rein rekursiven Funktion, indem nur eine Teilmenge der Stapelrahmen gespeichert und bei Bedarf neu erstellt wird.Nur in wenigen Fällen wirklich sinnvoll.Wenn sich Ihr Algorithmus nur bedingt auf den Kontext und nicht auf die Rückgabe verlässt und/oder Sie auf Speicher und nicht auf Geschwindigkeit optimieren.
Mathematica verfügt über eine besonders geschickte Methode zur Memoisierung, die auf der Tatsache beruht, dass Hashes und Funktionsaufrufe dieselbe Syntax verwenden:
fib[0] = 1;
fib[1] = 1;
fib[n_] := fib[n] = fib[n-1] + fib[n-2]
Das ist es.Es speichert fib[0] und fib[1] sofort zwischen (merkt es sich) und speichert den Rest nach Bedarf zwischen.Die Regeln für Mustervergleichsfunktionsaufrufe sehen vor, dass immer eine spezifischere Definition vor einer allgemeineren Definition verwendet wird.
Eine weitere hervorragende Ressource für C#-Programmierer für Rekursion, Partials, Currying, Memoisierung und dergleichen ist der Blog von Wes Dyer, obwohl er schon seit einiger Zeit nichts mehr gepostet hat.Er erklärt das Auswendiglernen gut, mit soliden Codebeispielen hier:http://blogs.msdn.com/wesdyer/archive/2007/01/26/function-memoization.aspx
Das Problem mit diesem Code besteht darin, dass er bei jeder Zahl größer als 15 (auf den meisten Computern) einen Stapelüberlauffehler generiert.
Wirklich?Welchen Computer verwenden Sie?Bei 44 dauert es lange, aber der Stapel quillt nicht über.Tatsächlich erhalten Sie einen Wert, der größer ist, als eine ganze Zahl aufnehmen kann (~4 Milliarden ohne Vorzeichen, ~2 Milliarden mit Vorzeichen), bevor der Stapel überläuft (Fibbonaci(46)).
Dies würde jedoch für das funktionieren, was Sie tun möchten (läuft sehr schnell)
class Program
{
public static readonly Dictionary<int,int> Items = new Dictionary<int,int>();
static void Main(string[] args)
{
Console.WriteLine(Fibbonacci(46).ToString());
Console.ReadLine();
}
public static int Fibbonacci(int number)
{
if (number == 1 || number == 0)
{
return 1;
}
var minus2 = number - 2;
var minus1 = number - 1;
if (!Items.ContainsKey(minus2))
{
Items.Add(minus2, Fibbonacci(minus2));
}
if (!Items.ContainsKey(minus1))
{
Items.Add(minus1, Fibbonacci(minus1));
}
return (Items[minus2] + Items[minus1]);
}
}
Wenn Sie eine Sprache mit erstklassigen Funktionen wie Scheme verwenden, können Sie Memoisierung hinzufügen, ohne den ursprünglichen Algorithmus zu ändern:
(define (memoize fn)
(letrec ((get (lambda (query) '(#f)))
(set (lambda (query value)
(let ((old-get get))
(set! get (lambda (q)
(if (equal? q query)
(cons #t value)
(old-get q))))))))
(lambda args
(let ((val (get args)))
(if (car val)
(cdr val)
(let ((ret (apply fn args)))
(set args ret)
ret))))))
(define fib (memoize (lambda (x)
(if (< x 2) x
(+ (fib (- x 1)) (fib (- x 2)))))))
Der erste Block bietet eine Memoisierungsfunktion und der zweite Block ist die Fibonacci-Folge, die diese Funktion nutzt.Dies hat nun eine O(n)-Laufzeit (im Gegensatz zu O(2^n) für den Algorithmus ohne Memoisierung).
Notiz:Die bereitgestellte Memoisierungsfunktion verwendet eine Kette von Abschlüssen, um nach früheren Aufrufen zu suchen.Im schlimmsten Fall kann dies O(n) sein.In diesem Fall stehen die gewünschten Werte jedoch immer an der Spitze der Kette, sodass eine O(1)-Suche gewährleistet ist.
Wie andere Poster angedeutet haben, Auswendiglernen ist eine Standardmethode, um Speicher gegen Geschwindigkeit einzutauschen. Hier ist ein Pseudocode zum Implementieren der Memoisierung für jede Funktion (vorausgesetzt, die Funktion hat keine Nebenwirkungen):
Anfänglicher Funktionscode:
function (parameters)
body (with recursive calls to calculate result)
return result
Dies sollte umgewandelt werden
function (parameters)
key = serialized parameters to string
if (cache[key] does not exist) {
body (with recursive calls to calculate result)
cache[key] = result
}
return cache[key]
Übrigens hat Perl eine auswendig lernen Modul, das dies für jede von Ihnen angegebene Funktion in Ihrem Code ausführt.
# Compute Fibonacci numbers
sub fib {
my $n = shift;
return $n if $n < 2;
fib($n-1) + fib($n-2);
}
Um sich diese Funktion zu merken, müssen Sie lediglich Ihr Programm mit starten
use Memoize;
memoize('fib');
# Rest of the fib function just like the original version.
# Now fib is automagically much faster ;-)
@lassevk:
Das ist großartig, genau das, worüber ich in meinem Kopf nachgedacht habe, nachdem ich über das Auswendiglernen in gelesen hatte Perl höherer Ordnung.Zwei Dinge wären meiner Meinung nach sinnvolle Ergänzungen:
- Ein optionaler Parameter zum Angeben einer statischen oder Mitgliedsmethode, die zum Generieren des Schlüssels für den Cache verwendet wird.
- Eine optionale Möglichkeit, das Cache-Objekt so zu ändern, dass Sie einen festplatten- oder datenbankgestützten Cache verwenden können.
Ich bin mir nicht sicher, wie man so etwas mit Attributen macht (oder ob sie mit dieser Art der Implementierung überhaupt möglich sind), aber ich habe vor, es herauszufinden.
(Off-Topic:Ich habe versucht, dies als Kommentar zu posten, wusste aber nicht, dass Kommentare eine so kurze zulässige Länge haben, sodass dies nicht wirklich als „Antwort“ passt.)
