When a function is expensive, it can be interesting to keep in cache the last computed values.
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 | import weakref
class DoubleNode:
"""node for a double linked list """
previous = None
next = None
def __init__(self, value):
self.value = value
def extract(self):
previous = self.previous
next = self.next
if previous:
previous.next = next
if next:
next.previous = previous
self.next = self.previous = None
def insert_after(self, node):
self.next = node.next
self.previous = node
node.next.previous = self
node.next = self
class BufferCache:
"""Store data in a double linked list..."""
count = 0
def __init__(self, function, capacity=50):
self.cache = weakref.WeakValueDictionary()
self.next = self.previous = self
self.function = function
self.capacity = capacity
def _append(self, value):
""" append a node for a new value """
node = DoubleNode(value)
node.insert_after(self.previous)
if self.count == self.capacity:
self.next.extract()
else:
self.count += 1
return node
def _value(self, node):
"""return the value and put the node as the first one"""
node.extract()
node.insert_after(self.previous)
return node.value
def __call__(self, *args):
try:
node = self.cache[args]
except KeyError:
x = self.function(*args)
self.cache[args] = self._append(x)
else:
x = self._value(node)
return x
def __repr__(self):
i = self.previous
s = ""
while i!=self:
s = s + repr(i.value) + " "
i = i.previous
return s
#
# sample
#
def foo(x):
print "computing"
return "*" + str(x)
foo_cache = BufferCache(foo,5)
for i in range(5):
print foo_cache(i)
print foo_cache(2)
|
The BufferCache class keep in memory the last values returned by a stateless function. Theses values are stored in a double linked list which act as a ring buffer but allow to move reused values at the start of the buffer.
It also use a dictionnary for retrieving the list node from functions arguments. Since it would be useless to store reference to node wich have been removed from the ring buffer, the dictionnary is a WeakValueDictionary (see weekref module) wich automaticaly remove objects which refcount reach 0.
Since the recipe use a dictionnary, all the function arguments must be hashable. If you need to work for sample with list arguments, you will have to find an other way to retrieve the node from functions arguments.
You could also make the _append method faster by using the RingBuffer (http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/68429) recipe when the number of nodes reach the buffer capacity.
See also the Memoizing recipe (http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/52201)