如何使用decorator将递归“分而治之”函数转换为动态编程函数？

Question

我正在尝试编写一个decorator函数，它使用动态编程将一个带有两个参数的纯递归函数转换为使用动态编程的等效但更有效的方法。 注：它被指定用来修饰两个输入函数。在

所以我试图记住这些值，但我不确定如何以decorator的形式正确地实现它？它如何修饰两个输入函数？在

编辑： 这就是我努力做到的：

profile_results = {}
t = {}

 '''The profile function stores the following: the time taken by the function, the name of the function and the number of times it was called and stores these in the dictionary called *profile_results* '''

def profile(func):
    import time
    def wrapper(*args, **kwargs):
        wrapper.calls += 1
        name = func.__name__
        t1 = time.time()
        res = func(*args, **kwargs)
        t2 = time.time() - t1
        t = (t2)
        my_tuple = (t,wrapper.calls)
        profile_results[name] = my_tuple
        return res
    wrapper.calls = 0
    return wrapper

#the dynamic function is the more efficient one and it is a decorator
@profile
def dynamic(func):
    def wrapper(*args, **kwargs):
        if args in t:
            return t[args]
        else:
            res = func(*args, **kwargs)
            t[args] = res
            return res
    return wrapper

#regular recursive function
@dynamic
@profile
def factorial(n):
    if n == 0:
        return 1
    else:
        return n * factorial(n-1)

这是我测试时打印出来的：

^{pr2}$

输出：

^{3}$

第一个输出是正确的，但我试图分析它，看看动态编程是否真的更快。但是，它显示的时间是0。我需要添加一个睡觉时间（）在某处和何处添加它以正确输出时间（假定它们是递归函数）？在

我想知道我是否装饰得很好。我试图装饰动态函数，它也是一个装饰器。我试图用动态函数和轮廓函数来修饰阶乘函数。在

任何帮助都将不胜感激！在

Answer 1

标准库中已经有一个memoize/cache修饰符：https://docs.python.org/3/library/functools.html#functools.lru_cache

别再发明轮子了，但也许它不适合你的需要。在