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
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
from threading import Lock # Linked list updates aren't thread-safe
class Node:
__slots__ = ("key", "val", "prev", "next")
def __init__(self, key, val):
self.key = key
self.val = val
self.prev = None
self.next = None
class pyLRU:
lock = Lock()
maxsize = None
__slots__ = ("function", "cache", "head", "tail", "hits", "miss")
def __init__(self, function):
self.function = function
self.cache = {}
self.head = Node("head", None)
self.tail = Node("tail", None)
self.head.next = self.tail
self.tail.prev = self.head
self.hits = 0
self.miss = 0
def __call__(self, *args, **kwargs):
if args in self.cache:
self._check()
self.hits += 1
self._get(args)
return self.cache[args]
self._check()
result = self.function(*args, **kwargs)
self.cache[args] = result
self.miss += 1
node = Node(args, result)
self._add(node)
return result
def cache_info(self):
return f"CacheInfo(hits={self.hits}, misses={self.miss}, maxsize={self.maxsize}, currsize={len(self.cache)})"
def _check(self):
if self.maxsize is not None and len(self.cache) >= self.maxsize:
node = self.head.next
self._remove(node)
if node.key in self.cache:
del self.cache[node.key]
def _add(self, node):
with self.lock:
p = self.tail.prev
p.next = node
self.tail.prev = node
node.prev = p
node.next = self.tail
def _remove(self, node):
with self.lock:
p = node.prev
n = node.next
p.next = n
n.prev = p
def _get(self, args):
# 부르면 맨 뒤로 업데이트
head = self.head
tail = self.tail
while head and tail:
if head.key == args:
node = head
self._remove(node)
self._add(node)
break
head = head.next
if tail.key == args:
node = tail
self._remove(node)
self._add(node)
break
tail = tail.prev
def print(self):
head = self.head
while head != self.tail:
print(head.key, end=" -> ")
head = head.next
print("tail")
pyLRU.maxsize = 32
FIBO = 250
@pyLRU
def fibo(n):
if n == 1:
return 0
elif n == 2:
return 1
else:
return fibo(n - 1) + fibo(n - 2)
from timeit import default_timer
start = default_timer()
print(fibo(FIBO))
print(f"{default_timer() - start:.5f}s")
print(fibo.cache_info())
fibo.print()
Enter to Rename, Shift+Enter to Preview
