Factorials

[Jacek Generowicz]

bokr at oz.net (Bengt Richter) writes:

> You could also let the factorial benefit from its own experience, e.g.,
> 
>  >>> def factorial(n, cache={}):
>  ...     fn = cache.get(n)
>  ...     if fn: print 'got cached %s!'%n; return fn
>  ...     if n<2: cache[n]=1; return 1
>  ...     return cache.setdefault(n, n*factorial(n-1))
>  ...

Or, you could let _any_ (keywordless) function benefit from its own
experience:

# General memoizer: takes a function as returns another function which
# has the same semantics as the original, but caches previously
# calculated values
def memoize(callable):
    cache = {}
    def proxy(*args):
        try: return cache[args]
        except KeyError: return cache.setdefault(args, callable(*args))
    return proxy

# A quick and dirty timer utility (timeit module in 2.3 ?), just to
# help us see how we're doing.
import time
def timer(fn, *args):
    start = time.time()
    val = fn(*args)
    stop = time.time()
    print "Took", stop-start, "seconds ..."
    return val

# The function we want to use
def factorial_rec(n):
  if n <= 1:
    return 1
  else:
    return n*factorial_rec(n-1)

# Now, make a cache-enabled version of your function
fact = memoize(factorial_rec)
# ... and use that, instead of the original ...

# See how long the bare function takes
print timer(factorial_rec, 100)

# The first call to the proxy will be slightly slower than the bare function
print timer(fact,100)

# But the second call with the same argument will be much faster
print timer(fact,100)

==================================================
Output:

Took 0.000393986701965 seconds ...
93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000
Took 0.000407934188843 seconds ...
93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000
Took 4.88758087158e-06 seconds ...
93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000