1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
|
def recursive_fibonacci(n: int) -> int:
if n in [0, 1]:
return n
return recursive_fibonacci(n - 1) + recursive_fibonacci(n - 2)
def recursive_cached_fibonacci(n: int) -> int:
cache = {0: 0, 1: 1}
def fibo(n) -> int:
if n in cache:
return cache[n]
cache[n] = fibo(n - 1) + fibo(n - 2)
return cache[n]
return fibo(n)
def iterative_fibonacci(n: int) -> int:
a, b = 0, 1
for _ in range(n):
a, b = b, a + b
return a
def test_iterative_fibo_10(benchmark):
@benchmark
def _():
iterative_fibonacci(10)
def test_recursive_fibo_10(benchmark):
@benchmark
def _():
recursive_fibonacci(10)
def test_recursive_fibo_20(benchmark):
@benchmark
def _():
recursive_fibonacci(20)
def test_recursive_cached_fibo_10(benchmark):
@benchmark
def _():
recursive_cached_fibonacci(10)
def test_recursive_cached_fibo_100(benchmark):
@benchmark
def _():
recursive_cached_fibonacci(100)
|
