如何转换递归的“分而治之”？功能到使用装饰器的动态编程功能？ [英] How to convert recursive "divide and conquer" function to a dynamic programming function using decorators?

问题描述

我正在尝试编写一个装饰器函数，该函数将使用分而治之策略的两个参数将纯递归函数转换为使用动态编程的等效但效率更高的策略。
注意：它被指定为装饰两个输入函数。

因此，我试图记住这些值，但是我不确定如何在装饰的形式？还有它如何修饰两个输入函数？

EDIT：
这就是我所管理的要做：

  profile_results = {} 
t = {} 
 
'''The profile函数存储以下内容：函数所花费的时间，函数的名称以及被调用的次数，并将它们存储在名为* profile_results *的字典中''
 
 def profile（ func）：
导入时间
 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，包装器.calls）
 profile_results [name] = my_tuple 
 return res 
 wrapper.calls = 0 
 return wrapper 
 
＃动态函数效率更高一个，它是一个装饰器
 @profile 
 def dynamic（func）：
 def wrapper（ * args，** kwargs）：
如果t中的args：
返回t [args] 
 else：
 res = func（* args，** kwargs）
t [args] = res 
 return res 
 return wrapper 
 
＃常规递归函数
 @dynamic 
 @profile 
 def factorial（n ）：如果n == 0，则
：
返回1 
否则：
返回n * factorial（n-1）
  

这是我测试时显示的内容：

 阶乘（5）
打印（t）
打印（profile_results）
  

输出：

  {{0，）：1，（1，）：1，（2，）：2，（3 ，）：6，（4，）：24，（5，）：120} 
 {'dynamic'：（0.0，1），'factorial'：（0.0，6）} 
  

第一个输出是正确的，但是我试图对其进行分析，以查看动态编程实际上是否更快。但是，它将时间显示为0。我是否需要在某个地方添加 time.sleep（），我应该在哪里添加它以正确输出时间（假设它们是递归函数）？ / p>

我想知道我是否在正确地装饰它。我正在尝试装饰也是装饰器的动态功能。而且我正在尝试同时使用动态函数和概要文件函数来装饰阶乘函数。

任何帮助将不胜感激！

解决方案

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

Don不会重新发明轮子，但也许它不适合您的需求。

I am trying to write a decorator function which converts a pure recursive function with two arguments that uses a "divide and conquer" strategy to an equivalent but more efficient one using dynamic programming. Note: it is designated to decorate two input functions.

So I am trying to memoize the values but I am not sure how to correctly implement it in the form of a decorator? Also how can it decorate two input functions?

EDIT: This is what I have managed to do:

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)

This is what it prints out when I test it:

factorial(5)
print(t)
print (profile_results)

Output:

{(0,): 1, (1,): 1, (2,): 2, (3,): 6, (4,): 24, (5,): 120}
{'dynamic': (0.0, 1), 'factorial': (0.0, 6)}

The first output is correct but I am trying to profile it to see if the dynamic programming one is actually faster. However, it is showing the times as 0. Would I need to add a time.sleep() somewhere and where would I add it to correctly output the time (given that they are recursive functions)?

I am wondering if I am decorating it properly. I am trying to decorate the dynamic function which is a decorator as well. And I am trying to decorate the factorial function with both the dynamic and profile function.

Any help would be appreciated!

解决方案

There's already a memoize / cache decorator in the standard library : https://docs.python.org/3/library/functools.html#functools.lru_cache

Don't re-invent the wheel, but perhaps it is not suited to what you need.

这篇关于如何转换递归的“分而治之”？功能到使用装饰器的动态编程功能？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！