Differences

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

--- python3:lru_cache [2019/05/07 12:09]
jguerin Removed mistype.
+++ python3:lru_cache [2019/05/07 12:43] (current)
jguerin
@@ Line 4: / Line 4: @@
 ===== 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 28: / Line 31: @@
 ==== 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        |
 ^ 20    | .0216s    | .0232s        |
@@ Line 39: / Line 42: @@
 ^ 100   | -         | .0192s        |
 ^ 200   | -         | .024s         |
-^ 300   | -         | .0232s        |
+^ 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