python - 使用装饰器为递归函数计时

Question

我正在尝试制作一个计时器装饰器，它可以为具有不同大小列表的函数计时。计时器适用于我在下面编写的 insert()，但不适用于 minimum() 等递归函数。对于任何大小大于 1 的列表，我都会收到递归深度错误。我应该如何解决这个问题？

def time_long_list(func):
    import random
    def helper(*args, **kwargs):
        for item in [10, 100, 1000, 10000]:
            list = [random.randint(1, 10) for element in range(item)]
            with Timer() as clock:
                func(list)
            print(clock.interval/item)
        return func
    return helper

@time_long_list
def insert(lst):
    new_list = []
    for item in lst:
        new_list.insert(0, item)
    return new_list

@time_long_list
def minimum(lst):
    if len(lst) == 0:
        return None
    elif len(lst) == 1:
        return lst[0]
    else:
        mid = len(lst) // 2
        min1 = minimum(lst[:mid])
        min2 = minimum(lst[mid:])
        if min1 <= min2:
            return min1
        else:
            return min2

insert()
minimum()

Answer 1

当你装饰一个函数时，你是在告诉 python 解释器接受这个函数，对它做“一些事情”，然后在全局/模块命名空间中存储对新的、修改后的函数的引用。

根据定义，递归是一个函数调用自身。

所以你在这里尝试做的事情是行不通的，因为你的函数现在已经用生成测试数据的所有代码装饰了。当您递归调用该函数时，您每次都会生成所有测试数据。由于每一步都会生成新的测试数据，因此您永远无法到达递归的底部，并且不可避免地 - 您达到了深度限制。

你需要的是在我们装饰函数的时候保留对原始函数的引用。然后您将有两个函数，一个生成测试数据并执行递归的顶层，另一个不生成测试数据。它不是纯粹的递归——因为你有两个函数而不是一个，但这可能是你能做的最好的。

通过修 retrofit 饰器，我们可以保留对原始函数的引用

def time_long_list(func):
    import random
    def helper(*args, **kwargs):
        for item in [10, 100, 1000, 10000]:
            list = [random.randint(1, 10) for element in range(item)]
            with Timer() as clock:
                func(list, func)
                print(clock.interval/item)
        return func
    helper.original = func
return helper

然后修改你的递归函数，让它总是调用它自己的原始版本，而不是修改后的版本

@time_long_list
def minimum(lst, undecorated_func = None):
    if len(lst) == 0:
        return None
    elif len(lst) == 1:
        return lst[0]
    else:
        mid = len(lst) // 2
        min1 = minimum.original(lst[:mid])
        min2 = minimum.original(lst[mid:])
        if min1 <= min2:
            return min1
        else:
            return min2

我不建议这是执行此操作的好方法 - 你会更好 - 正如评论所建议的那样，如果可能的话，创建一个单独的顶级函数来进行计时和测试数据创建。