Memoisierung und Tabellen: zwei Wege zur gleichen Lösung
Lesen anpassen
Nach dieser Lektion kannst du
Memoisierung und Tabellierung an derselben Rekurrenz unterscheiden.
Eine Reihenfolge wählen, in der Abhängigkeiten schon berechnet sind.
Zeitaufwand, gespeicherte Werte und Rekursionsspeicher getrennt betrachten.
Vorausgesetzt: Teilprobleme erkennen und Ergebnisse wiederverwenden
In der vorigen Lektion haben wir Schrittfolgen für eine Treppe gezählt. Die Frage „Wie viele Wege führen zu Stufe sechs?“ führte mehrfach zur Frage nach Stufe vier. Diese Wiederholung lässt sich auf zwei Arten vermeiden.
Du kannst die große Frage stellen und jede Antwort auf eine kleinere Frage sofort aufbewahren. Oder du rechnest die kleinen Fragen von Anfang an in einer passenden Reihenfolge aus. Beides verwendet dieselben Teilprobleme und dieselbe Rechenregel.
Wir untersuchen beide Vorgehensweisen zunächst an einer bekannten Zahlenfolge. So können wir den Unterschied am Ablauf erkennen, ohne gleichzeitig ein neues Anwendungsproblem lösen zu müssen.
Die Fibonacci-Folge
Die Fibonacci-Folge beginnt hier mit und . Für jede ganze Zahl ist die Summe ihrer beiden Vorgänger. Die ersten Werte sind also 0, 1, 1, 2, 3, 5, 8.
Diese Anfangswerte unterscheiden sich von den Treppenzahlen der vorigen Lektion. Wir dürfen die Tabellen deshalb nicht unverändert austauschen. Gleich ist die Form der Rekurrenz: Jeder neue Wert hängt von zwei kleineren Werten ab.
Memoisierung: von der Frage zu ihren Abhängigkeiten
Memoisierung bedeutet, berechnete Antworten unter ihrem Zustand in einem Speicher abzulegen. Ein Aufruf für prüft zuerst, ob der Wert bereits vorliegt. Wenn ja, gibt er ihn sofort zurück. Andernfalls berechnet er die nötigen kleineren Werte, addiert sie und speichert die neue Antwort.
Diese Vorgehensweise heißt auch Top-down, weil sie mit der ursprünglichen Frage beginnt und zu den benötigten kleineren Fragen hinabgeht. Die Anfangswerte 0 und 1 werden direkt beantwortet oder vorab im Speicher abgelegt.
Wichtig ist die Unterscheidung zwischen „nicht gespeichert“ und „gespeichert mit Wert null“. ist tatsächlich null. Ein Test, der null wie einen fehlenden Eintrag behandelt, ist daher als allgemeine Speicherprüfung ungeeignet.
Ein Aufruf für
Ein Aufruf für
Wir bearbeiten zuerst immer den Vorgänger . Die Rechnung steigt dadurch zunächst über , und zu den Anfangswerten ab. Beim Zurückkehren wächst der Speicher.
| Neu berechneter Wert | Verwendete Antworten | Gespeichertes Ergebnis |
|---|---|---|
| , | 1 | |
| , | 2 | |
| , | 3 | |
| , | 5 |
Wenn der Aufruf für später benötigt, wird keine weitere vollständige Berechnung von gestartet. Sein Ergebnis wird direkt gelesen.
Mit Memoisierung darf ein Zustand durchaus mehrfach angefragt werden. Entscheidend ist, dass seine eigentliche Berechnung nur einmal stattfindet. Ein Speicherzugriff ist etwas anderes als das erneute Lösen des Teilproblems.
Tabellierung: von den Anfangswerten zum Ziel
Bei der Tabellierung planen wir die Rechenreihenfolge vorab. Für Fibonacci tragen wir zunächst und ein. Danach berechnen wir . Diese Vorgehensweise heißt Bottom-up.
Die Reihenfolge muss zu den Abhängigkeiten passen. Wenn an der Reihe ist, müssen und schon vorliegen. Ein Durchlauf von großen zu kleinen Indizes würde das nicht leisten.
Allgemein kann man Zustände als Punkte und die benötigten Antworten als Verbindungen darstellen. Eine gültige Auswertungsreihenfolge löst die Voraussetzungen eines Zustands vor dem Zustand selbst. Eine unveränderte Rekurrenz mit einem Kreis solcher Abhängigkeiten lässt sich auf diese Weise nicht einfach von Anfangswerten aus auswerten.
Was beide Wege gemeinsam haben
Was beide Wege gemeinsam haben
Für Fibonacci benötigen beide Verfahren alle Zustände von 0 bis . Jeder Zustand ab 2 verlangt eine Addition. Wenn wir Additionen und Speicherzugriffe als konstante Schritte zählen, brauchen beide Verfahren Zeit.
Mit vollständiger Tabelle speichern beide Werte. Die rekursive Variante braucht zusätzlich einen Aufrufstapel: Dort merkt sich das Programm, welche Aufrufe nach der Rückkehr aus einem kleineren Aufruf fortgesetzt werden müssen. Die tiefste Kette kann hier lang sein.
Bei anderen Problemen kann Memoisierung vorteilhaft sein, wenn von der Ausgangsfrage nur wenige der theoretisch möglichen Zustände erreichbar sind. Eine vollständig ausgefüllte Tabelle würde dann auch unnötige Zustände bearbeiten.
Bottom-up ist nicht automatisch eine bessere asymptotische Laufzeitklasse. Unterschiede entstehen durch die tatsächlich besuchten Zustände, den Aufwand pro Zustand und den Speicher für den Ablauf. Bei sehr großen Fibonacci-Zahlen muss zusätzlich die Länge der gespeicherten Zahlen berücksichtigt werden.
Nur die zwei zuletzt benötigten Werte behalten
Nur die zwei zuletzt benötigten Werte behalten
Wollen wir ausschließlich wissen, brauchen wir die alten Tabellenzeilen nicht vollständig. Für den nächsten Wert genügen zwei Variablen und . Anfangs stehen sie für und .
In einem Schritt berechnen wir zuerst . Danach setzen wir auf den bisherigen Wert von und auf . Für das Ziel sieht das so aus:
| Nach der Berechnung von | ||
|---|---|---|
| Anfang | 0 | 1 |
| 1 | 1 | |
| 1 | 2 | |
| 2 | 3 | |
| 3 | 5 |
Für geben wir direkt 0 zurück; für direkt 1. Ab führen wir die beschriebenen Schritte bis aus und lesen das Ergebnis aus .
Wir benötigen eine konstante Anzahl gespeicherter Zahlen. Das heißt nicht, dass ihre Darstellung eine konstante Zahl von Bits beansprucht. Außerdem stehen nachher die früheren Folgenglieder nicht mehr zum Nachschlagen zur Verfügung.
Zu frühes Überschreiben verändert die Rechnung
Zu frühes Überschreiben verändert die Rechnung
Wer zuerst und anschließend ausführt, verwendet in der zweiten Anweisung schon den neuen Wert von . Statt der beiden verschiedenen alten Werte wird der alte Wert von zweimal addiert.
Berechne die Summe zunächst in einer Hilfsvariablen oder verwende eine gleichzeitige Zuweisung, deren rechte Seite vollständig mit den alten Werten ausgewertet wird. Begründe jede Speicheroptimierung damit, welche alten Werte noch gebraucht werden.
Zusammenfassung
Memoisierung beginnt bei der Ausgangsfrage, berechnet benötigte Abhängigkeiten und merkt sich die Antworten.
Tabellierung beginnt bei Anfangswerten und folgt einer vorher festgelegten gültigen Reihenfolge.
Beide Verfahren können dieselbe Rekurrenz mit derselben Laufzeitklasse auswerten.
Bei rekursiven Verfahren gehört der Aufrufstapel zur Speicherbilanz.
Speicher darf erst überschrieben werden, wenn kein zukünftiger Schritt den alten Wert benötigt.
Übungen
Wie groß ist bei und ?
Welche Aussage über Memoisierung trifft zu?
Warum wäre es bei einer vollständigen Bottom-up-Tabelle für Fibonacci falsch, die Einträge von abwärts bis 2 zu berechnen?
Vor einem Schritt stehen die Variablen bei und . Wir berechnen , danach und . Welchen Wert hat anschließend ?