时间戳

首页 > 解决方案 > 如何提高组合递归函数的性能？

python - 如何提高组合递归函数的性能？

问题描述

计算组合如下：

def C(n,r):
    if n==r:
        return 1
    elif r==1:
        return n
    else:
        return C(n-1,r)+C(n-1,r-1)

虽然参考上面的等式来计算 C(990, 33)，python 会花费太多时间。

如何提高其性能？

标签： pythonrecursionoptimizationcombinations

解决方案

受到@user1558604 评论的启发；这要快得多：

cache = dict()

def C(n,r):
    if (n,r) in cache:
        return cache[(n,r)]
    elif n==r:
        cache[(n,r)] = 1
        return 1
    elif r==1:
        cache[(n,r)] = n
        return n
    else:
        cache[(n,r)] = C(n-1,r)+C(n-1,r-1)
        return C(n-1,r)+C(n-1,r-1)

输出：

>>> import timeit
>>> %timeit C(990, 33)
321 ns ± 24.7 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)

推荐阅读