Python: Is math.factorial memoized?

Question

I solve the problem in three different ways, two are recursive, and I remember them myself. The other is not recursive, but uses math.factorial. I need to know if I need to add explicit memoization to it.

Thanks.

Answer 1

Find math_factorial at this link and you will find its implementation in python:

http://svn.python.org/view/python/trunk/Modules/mathmodule.c?view=markup

PS This is for python2.6

Answer 2

Python math.factorial is not memoized, it's a simple loop that multiplies values ​​from 1 to your argument. If you need memoization, you need to do it explicitly.

Here is an easy way to memoize using the setdefault dictionary method.

import math cache = {} def myfact(x): return cache.setdefault(x,math.factorial(x)) print myfact(10000) print myfact(10000) 

Answer 3

Python math.factorial is not saved.

I will tell you about some examples of trial and error in order to understand why in order to get a truly memorialized and working factorial function, you need to redefine it ex-novo with a few things in mind.

The other answer is actually incorrect. Here,

 import math cache = {} def myfact(x): return cache.setdefault(x,math.factorial(x)) 

line

 return cache.setdefault(x,math.factorial(x)) 

calculates both x and math.factorial(x) each time, and therefore you do not improve performance.

You can come up with something like this:

 if x not in cache: cache[x] = math.factorial(x) return cache[x] 

but actually it’s wrong. Yes, you should not calculate the factorial of the same x again, but think, for example, if you are going to calculate myfact(1000) and soon after that myfact(999) . Both of them are fully computed, so they get no advantage because myfact(1000) automatically calculates myfact(999) .

It is natural then to write something like this:

 def memoize(f): """Returns a memoized version of f""" memory = {} def memoized(*args): if args not in memory: memory[args] = f(*args) return memory[args] return memoized @memoize def my_fact(x): assert x >= 0 if x == 0: return 1 return x * my_fact(x - 1) 

That will work. Unfortunately, it soon reaches the maximum depth of recursion.

So how to implement it?

Here is an example of a truly memoized factorial that uses how factorials work and do not consume the entire stack with recursive calls:

 # The 'max' key stores the maximum number for which the factorial is stored. fact_memory = {0: 1, 1: 1, 'max': 1} def my_fact(num): # Factorial is defined only for non-negative numbers assert num >= 0 if num <= fact_memory['max']: return fact_memory[num] for x in range(fact_memory['max']+1, num+1): fact_memory[x] = fact_memory[x-1] * x fact_memory['max'] = num return fact_memory[num] 

I hope you find this helpful.

EDIT:

As a note, a way to achieve the same optimization, at the same time, brevity and elegance of recursion would be to redefine the function as a tail- recursive function .

 def memoize(f): """Returns a memoized version of f""" memory = {} def memoized(*args): if args not in memory: memory[args] = f(*args) return memory[args] return memoized @memoize def my_fact(x, fac=1): assert x >= 0 if x < 2: return fac return my_fact(x-1, x*fac) 

Tail recursion functions can actually be recognized by the interpreter / compiler and automatically translated / optimized into the iterative version, but not all interpreters / compilers support this.

Unfortunately, python does not support tail recursion optimization, so you still get:

 RuntimeError: maximum recursion depth exceeded 

when my_fact input is high.

Answer 4

I'm late to the party, but here are my 2c on implementing an effective memoized factorial function in Python. This approach is more efficient, as it relies on a massive structure (i.e. list ), rather than a hashed container (i.e. dict ). Recursion is not involved (you have some overhead for the Python function) and slow loops are not involved. And it is (possibly) functionally pure, since there are no external side effects (that is, it does not change the global variable). It caches all intermediate factorials, so if you have already calculated factorial(n) , you will need O (1) to calculate factorial(m) for any 0 <= m <= n and O (mn) for any m> n.

 def inner_func(f): return f() @inner_func def factorial(): factorials = [1] def calculate_factorial(n): assert n >= 0 return reduce(lambda cache, num: (cache.append(cache[-1] * num) or cache), xrange(len(factorials), n+1), factorials)[n] return calculate_factorial