[BangPypers] python speed comparison

[Dhananjay Nene]

On Mon, Aug 9, 2010 at 3:59 PM, Emil Chacko <emilchacko at 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