Differences

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

--- python3:lru_cache [2018/11/03 16:38]
jguerin
+++ 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 27: / Line 30: @@
 </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