8.4. Case Study: Memoize¶
8.4.1. Recap¶
Recap information about factorial (n!
):
5! = 5 * 4!
4! = 4 * 3!
3! = 3 * 2!
2! = 2 * 1!
1! = 1 * 0!
0! = 1
factorial(5) # = 120
return 5 * factorial(4) # 5 * 24 = 120
return 4 * factorial(3) # 4 * 6 = 24
return 3 * factorial(2) # 3 * 2 = 6
return 2 * factorial(1) # 2 * 1 = 2
return 1 * factorial(0) # 1 * 1 = 1
return 1 # 1
8.4.2. No Cache¶
>>> #%%timeit -r 1000 -n 10_000
>>> def factorial(n: int) -> int:
... if n == 0:
... return 1
... else:
... return n * factorial(n-1)
>>>
>>>
>>> factorial(50)
>>> factorial(40)
>>> factorial(45)
283 µs ± 6.63 µs per loop (mean ± std. dev. of 1000 runs, 10000 loops each)
8.4.3. Global Scope¶
>>> _cache = {}
>>>
>>> def cache(func):
... def wrapper(n):
... if n not in _cache:
... _cache[n] = func(n)
... return _cache[n]
... return wrapper
>>>
>>>
>>> @cache
... def factorial(n):
... if n == 0:
... return 1
... else:
... return n * factorial(n-1)
>>>
>>>
>>> factorial(50)
>>> factorial(40)
>>> factorial(45)
8.4.4. Local Scope¶
>>> def cache(func):
... _cache = {}
... def wrapper(n):
... if n not in _cache:
... _cache[n] = func(n)
... return _cache[n]
... return wrapper
>>>
>>>
>>> @cache
... def factorial(n):
... if n == 0:
... return 1
... else:
... return n * factorial(n-1)
>>>
>>>
>>> factorial(50)
>>> factorial(40)
>>> factorial(45)
8.4.5. Embedded Scope¶
>>> def cache(func):
... def wrapper(n):
... if n not in wrapper._cache:
... wrapper._cache[n] = func(n)
... return wrapper._cache[n]
... if not hasattr(wrapper, '_cache'):
... setattr(wrapper, '_cache', {})
... return wrapper
>>>
>>>
>>> @cache
... def factorial(n: int) -> int:
... if n == 0:
... return 1
... else:
... return n * factorial(n-1)
>>>
>>>
>>> factorial(50)
>>> factorial(40)
>>> factorial(45)
8.4.6. Contains¶
>>> #%%timeit -r 1000 -n 10_000
>>> _cache = {}
>>>
>>> def factorial(n: int) -> int:
... if n in _cache:
... return _cache[n]
... if n == 0:
... return 1
... else:
... result = _cache[n] = n * factorial(n-1)
... return result
>>>
>>>
>>> factorial(50)
>>> factorial(40)
>>> factorial(45)
153 µs ± 2.49 µs per loop (mean ± std. dev. of 1000 runs, 10000 loops each)
8.4.7. Get¶
>>> #%%timeit -r 1000 -n 10_000
>>> _cache = {}
>>>
>>> def factorial(n: int) -> int:
... result = _cache.get(n)
... if result:
... return result
... if n == 0:
... return 1
... else:
... result = _cache[n] = n * factorial(n-1)
... return result
>>>
>>>
>>> factorial(50)
>>> factorial(40)
>>> factorial(45)
181 µs ± 10.3 µs per loop (mean ± std. dev. of 1000 runs, 10000 loops each)
8.4.8. Exceptions¶
>>> #%%timeit -r 1000 -n 10_000
>>> _cache = {}
>>>
>>> def factorial(n: int) -> int:
... if n == 0:
... return 1
... try:
... return _cache[n]
... except KeyError:
... _cache[n] = result = n * factorial(n-1)
... return result
>>>
>>>
>>> factorial(50)
>>> factorial(40)
>>> factorial(45)
618 µs ± 6.6 µs per loop (mean ± std. dev. of 1000 runs, 10000 loops each)
8.4.9. Layer¶
>>> #%%timeit -r 1000 -n 10_000
>>> _cache = {}
>>>
>>> def fac(n: int) -> int:
... def factorial(n: int) -> int:
... if n == 0:
... return 1
... return n * factorial(n-1)
... if not n in _cache:
... _cache[n] = factorial(n)
... return _cache[n]
>>>
>>>
>>> fac(50)
>>> fac(40)
>>> fac(45)
283 µs ± 6.44 µs per loop (mean ± std. dev. of 1000 runs, 10000 loops each)
Get from cache
>>> #%%timeit -r 1000 -n 10_000
>>> _cache = {}
>>>
>>> def factorial(n: int) -> int:
... if n == 0:
... return 1
... if n in _cache:
... return _cache[n]
... result = _cache[n] = n * factorial(n-1)
... return result
>>>
>>>
>>> factorial(50)
>>> factorial(40)
>>> factorial(45)
153 µs ± 9.64 µs per loop (mean ± std. dev. of 1000 runs, 10000 loops each)
8.4.10. Assignment Expression¶
>>> #%%timeit -r 1000 -n 10_000
>>> _cache = {}
>>>
>>> def factorial(n):
... if n == 0:
... return 1
... if (result := _cache.get(n)):
... return result
... result = n * factorial(n-1)
... _cache[n] = result
... return result
>>>
>>>
>>> factorial(50)
>>> factorial(40)
>>> factorial(45)
153 µs ± 9.64 µs per loop (mean ± std. dev. of 1000 runs, 10000 loops each)