Wie man eine langsame Rekursion schnell macht
Memoisation bedeutet, das Ergebnis eines Funktionsaufrufs zu merken, damit derselbe Aufruf nie ein zweites Mal gerechnet wird. Eine rekursive Funktion, die Millionen Aufrufe braucht, kommt dann mit einigen Dutzend aus.
Ein Getränkeautomat soll einen Betrag in möglichst wenige Wertmarken wechseln. Ohne Merken rechnet er dieselben Teilbeträge immer wieder.
Am Ende dieser Lektion
Notiz
Ich kann eine langsame Rekursion mit einer Merktabelle beschleunigen.
Schlüsselwörter
| Begriff | Was er bedeutet | Beispiel |
|---|---|---|
| Memoisation | Ergebnisse von Aufrufen merken und wiederverwenden | |
| Merktabelle | ein Wörterbuch, das Eingabe und Ergebnis speichert | merke[10] = 55 |
| Teilproblem | ein kleineres Problem, das zum großen gehört | |
| Dynamische Programmierung | ein großes Problem aus gemerkten Teilproblemen lösen | |
| Gieriges Verfahren | immer die jetzt beste Wahl treffen |
Die Zellen, die Lernende ausfüllen, bleiben in dieser Vorschau leer.
Dieselbe Arbeit wird immer wieder getan
Wenn fib(6) gerechnet wird, ruft es fib(5) und fib(4) auf. Auch fib(5) ruft wieder fib(4) auf, und das rechnet alles noch einmal.
Der Code zählt, wie oft jedes fib(k) aufgerufen wird. Diese Wiederholung ist die Verschwendung. Genau sie lässt sich vermeiden.
Wie oft jedes fib(k) vorkommt
# Wie oft wird jedes fib(k) gerechnet, wenn wir fib(6) wollen?
anzahl = {}
def fib(n):
if n in anzahl:
anzahl[n] = anzahl[n] + 1
else:
anzahl[n] = 1
if n < 2:
return n
return fib(n - 1) + fib(n - 2)
print("fib(6) =", fib(6))
for k in range(7):
print("fib(", k, ") wurde", anzahl[k], "mal aufgerufen")
# Aendern Sie 6 auf 8. Welche Zeile waechst am staerksten?
Die Aufrufe bei fib(6)
| Aufruf | Wie oft gerechnet | Wie oft nötig |
|---|---|---|
| fib(6) | 1 | 1 |
| fib(5) | 1 | 1 |
| fib(4) | 2 | 1 |
| fib(3) | 3 | 1 |
| fib(2) | 5 | 1 |
| fib(1) | 8 | 1 |
| fib(0) | 5 | 1 |
Die Zellen, die Lernende ausfüllen, bleiben in dieser Vorschau leer.
Eine Merktabelle schlägt nach, statt neu zu rechnen
Die Merktabelle ist ein Wörterbuch. Der Schlüssel ist die Eingabe, der Wert das Ergebnis. Die Funktion schaut zuerst nach. Steht die Eingabe schon darin, gibt sie das Ergebnis sofort zurück.
Sonst rechnet sie, trägt das Ergebnis ein und gibt es zurück. Jedes Teilproblem wird so nur einmal gerechnet. Aus 2.692.537 Aufrufen bei fib(30) werden 59.
fib mit Merktabelle
# Dieselbe Funktion, aber mit einer Merktabelle (einem Woerterbuch).
merke = {}
aufrufe = [0]
def fib(n):
aufrufe[0] = aufrufe[0] + 1
if n in merke:
return merke[n] # schon gerechnet: nur nachschlagen
if n < 2:
ergebnis = n
else:
ergebnis = fib(n - 1) + fib(n - 2)
merke[n] = ergebnis
return ergebnis
for n in [10, 20, 30]:
merke = {}
aufrufe[0] = 0
print("fib(", n, ") =", fib(n), "Aufrufe:", aufrufe[0])
# Ohne Merktabelle waren es 177, 21891 und 2692537 Aufrufe.
Im Lab: dieselben Zahlen mit einer Schleife
Man kann die Merktabelle auch von unten füllen: erst fib(0), dann fib(1), und jedes weitere aus den beiden davor. Das ist die dynamische Programmierung.
Die Befehle bauen die Tabelle in einer Schleife und geben einen Wert aus. Für fib(30) sind das nur 29 Additionen.
fib(30) in einer Schleife
python3 -c "t = [0, 1]; exec('for i in range(2, 31): t.append(t[i - 1] + t[i - 2])'); print(t[30])"Hier angezeigt, nicht ausgeführt. Erstellen Sie ein kostenloses Konto, um „Ausführen“ zu drücken und ihn im Terminal Ihres eigenen Labs einzugeben.
fib(90) in einer Schleife
python3 -c "t = [0, 1]; exec('for i in range(2, 91): t.append(t[i - 1] + t[i - 2])'); print(t[90])"Hier angezeigt, nicht ausgeführt. Erstellen Sie ein kostenloses Konto, um „Ausführen“ zu drücken und ihn im Terminal Ihres eigenen Labs einzugeben.
Wechselgeld mit den wenigsten Marken
Ein Automat hat Marken zu 1, 3 und 4. Wie wechselt er 6 in möglichst wenige Marken? Die Teilprobleme heißen: die wenigsten Marken für jeden kleineren Betrag.
Für einen Betrag b probiert er jede Marke aus. Er nimmt die Marke und fragt nach den wenigsten Marken für den Rest. Die beste Wahl plus 1 ist die Antwort.
Wenigste Marken für Beträge 0 bis 8
| Betrag | Beste Wahl | Wenigste Marken |
|---|---|---|
| 0 | keine | 0 |
| 1 | 1 | 1 |
| 2 | 1 + 1 | 2 |
| 3 | 3 | 1 |
| 4 | 4 | 1 |
| 5 | 4 + 1 | 2 |
| 6 | 3 + 3 | 2 |
| 7 | 3 + 4 | 2 |
| 8 | 4 + 4 | 2 |
Die Zellen, die Lernende ausfüllen, bleiben in dieser Vorschau leer.
Die wenigsten Marken mit Merktabelle
# Wechselgeld: die wenigsten Marken fuer einen Betrag, Marken zu 1, 3 und 4.
marken = [1, 3, 4]
merke = {}
def wenigste(betrag):
if betrag == 0:
return 0
if betrag in merke:
return merke[betrag]
beste = 1000
for wert in marken:
if wert <= betrag:
versuch = 1 + wenigste(betrag - wert)
if versuch < beste:
beste = versuch
merke[betrag] = beste
return beste
for betrag in [6, 7, 8]:
print("Betrag", betrag, ":", wenigste(betrag), "Marken")
# Aendern Sie die Marken auf [1, 5, 12] und den Betrag auf 15.
Ein häufiger Fehler
Warnung
Viele denken, es genüge, immer die größte passende Marke zu nehmen. Für 6 ergibt das 4, 1 und 1, also drei Marken. Mit 3 und 3 sind es nur zwei. Ein gieriges Verfahren ist nicht immer das beste. Die Tabelle der Teilprobleme probiert alle Wege.
Weiterführend
Ändern Sie wenigste_muenzen so, dass es nicht nur die Zahl zurückgibt, sondern auch die Liste der Münzen. Merken Sie sich dazu in der Tabelle für jeden Betrag die gewählte Münze.
Rechnen Sie dann von Hand nach, ob bei 63 mit den Marken 1, 3 und 4 wirklich 16 Marken nötig sind.