Python: math.factorial 是缓存的吗？

Question

我正在用三种不同的方法解决一个问题，其中两种是递归的方法，我自己做了记忆化处理。另一种方法不是递归的，而是用到了数学中的阶乘函数。我想知道我是否需要给它加上明确的记忆化处理。

谢谢。

Answer 1

Python的math.factorial函数并没有使用缓存。

我将通过一些尝试和错误的例子来告诉你，为什么要想要一个真正有缓存功能的阶乘函数，你需要从头开始重新定义它，并考虑一些因素。

其实之前的回答并不正确。在这里，

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

这一行

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

每次都会计算和，所以你并没有获得任何性能上的提升。

你可能会想这样做：

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

但实际上这也是错误的。是的，你避免了对同一个重复计算阶乘，但想想看，比如你要计算，然后很快又要计算。这两个计算都是完全独立的，所以并没有利用到自动计算的优势。

那么自然就会想到写成这样：

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)

这样是可以工作的。不幸的是，它很快就会达到最大递归深度。

那么该怎么实现呢？

这里有一个真正有缓存功能的阶乘例子，它利用了阶乘的特性，并且不会因为递归调用而耗尽所有的栈空间：

# 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]

希望你觉得这个有用。

编辑：

作为一个补充，有一种方法可以在保持递归的简洁和优雅的同时实现相同的优化，那就是将函数重新定义为尾递归函数。

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)

尾递归函数实际上可以被解释器或编译器识别，并自动转换或优化为迭代版本，但并不是所有的解释器或编译器都支持这个。

不幸的是，Python并不支持尾递归优化，所以当的输入很高时，你仍然会遇到：

RuntimeError: maximum recursion depth exceeded

的问题。

Answer 2

Python里的math.factorial函数并没有使用缓存，它只是一个简单的循环，把从1到你输入的数字的值都乘起来。如果你需要缓存功能，那你得自己去实现。

下面是一个简单的方法，可以用字典的setdefault方法来实现缓存。

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

Answer 3

在这个链接上搜索 math_factorial，你会找到它在 Python 中的实现：

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

附注：这是针对 Python 2.6 的内容。