class LRU_Cache:
def __init__(self, user_function, maxsize=1024):
# Link layout: [PREV, NEXT, KEY, RESULT]
self.root = root = [None, None, None, None]
self.user_function = user_function
self.cache = cache = {}
last = root
for i in range(maxsize):
key = object()
cache[key] = last[1] = last = [last, root, key, None]
root[0] = last
def __call__(self, *key):
cache = self.cache
root = self.root
link = cache.get(key)
if link is not None:
link_prev, link_next, _, result = link
link_prev[1] = link_next
link_next[0] = link_prev
last = root[0]
last[1] = root[0] = link
link[0] = last
link[1] = root
return result
result = self.user_function(*key)
root[2] = key
root[3] = result
oldroot = root
root = self.root = root[1]
root[2], oldkey = None, root[2]
root[3], oldvalue = None, root[3]
del cache[oldkey]
cache[key] = oldroot
return result
if __name__ == '__main__':
p = LRU_Cache(ord, maxsize=3)
for c in 'abcdecaeaa':
print(c, p(c))
Diff to Previous Revision
--- revision 5 2012-03-17 21:25:12
+++ revision 6 2013-03-06 06:04:18
@@ -1,39 +1,43 @@
class LRU_Cache:
- def __init__(self, original_function, maxsize=1000):
- self.original_function = original_function
- self.maxsize = maxsize
- self.mapping = {}
- self.root = []
- self.root[:] = self.root, self.root, None, None
+ def __init__(self, user_function, maxsize=1024):
+ # Link layout: [PREV, NEXT, KEY, RESULT]
+ self.root = root = [None, None, None, None]
+ self.user_function = user_function
+ self.cache = cache = {}
+
+ last = root
+ for i in range(maxsize):
+ key = object()
+ cache[key] = last[1] = last = [last, root, key, None]
+ root[0] = last
def __call__(self, *key):
- PREV, NEXT = 0, 1
- mapping, root = self.mapping, self.root
-
- link = mapping.get(key, root)
- if link is root:
- value = self.original_function(*key)
- if len(mapping) >= self.maxsize:
- old_prev, old_next, old_key, old_value = root[NEXT]
- root[NEXT] = old_next
- old_next[PREV] = root
- del mapping[old_key]
- last = root[PREV]
- link = [last, root, key, value]
- mapping[key] = last[NEXT] = root[PREV] = link
- else:
- link_prev, link_next, key, value = link
- link_prev[NEXT] = link_next
- link_next[PREV] = link_prev
- last = root[PREV]
- last[NEXT] = root[PREV] = link
- link[PREV] = last
- link[NEXT] = root
- return value
+ cache = self.cache
+ root = self.root
+ link = cache.get(key)
+ if link is not None:
+ link_prev, link_next, _, result = link
+ link_prev[1] = link_next
+ link_next[0] = link_prev
+ last = root[0]
+ last[1] = root[0] = link
+ link[0] = last
+ link[1] = root
+ return result
+ result = self.user_function(*key)
+ root[2] = key
+ root[3] = result
+ oldroot = root
+ root = self.root = root[1]
+ root[2], oldkey = None, root[2]
+ root[3], oldvalue = None, root[3]
+ del cache[oldkey]
+ cache[key] = oldroot
+ return result
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))
+ p = LRU_Cache(ord, maxsize=3)
+ for c in 'abcdecaeaa':
+ print(c, p(c))
