class LRU_Cache:
def __init__(self, original_function, maxsize=1000):
self.original_function = original_function
self.maxsize = maxsize
self.mapping = {}
PREV, NEXT, KEY, VALUE = 0, 1, 2, 3
self.head = [None, None, None, None] # oldest
self.tail = [self.head, None, None, None] # newest
self.head[NEXT] = self.tail
def __call__(self, *key):
PREV, NEXT = 0, 1
mapping, head, tail = self.mapping, self.head, self.tail
link = mapping.get(key, head)
if link is head:
value = self.original_function(*key)
if len(mapping) >= self.maxsize:
old_prev, old_next, old_key, old_value = head[NEXT]
head[NEXT] = old_next
old_next[PREV] = head
del mapping[old_key]
last = tail[PREV]
link = [last, tail, key, value]
mapping[key] = last[NEXT] = tail[PREV] = link
else:
link_prev, link_next, key, value = link
link_prev[NEXT] = link_next
link_next[PREV] = link_prev
last = tail[PREV]
last[NEXT] = tail[PREV] = link
link[PREV] = last
link[NEXT] = tail
return value
if __name__ == '__main__':
p = LRU_Cache(pow, maxsize=3)
for i in [1,2,3,4,5,3,1,5,1,1]:
print(i, p(i, 2))
Diff to Previous Revision
--- revision 1 2011-11-30 20:50:59
+++ revision 2 2011-11-30 21:14:26
@@ -11,18 +11,17 @@
self.head[NEXT] = self.tail
def __call__(self, *key):
- PREV, NEXT, KEY, VALUE = 0, 1, 2, 3
+ PREV, NEXT = 0, 1
mapping, head, tail = self.mapping, self.head, self.tail
link = mapping.get(key, head)
if link is head:
value = self.original_function(*key)
if len(mapping) >= self.maxsize:
- oldest = head[NEXT]
- next_oldest = oldest[NEXT]
- head[NEXT] = next_oldest
- next_oldest[PREV] = head
- del mapping[oldest[KEY]]
+ old_prev, old_next, old_key, old_value = head[NEXT]
+ head[NEXT] = old_next
+ old_next[PREV] = head
+ del mapping[old_key]
last = tail[PREV]
link = [last, tail, key, value]
mapping[key] = last[NEXT] = tail[PREV] = link
