UT Martin Competitive Programming Guidebook

User Tools

Site Tools

Trace:
python3:lru_cache

Differences

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

Link to this comparison view

Both sides previous revision Previous revision
Next revision 		Previous revision
python3:lru_cache [2019/05/07 12:00]
jguerin Started table. 		python3:lru_cache [2019/05/07 12:43] (current)
jguerin
Line 1: Line 1:
-bb====== LRU Cache ======+====== 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]]. 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 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> <file python fibonacci.py>
 def fib(n): def fib(n):
Line 28: Line 31:
  
 ==== Benchmarks ==== ==== Benchmarks ====
-((Python 3.5.2))+The naive recursive implementation fails quickly as expected (at nearly a minute for //n=//40).
  
-^ %%n%%          ^ fibonacci.py          ^ fibonacci_lru.py          ^+^ %%n%%          ^ fibonacci.py((Python 3.5.2))          ^ fibonacci_lru.py          ^
 ^ 10    | .016s     | .0224s        | ^ 10    | .016s     | .0224s        |
-^ 20    | .0216s    | .0232s     |+^ 20    | .0216s    | .0232s        |
 ^ 30    | .4664s    | .0216s        | ^ 30    | .4664s    | .0216s        |
 ^ 40    | -         | .0248s        | ^ 40    | -         | .0248s        |
-^ 50    | -         | .024s        |+^ 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        |
  
python3/lru_cache.1557248428.txt.gz · Last modified: 2019/05/07 12:00 by jguerin

Page Tools

Except where otherwise noted, content on this wiki is licensed under the following license: CC Attribution-Noncommercial-Share Alike 4.0 International
CC Attribution-Noncommercial-Share Alike 4.0 International Donate Powered by PHP Valid HTML5 Valid CSS Driven by DokuWiki