-
Notifications
You must be signed in to change notification settings - Fork 0
/
Fibonacci.py
70 lines (62 loc) · 1.89 KB
/
Fibonacci.py
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
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
import time
from functools import lru_cache
end = 40
fibonacci_cache = {}
#no performance using normal way
def fibonacci(n):
#check the input
if type(n) != int:
raise TypeError("n Must be a positive int")
if n < 1:
raise ValueError("n Must be a positive int")
if n == 1:
return 1
elif n == 2:
return 1
elif n > 2:
return fibonacci(n-1) + fibonacci(n-2)
#optimized metod using cache
def fibonacci_memoization(n):
#check the input
if type(n) != int:
raise TypeError("n Must be a positive int")
if n < 1:
raise ValueError("n Must be a positive int")
#if we have cached the value then return it
if n in fibonacci_cache:
return fibonacci_cache[n]
if n == 1:
value = 1
elif n == 2:
value = 1
elif n > 2:
value = fibonacci(n-1) + fibonacci(n-2)
#cache the value and return it
fibonacci_cache[n] = value
return value
#using lru cache from functools improves performance
@lru_cache(maxsize = 1000)
def fibonacci_lru_cache(n):
#check the input
if type(n) != int:
raise TypeError("n Must be a positive int")
if n < 1:
raise ValueError("n Must be a positive int")
if n == 1:
return 1
elif n == 2:
return 1
elif n > 2:
return fibonacci(n-1) + fibonacci(n-2)
time1 = time.time()
for n in range(1, end):
print(n, ":", fibonacci(n), " With Normal Method")
print("Time for normal way", time.time() - time1)
time2 = time.time()
for n in range(1, end):
print(n, ":", fibonacci_memoization(n), " With Memorization Method")
print("Time for Cache way", time.time() - time2)
time3 = time.time()
for n in range(1, end):
print(n, ":", fibonacci_lru_cache(n), " With Memorization LRU Cache Method")
print("Time for Cache LRE way", time.time() - time3)