 |
|||
| HSG |
|
Beispiel 1
Anwendung
Problem
Rekursive Berechnungen mit hohem Aufwand - www.inf-schule.de
Lösung
Memoization - das Prinzip
def f(x):
return x*x
fmemo = {}
def fm(x):
if not x in fmemo:
fmemo[x] = x*x
return fmemo[x]
Tests
>>> f(5)
25
>>> fm(5)
25
>>> fm(3)
9
>>> fm(7)
49
>>> fmemo
{3: 9, 5: 25, 7: 49}
>>> fm(3.1)
9.610000000000001
>>> fm(-0.0071)
5.041000000000001e-05
>>> fmemo
{3.1: 9.610000000000001, 3: 9, -0.0071: 5.041000000000001e-05, 5: 25, 7: 49}
Aufgabe
Vergleiche Lösungen mit und ohne Memoizing durch Zeitmessungen.
Links
- Memoisation - wikipedia
- Memoization - wikipedia, engl.
- Assoziatives Array - wikipedia
- dict - Python Library Reference
- Memoizing - Python-recipe