Differences

This shows you the differences between two versions of the page.

--- python3:lru_cache [2018/11/03 16:30]
jguerin
+++ python3:lru_cache [2019/05/07 12:43] (current)
jguerin
@@ Line 1: / Line 1: @@
 ====== 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.
+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 [[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):
@@ Line 14: / Line 17: @@
 </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

Differences

Page Tools