0

我有一个递归算法，我在其中计算一些概率值。输入是一个整数列表和一个整数值，它表示一个常量值。

例如，p([12,19,13], 2)进行三个递归调用，它们是

p([12,19],0)和p([13], 2)

p([12,19],1)和p([13], 1)

p([12,19],2)和p([13], 0)

因为 2 可以分解为 0+2、1+1 或 2+0。然后每个调用都遵循类似的方法并进行其他几个递归调用。

我有的递归算法

limit = 20
def p(listvals, cval):
    # base case
    if len(listvals) == 0:
        return 0

    if len(listvals) == 1:
        if cval == 0:
            return listvals[0]/limit
        elif listvals[0] + cval > limit:
            return 0
        else:
            return 1/limit

    result = 0
    for c in range(0,cval+1):
        c1 = c
        c2 = cval-c
        listvals1 = listvals[:-1]
        listvals2 = [listvals[-1]]
        if listvals[-1] + c2 <= limit:
            r = p(listvals1, c1) * p(listvals2, c2)
            result = result+r

    return result

我一直在尝试将其转换为自下而上的 DP 代码，但无法弄清楚我需要进行迭代的方式。

我写下了最终结果需要计算的所有中间步骤，很明显在递归调用的底部有很多重复。

我尝试创建一个预先计算值的字典，如下所示

m[single_value]=[list of calculated values]

并使用这些值而不是进行第二次递归调用p(listvals2, c2)，但就运行时间而言，它并没有多大帮助。

如何通过使用适当的自下而上的方法来提高运行时间？

4

1 回答 1

1

不确定我是否理解您的程序想要计算的内容，所以对此无能为力，也许可以再解释一下？

关于提高性能，您只缓存在递归调用中重复的计算的叶节点。更好的方法是将函数的第一个参数p作为元组而不是列表，然后将两个参数的元组p用作字典中的缓存键。

Python 的标准库functools提供了一种简单的方法来完成这个相当常见的部分。

from functools import wraps

def cached(func):
  cache = {}
  @wraps(func)
  def wrapped(listvals, cval):
    key = (listvals, cval)
    if key not in cache:
        cache[key] = func(key)
    return cache[key]
  return wrapped

使用此装饰器缓存所有调用函数：

@cached
def p(listvals, cval):

现在有你的p元组而不是列表：

p((12,19,13), 2)
于 2019-04-06T13:22:28.183 回答