UT Martin Competitive Programming Guidebook

This page is read only. You can view the source, but not change it. Ask your administrator if you think this is wrong.

====== LRU Cache ======
Memoization is a common optimization technique where repeatedly computed values are cached for quick lookup. While memoization can be achieved by a relatively simple modification to many recursive formulations, Python3's [[https://docs.python.org/3/library/functools.html|functools]] library implements automatic memoization in the form of an LRU (least recently used) cache as a [[https://www.python.org/dev/peps/pep-0318/|function decorator]].


===== The Fibonacci Sequence =====
The [[https://en.wikipedia.org/wiki/Fibonacci_number|Fibonacci]] sequence (//f<sub>n</sub> = f<sub>n-1</sub>+f<sub>n-2</sub>//) is a canonical example of a naive recursive function with exponential complexity.

The naive implementation is exponential. The second example using the LRU cache shows little growth up to moderately large values of //n//.

<file python fibonacci.py>
def fib(n):
    if n < 2:
        return 1
    return fib(n-1) + fib(n-2)

print(fib(40))
</file>

<file python fibonacci_lru.py>
from functools import *

@lru_cache(maxsize=None)

def fib(n):
    if n < 1:
        return n
    return fib(n-1) + fib(n-2)

print(fib(300))
</file>

==== Benchmarks ====
The naive recursive implementation fails quickly as expected (at nearly a minute for //n=//40).

^ %%n%%          ^ fibonacci.py((Python 3.5.2))          ^ fibonacci_lru.py          ^
^ 10    | .016s     | .0224s        |
^ 20    | .0216s    | .0232s        |
^ 30    | .4664s    | .0216s        |
^ 40    | -         | .0248s        |
^ 50    | -         | .024s         |
^ ...   | ...       | ....          |
^ 100   | -         | .0192s        |
^ 200   | -         | .024s         |
^ 300((300 was the chosen cutoff because at 400 we encounter a "maximum recursion depth exceeded" error in Python3. Greater values can be attempted by [[python3:recursion_depth|adjusting the stack limit]].))   | -         | .0232s        |

UT Martin Competitive Programming Guidebook

User Tools

Site Tools

Page Tools