Remind you that decorators cannot memoize (when not using decorator syntax)
I have a simple memoizer decorator:
def funcmemo(f):
memo = {}
@wraps(f)
def wrapper(*args):
if args in memo:
return memo[args]
else:
temp = f(*args)
print "memoizing: ", args, temp
memo[args] = temp
return temp
return wrapper
Now when I use it via the @ token,
@funcmemo
def fib(n):
print "fib called with:", n
if n < 2: return n
return fib(n-2) + fib(n-1)
res = fib(3)
print "result:", res
it works correctly as seen in the printed output:
fib called with: 3
fib called with: 1
memoizing: (1,) 1
fib called with: 2
fib called with: 0
memoizing: (0,) 0
memoizing: (2,) 1
memoizing: (3,) 2
result: 2
However, when I do this:
def fib(n):
print "fib called with:", n
if n < 2: return n
return fib(n-2) + fib(n-1)
memfib = funcmemo(fib)
res = memfib(3)
print "result:", res
Apparently an undecorated fick is called, with only the final return value "reaching" the cache (obviously causing a huge slowdown):
fib called with: 3
fib called with: 1
fib called with: 2
fib called with: 0
fib called with: 1
memoizing: (3,) 2
result: 2
Curiously, this works great:
def fib(n):
print "fib called with:", n
if n < 2: return n
return fib(n-2) + fib(n-1)
fib = funcmemo(fib)
res = fib(3)
print "result:", res
Also, the same happens with the class based version:
class Classmemo(object):
def __init__ (self, f):
self.f = f
self.mem = {}
def __call__ (self, *args):
if args in self.mem:
return self.mem[args]
else:
tmp = self.f(*args)
print "memoizing: ", args, temp
self.mem[args] = tmp
return tmp
The problem also arises when using an "anonymous" decorated function like
res = Classmemo(fib)(3)
I would be glad to know the reasons for this.
source to share
There is nothing curious about this. When you do
memofib = funcmemo(fib)
You don't change the function to fib
point to any side, but create a new function and give it a name memofib
.
Thus, when the call memofib
is called, it calls the function pointed to by the name fib
- which recursively calls itself, not memofib
- so no memoization occurs.
In your second example, you do
fib = funcmemo(fib)
so it calls itself recursively and memoization happens at all levels.
If you don't want to overwrite the name fib
, as the decorator version or your second example, you can change fib
to accept the function name:
def fib(n, fibfunc):
print "fib called with:", n
if n < 2: return n
return fibfunc(n-2, fibfunc) + fibfunc(n-1, fibfunc)
memofib = funcmemo(fib)
res = fib(3, memofib)
You can also use the fixed point combinator to avoid passing fibfunc
every time:
def Y(f):
def Yf(*args):
return f(Yf)(*args)
return f(Yf)
@Y
def fib(f):
def inner_fib(n):
print "fib called with:", n
if n < 2: return n
return f(n-2) + f(n-1)
return inner_fib
source to share