Lektion 5.2

Memoisierung und Tabellen: zwei Wege zur gleichen Lösung

18 min Lesezeit
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.

Definition

Die Fibonacci-Folge

Die Fibonacci-Folge beginnt hier mit F(0)=0F(0)=0 und F(1)=1F(1)=1. Für jede ganze Zahl k≥2k\ge 2 ist F(k)F(k) 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.

F(k)=F(k−1)+F(k−2)(k≥2)F(k)=F(k-1)+F(k-2)\qquad(k\ge 2)
Definition

Memoisierung: von der Frage zu ihren Abhängigkeiten

Memoisierung bedeutet, berechnete Antworten unter ihrem Zustand in einem Speicher abzulegen. Ein Aufruf für F(k)F(k) 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“. F(0)F(0) ist tatsächlich null. Ein Test, der null wie einen fehlenden Eintrag behandelt, ist daher als allgemeine Speicherprüfung ungeeignet.

Beispiel

Ein Aufruf für F(5)F(5)

Wir bearbeiten zuerst immer den Vorgänger F(k−1)F(k-1). Die Rechnung steigt dadurch zunächst über F(4)F(4), F(3)F(3) und F(2)F(2) zu den Anfangswerten ab. Beim Zurückkehren wächst der Speicher.

Neu berechneter WertVerwendete AntwortenGespeichertes Ergebnis
F(2)F(2)F(1)=1F(1)=1, F(0)=0F(0)=01
F(3)F(3)F(2)=1F(2)=1, F(1)=1F(1)=12
F(4)F(4)F(3)=2F(3)=2, F(2)=1F(2)=13
F(5)F(5)F(4)=3F(4)=3, F(3)=2F(3)=25

Wenn der Aufruf für F(4)F(4) später F(2)F(2) benötigt, wird keine weitere vollständige Berechnung von F(2)F(2) 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.

Definition

Tabellierung: von den Anfangswerten zum Ziel

Bei der Tabellierung planen wir die Rechenreihenfolge vorab. Für Fibonacci tragen wir zunächst F(0)F(0) und F(1)F(1) ein. Danach berechnen wir F(2),F(3),…,F(n)F(2),F(3),\ldots,F(n). Diese Vorgehensweise heißt Bottom-up.

Die Reihenfolge muss zu den Abhängigkeiten passen. Wenn F(k)F(k) an der Reihe ist, müssen F(k−1)F(k-1) und F(k−2)F(k-2) 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.

Beispiel

Was beide Wege gemeinsam haben

Für Fibonacci benötigen beide Verfahren alle Zustände von 0 bis nn. Jeder Zustand ab 2 verlangt eine Addition. Wenn wir Additionen und Speicherzugriffe als konstante Schritte zählen, brauchen beide Verfahren O(n)O(n) Zeit.

Mit vollständiger Tabelle speichern beide O(n)O(n) 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 O(n)O(n) 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.

Beispiel

Nur die zwei zuletzt benötigten Werte behalten

Wollen wir ausschließlich F(n)F(n) wissen, brauchen wir die alten Tabellenzeilen nicht vollständig. Für den nächsten Wert genügen zwei Variablen aa und bb. Anfangs stehen sie für F(0)=0F(0)=0 und F(1)=1F(1)=1.

In einem Schritt berechnen wir zuerst c=a+bc=a+b. Danach setzen wir aa auf den bisherigen Wert von bb und bb auf cc. Für das Ziel F(5)F(5) sieht das so aus:

Nach der Berechnung vonaabb
Anfang01
F(2)F(2)11
F(3)F(3)12
F(4)F(4)23
F(5)F(5)35

Für n=0n=0 geben wir direkt 0 zurück; für n=1n=1 direkt 1. Ab n=2n=2 führen wir die beschriebenen Schritte bis nn aus und lesen das Ergebnis aus bb.

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.

Häufige Fehler

Zu frühes Überschreiben verändert die Rechnung

Wer zuerst a=ba=b und anschließend b=a+bb=a+b ausführt, verwendet in der zweiten Anweisung schon den neuen Wert von aa. Statt der beiden verschiedenen alten Werte wird der alte Wert von bb zweimal addiert.

Richtig ist

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

Aufgabe 1Numerisch

Wie groß ist F(8)F(8) bei F(0)=0F(0)=0 und F(1)=1F(1)=1?

Aufgabe 2Multiple Choice

Welche Aussage über Memoisierung trifft zu?

Aufgabe 3Freitext

Warum wäre es bei einer vollständigen Bottom-up-Tabelle für Fibonacci falsch, die Einträge von nn abwärts bis 2 zu berechnen?

Aufgabe 4Numerisch

Vor einem Schritt stehen die Variablen bei a=3a=3 und b=5b=5. Wir berechnen c=a+bc=a+b, danach a=ba=b und b=cb=c. Welchen Wert hat anschließend bb?