def cache_generator(original_function, maxsize):
mapping = {}
mapping_get = mapping.get
sentinel = object()
value = None
size = 0
PREV, NEXT, KEY, VALUE = range(4)
startnode = [None, None, None, None] # oldest
endnode = [startnode, None, None, None] # newest
startnode[NEXT] = endnode
while 1:
key = yield value
link = mapping_get(key, sentinel)
if link is sentinel:
value = original_function(key)
last = endnode[PREV]
last[NEXT] = endnode[PREV] = mapping[key] = [last, endnode, key, value]
if size >= maxsize:
oldest = startnode[NEXT]
next_oldest = oldest[NEXT]
startnode[NEXT] = next_oldest
next_oldest[PREV] = startnode
del mapping[oldest[KEY]]
else:
size += 1
else:
link_prev, link_next, key, value = link
link_prev[NEXT] = link_next
link_next[PREV] = link_prev
last = endnode[PREV]
last[NEXT] = endnode[PREV] = link
link[PREV] = last
link[NEXT] = endnode
def make_cache(original_function, maxsize=100):
'Create a cache around a function that takes a single argument'
c = cache_generator(original_function, maxsize)
next(c)
return c.send
if __name__ == '__main__':
p = make_cache(ord, maxsize=3)
for c in 'abcdecaeaa':
print(c, p(c))
Diff to Previous Revision
--- revision 1 2011-11-30 00:50:55
+++ revision 2 2011-11-30 20:26:09
@@ -16,7 +16,7 @@
value = original_function(key)
last = endnode[PREV]
last[NEXT] = endnode[PREV] = mapping[key] = [last, endnode, key, value]
- if size > maxsize:
+ if size >= maxsize:
oldest = startnode[NEXT]
next_oldest = oldest[NEXT]
startnode[NEXT] = next_oldest
