On Mon, Aug 9, 2010 at 3:59 PM, Emil Chacko <emilcha...@gmail.com> wrote:
> This implementation is really good.It's really fast compared to the initial
> one I posted but i didn't understand much about this memoize.I asked one of
> my friend he told it's python decorators.Can anyone please explain what the
> function memoize does.
>
>
Commented code follows :
#memoize is a decorator around the function f (wrapper function)
def memoize(f):
# declare a cache to store prior results
cache = {}
# g is the wrapper function which takes the input number a
def g(a):
# Check if f had earlier been called with the value a
# If it had been called, a will be a key in the cache dict
if a not in cache:
# Now we know f had not been called earlier for the value a
# Hence invoke the function f for value a and capture the
# return value of the same as a value in the cache for the key
# value of a
cache[a] = f(a)
# return the computed or the cached value for a
return cache[a]
# Return the wrapper g
# This is triggered when the @memoize directive is observed.
# It for practical purposes replaces the wrapped function 'f' which
subsequently in
# this example is 'solve' by this function 'g' which in turn internally
calls
# 'a' or 'solve' in this case
return g
# trigger the function wrapping by using a decorator
@memoize
def solve(n):
if n == 1:
return 1
elif n%2 == 0:
return 1 + solve(n/2)
else:
return 1 + solve(3*n+1)
# use solve as you otherwise might have done
# (the decoration / memoisation / wrapping is transparent)
print max((solve(i), i) for i in range(1, 1+1000000))
--
--------------------------------------------------------
blog: http://blog.dhananjaynene.com
twitter: http://twitter.com/dnene
_______________________________________________
BangPypers mailing list
BangPypers@python.org
http://mail.python.org/mailman/listinfo/bangpypers
