Hilft das Verwenden von funktionalen Sprachen gegen die wiederholte Berechnung von Werten?

Question

Betrachten wir eine Funktion f (x, y):

f(x,0) = x*x; 
f(0,y) = y*(y + 1); 
f(x,y) = f(x,y-1) + f(x-1,y); 

Wenn man die rekursiv in einer Sprache wie C++ zu implementieren versucht, wird er auf ein Problem stoßen.

Angenommen, die Funktion wird zuerst mit x = x0 und y = y0 aufgerufen. Dann werden für jedes Paar (x, y), bei dem 0 <= x < x0 und 0 <= y < y0 die Zwischenwerte mehrfach berechnet werden - rekursive Aufrufe bilden einen riesigen Baum, in dem mehrere Blätter tatsächlich die gleichen Paare (x, y) enthalten. Für Paare (x, y), bei denen x und y beide nahe bei 0 liegen, werden Werte mehrfach berechnet.

Zum Beispiel habe ich eine ähnliche Funktion in C++ getestet - für x=20 und y=20 ihre Berechnung dauert etwa 4 Stunden (ja, vier Stunden Erde!).

Offensichtlich kann die Implementierung so umgeschrieben werden, dass wiederholte Berechnungen nicht auftreten - entweder iterativ oder mit einer Cache-Tabelle.

Die Frage ist: Werden funktionale Sprachen besser und vermeiden wiederholte Berechnungen bei der rekursiven Implementierung einer Funktion wie oben?

Answer 1

Der Begriff Sie hier suchen ist Memoization:

In dem Computer memoization eine in erster Linie Programme durch mit Funktionsaufrufen die Berechnung der Ergebnisse zu vermeiden Wiederholung zu beschleunigen Computer verwendet Optimierungstechnik ist für zuvor verarbeitete Eingänge.

Nein, funktionale Sprache implementiert Memoization nicht automatisch. Sie können es in ihnen implementieren, aber auch in C++. Es stimmt jedoch, dass, wenn Sie rein funktionalen Code schreiben (d. H. Ohne Nebenwirkungen), die Memo-Erstellung einfacher ist. Einige dynamische Sprachen (z. B. Perl) verfügen über Auto-Memo-Module, mit denen sich einfach jede Funktion merken lässt. Es gibt eine Diskussion dieses Themas in der Automatic memoization section of the Wikipedia article.

Zum Beispiel hier ist ein naiver C++ Fibonacci:

long fib_rec(long index) 
{ 
    if (index < 2) 
     return index; 
    else 
     return fib_rec(index - 1) + fib_rec(index - 2); 
} 

Und hier ist eine memoized Version:

long fib_memoized_aux(vector<long>& cache, long index) 
{ 
    if (cache[index] >= 0) 
    return cache[index]; 

    cache[index] = fib_memoized_aux(cache, index - 1) + fib_memoized_aux(cache, index - 2); 
    return cache[index]; 
} 


long fib_memoized(long index) 
{ 
    vector<long> cache(index + 1, -1); 
    cache[0] = 0; 
    cache[1] = 1; 

    return fib_memoized_aux(cache, index); 
}