Python: math.factorial被记忆了吗？

Question

我正在用三种不同的方法解决problem，其中两种是递归的，我自己记忆它们。另一种不是递归的，而是使用math.factorial。我需要知道我是否需要向它添加显式的memoization。

谢谢。

Answer 1

在这个链接上搜索math_factorial，你会发现它在python中的实现：

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

附言:这是针对python2.6的

Answer 2

Python的math.factorial没有被记忆，它是一个简单的for循环，将值从1乘以您的arg。如果你需要memoization，你需要显式的去做。

下面是一种使用字典setdefault方法进行记忆的简单方法。

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

Answer 3

Python的math.factorial没有被记忆。

我将通过一些试验和错误的例子来指导你，看看为什么要得到一个真正记忆的和有效的阶乘函数，你必须重新定义它，考虑到一些事情。

另一个答案实际上是不正确的。这里,

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

这条线

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

每次都会同时计算x和math.factorial(x)，因此不会获得任何性能改进。

您可能会考虑这样做：

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

但实际上这也是错误的。是的，你避免再次计算同一个x的阶乘，但是想一想，例如，如果你要计算myfact(1000)，然后很快计算myfact(999)。它们都是完全计算出来的，因此没有利用myfact(1000)自动计算myfact(999)这一事实。

然后很自然地就会写出这样的东西：

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]

我希望这对你有用。

编辑：

需要注意的是，要实现同样的优化，同时又具有递归的简洁性和优雅，一种方法是将函数重新定义为tail-recursive函数。

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

当my_fact的输入为高电平时。