# 10.4. Case Study: Memoize¶

## 10.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


## 10.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)


## 10.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)


## 10.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)


## 10.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)


## 10.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)


## 10.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)


## 10.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)


## 10.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)


## 10.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)