Welcome, guest | Sign In | My Account | Store | Cart

When a function is expensive, it can be interesting to keep in cache the last computed values.

Python, 75 lines
 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)