Hinweise zur effizienten Lösung der folgenden Funktion in Haskell für große Zahlen (n > 108)
f(n) = max(n, f(n/2) + f(n/3) + f(n/4))
Ich habe Beispiele für das Auswendiglernen in Haskell gesehen, um Fibonacci-Zahlen zu lösen, bei denen alle Fibonacci-Zahlen (träge) bis zum erforderlichen n berechnet wurden. In diesem Fall müssen wir für ein gegebenes n nur sehr wenige Zwischenergebnisse berechnen.
Vielen Dank
haskell
memoization
Angel de Vicente
quelle
quelle
Antworten:
Wir können dies sehr effizient tun, indem wir eine Struktur erstellen, die wir in sublinearer Zeit indizieren können.
Aber zuerst,
Lassen Sie uns definieren
f
, aber lassen Sie es "offene Rekursion" verwenden, anstatt sich selbst direkt aufzurufen.Sie können eine unmemoized
f
mit verwendenfix f
Auf diese Weise können Sie testen,
f
was Sie für kleine Wertef
von tun, indem Sie beispielsweise Folgendes aufrufen:fix f 123 = 144
Wir könnten dies auswendig lernen, indem wir definieren:
Das funktioniert passabel gut und ersetzt das, was O (n ^ 3) Zeit in Anspruch nehmen würde, durch etwas, das die Zwischenergebnisse auswendig lernt.
Es dauert jedoch immer noch eine lineare Zeit, nur um zu indizieren, um die gespeicherte Antwort für zu finden
mf
. Dies bedeutet, dass Ergebnisse wie:sind erträglich, aber das Ergebnis skaliert nicht viel besser. Wir können es besser machen!
Definieren wir zunächst einen unendlichen Baum:
Und dann definieren wir einen Weg, um darin zu indizieren, damit wir stattdessen einen Knoten mit Index
n
in O (log n) Zeit finden können:... und wir finden vielleicht einen Baum voller natürlicher Zahlen, damit wir nicht mit diesen Indizes herumspielen müssen:
Da wir indizieren können, können Sie einfach einen Baum in eine Liste konvertieren:
Sie können die bisherige Arbeit überprüfen, indem Sie überprüfen, ob
toList nats
Sie diese erhalten[0..]
Jetzt,
funktioniert genau wie in der obigen Liste, aber anstatt lineare Zeit zu benötigen, um jeden Knoten zu finden, kann er in logarithmischer Zeit verfolgt werden.
Das Ergebnis ist erheblich schneller:
In der Tat ist es so viel schneller , dass Sie durchmachen können und ersetzen
Int
mitInteger
oben und fast augenblicklich lächerlich großen Antworten erhaltenquelle
f_tree
in einerwhere
Klausel definiert werden sollte , um zu vermeiden, dass nicht benötigte Pfade über Aufrufe hinweg im Baum gespeichert werden.Edwards Antwort ist so ein wunderbares Juwel, dass ich sie dupliziert und Implementierungen von
memoList
und bereitgestellt habememoTree
Kombinatoren , die eine Funktion in offen-rekursiver Form auswendig lernen.quelle
Nicht der effizienteste Weg, merkt sich aber:
auf Anfrage
f !! 144
wird geprüft, obf !! 143
vorhanden, der genaue Wert wird jedoch nicht berechnet. Es ist immer noch als unbekanntes Ergebnis einer Berechnung festgelegt. Die einzigen exakten berechneten Werte sind die benötigten.Soweit berechnet, weiß das Programm zunächst nichts.
Wenn wir die Anfrage stellen
f !! 12
, wird ein Mustervergleich durchgeführt:Jetzt beginnt die Berechnung
Dies stellt rekursiv eine weitere Anforderung an f, also berechnen wir
Jetzt können wir einige wieder hochrinnen
Das heißt, das Programm weiß jetzt:
Weiter rieseln:
Das heißt, das Programm weiß jetzt:
Nun fahren wir mit unserer Berechnung fort von
f!!6
:Das heißt, das Programm weiß jetzt:
Nun fahren wir mit unserer Berechnung fort von
f!!12
:Das heißt, das Programm weiß jetzt:
Die Berechnung erfolgt also ziemlich träge. Das Programm weiß, dass ein Wert für
f !! 8
existiert, der gleich istg 8
, aber es hat keine Ahnung, wasg 8
ist.quelle
g n m = (something with) f!!a!!b
Dies ist ein Nachtrag zu Edward Kmotts ausgezeichneter Antwort.
Als ich seinen Code ausprobierte, schienen die Definitionen von
nats
undindex
ziemlich mysteriös zu sein, also schreibe ich eine alternative Version, die ich leichter verständlich fand.Ich definiere
index
undnats
in Bezug aufindex'
undnats'
.index' t n
wird über den Bereich definiert[1..]
. (Erinnern Sie sich daran, dass diesindex t
über den Bereich definiert ist[0..]
.) Es durchsucht den Baum, indem esn
als eine Folge von Bits behandelt und die Bits in umgekehrter Reihenfolge durchliest. Wenn das Bit ist1
, nimmt es den rechten Zweig. Wenn das Bit ist0
, nimmt es den linken Zweig. Es stoppt, wenn es das letzte Bit erreicht (das a sein muss1
).Genau wie
nats
für definiert,index
so dassindex nats n == n
immer wahr ist,nats'
ist für definiertindex'
.Nun,
nats
undindex
sind einfachnats'
undindex'
doch mit den um 1 verschobenen Werten:quelle
Wie in der Antwort von Edward Kmett angegeben, müssen Sie kostspielige Berechnungen zwischenspeichern und schnell darauf zugreifen können, um die Dinge zu beschleunigen.
Um die Funktion nicht monadisch zu halten, erfüllt die Lösung des Erstellens eines unendlichen faulen Baums mit einer geeigneten Methode zum Indizieren (wie in den vorherigen Beiträgen gezeigt) dieses Ziel. Wenn Sie die nicht-monadische Natur der Funktion aufgeben, können Sie die in Haskell verfügbaren assoziativen Standardcontainer in Kombination mit „zustandsähnlichen“ Monaden (wie State oder ST) verwenden.
Während der Hauptnachteil darin besteht, dass Sie eine nicht monadische Funktion erhalten, müssen Sie die Struktur nicht mehr selbst indizieren und können nur Standardimplementierungen von assoziativen Containern verwenden.
Dazu müssen Sie zuerst Ihre Funktion neu schreiben, um jede Art von Monade zu akzeptieren:
Für Ihre Tests können Sie weiterhin eine Funktion definieren, die mit Data.Function.fix keine Memoisierung ausführt, obwohl sie etwas ausführlicher ist:
Sie können dann State Monad in Kombination mit Data.Map verwenden, um die Dinge zu beschleunigen:
Mit geringfügigen Änderungen können Sie den Code so anpassen, dass er stattdessen mit Data.HashMap funktioniert:
Anstelle von persistenten Datenstrukturen können Sie auch veränderbare Datenstrukturen (wie die Data.HashTable) in Kombination mit der ST-Monade ausprobieren:
Im Vergleich zur Implementierung ohne Memoisierung können Sie mit jeder dieser Implementierungen für große Eingaben Ergebnisse in Mikrosekunden erzielen, anstatt mehrere Sekunden warten zu müssen.
Anhand von Criterion als Benchmark konnte ich feststellen, dass die Implementierung mit der Data.HashMap tatsächlich etwas besser abschnitt (etwa 20%) als die mit der Data.Map und der Data.HashTable, für die die Timings sehr ähnlich waren.
Ich fand die Ergebnisse des Benchmarks etwas überraschend. Mein anfängliches Gefühl war, dass die HashTable die HashMap-Implementierung übertreffen würde, da sie veränderbar ist. In dieser letzten Implementierung ist möglicherweise ein Leistungsfehler verborgen.
quelle
Ein paar Jahre später habe ich mir das angeschaut und festgestellt, dass es eine einfache Möglichkeit gibt, dies in linearer Zeit mithilfe
zipWith
einer Hilfsfunktion zu speichern :dilate
hat die handliche Eigenschaft, dassdilate n xs !! i == xs !! div i n
.Angenommen, wir erhalten f (0), vereinfacht dies die Berechnung auf
Sieht unserer ursprünglichen Problembeschreibung sehr ähnlich und gibt eine lineare Lösung an (
sum $ take n fs
nimmt O (n)).quelle
Noch ein Nachtrag zu Edward Kmotts Antwort: ein in sich geschlossenes Beispiel:
Verwenden Sie es wie folgt, um eine Funktion mit einem einzelnen ganzzahligen Argument (z. B. Fibonacci) zu speichern:
Es werden nur Werte für nicht negative Argumente zwischengespeichert.
Verwenden Sie
memoInt
Folgendes , um auch Werte für negative Argumente zwischenzuspeichern :Verwenden Sie
memoIntInt
Folgendes, um Werte für Funktionen mit zwei ganzzahligen Argumenten zwischenzuspeichern :quelle
Eine Lösung ohne Indizierung und nicht basierend auf Edward KMETTs.
Ich zähle gemeinsame Teilbäume zu einem gemeinsamen Elternteil aus (
f(n/4)
wird zwischenf(n/2)
und geteiltf(n/4)
undf(n/6)
wird zwischenf(2)
und geteiltf(3)
). Durch Speichern als einzelne Variable im übergeordneten Element wird die Berechnung des Teilbaums einmal durchgeführt.Der Code lässt sich nicht leicht auf eine allgemeine Memo-Funktion erweitern (zumindest würde ich nicht wissen, wie es geht), und Sie müssen wirklich darüber nachdenken, wie sich Teilprobleme überschneiden, sondern über die Strategie sollte für allgemeine mehrere nicht ganzzahlige Parameter funktionieren . (Ich habe es mir für zwei String-Parameter ausgedacht.)
Das Memo wird nach jeder Berechnung verworfen. (Wieder dachte ich über zwei String-Parameter nach.)
Ich weiß nicht, ob dies effizienter ist als die anderen Antworten. Jede Suche besteht technisch gesehen nur aus einem oder zwei Schritten ("Sehen Sie sich Ihr Kind oder das Kind Ihres Kindes an"), aber es kann viel zusätzlichen Speicherplatz geben.
Bearbeiten: Diese Lösung ist noch nicht korrekt. Die Freigabe ist unvollständig.Bearbeiten: Es sollte jetzt Unterkinder richtig teilen, aber ich erkannte, dass dieses Problem viele nicht triviale Freigaben hat:
n/2/2/2
undn/3/3
möglicherweise dasselbe ist. Das Problem passt nicht zu meiner Strategie.quelle