-
Notifications
You must be signed in to change notification settings - Fork 0
/
cached_fibonacci.py
73 lines (52 loc) · 1.72 KB
/
cached_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
71
72
73
import time
class Tools:
def __init__(self):
self.hash_table = dict()
self.args = None
self.kwargs = None
self.hash_key = []
self.log_stack = []
def appendLogStack(self, log):
self.log_stack.append(log)
return self
def appendHashKeyStack(self):
temp_args = self.args or ""
temp_kwargs = self.kwargs or ""
self.hash_key.append(f"{temp_args}{temp_kwargs}")
return self
def updateState(self, **kwargs):
for key in kwargs:
self.appendLogStack(f"KEY: {key} = {kwargs[key]}")
setattr(self, key, kwargs[key])
return self
def updateHashTable(self):
last_hash_key = self.hash_key[-1]
if last_hash_key in self.hash_table:
self.appendLogStack("Already Cached in Hash Table")
return self
self.hash_table[last_hash_key] = self.cached_function(
*self.args, **self.kwargs)
log = f"""
UPDATE:
self.hash_table[{last_hash_key}] = {self.hash_table[last_hash_key]}
"""
self.appendLogStack(log)
return self
def cacheFunc(self, cached_function):
self.cached_function = cached_function
def wrapper(*args, **kwargs):
self.updateState(
args=args,
kwargs=kwargs).appendHashKeyStack().updateHashTable()
return self.hash_table[self.hash_key.pop()]
return wrapper
@Tools().cacheFunc
def fib(n):
if n == 1 or n == 2:
return 1
return fib(n - 1) + fib(n - 2)
if __name__ == "__main__":
start = time.time()
result = fib(int(input("enter: ")))
print(result)
print(f"time: {time.time() - start}")