python - 内存蛋花

Question

我正在努力理解基于鸡蛋掉落问题的以下代码行。特别是，我无法理解 memo_cyclic 函数。您能向我解释一下 *args 的作用吗，以及 decorator 在此设置中的工作原理吗？ f_memo.__name__ = f.__name__ 有什么作用？为什么当我删除上面的行并包括 @memo_cyclic 时，程序会返回错误？

def memo_cyclic(f_cycle):
    def decorator(f):
        cache = {}
        def f_memo(*args):
            args = tuple(args)
            if args not in cache:
                cache[args] = f_cycle(*args)
                cache[args] = f(*args)
            return cache[args]
        f_memo.__name__ = f.__name__
        return f_memo
    return decorator

fail = float("infinity")

@memo_cyclic(lambda *args: fail)
def f(n, lo, hi, fl=0, dr=0):
    if lo == hi:
        return 0 # only one floor is possible
    if n+dr == 0:
        return fail # out of eggs
    if fl == 0:
        n, dr = n+dr, 0 # pick up any dropped eggs
    return 1 + min(f(n, lo, hi, fl-1, dr) if fl > 0 else fail,  # go down one floor
                   f(n, lo, hi, fl+1, dr) if fl < hi else fail, # go up one floor
                   max(f(n-1, lo,   fl, fl, dr),                # drop egg (broken)
                       f(n-1, fl+1, hi, fl, dr+1))              # drop egg (unbroken)
                       if n > 0 and lo <= fl < hi else fail)

import sys
sys.setrecursionlimit(10000)

print [f(n, 0, n) for n in range(20)]
print [f(1, 0, n) for n in range(20)]
print f(2, 0, 99)

Answer 1

这在任何关于装饰器的优秀教程中都有解释。例如https://realpython.com/primer-on-python-decorators/ .

但这是基本流程。考虑这个构造。

@decorator
def some_function (...):
    ...

实际上是以下内容的简写:

def some_function (...):
    ...

some_function = decorator(some_function)

但是在您的情况下，您有一个带参数的装饰器。那有什么作用？嗯:

@complex_decorator(stuff)
def some_function (...):
    ...

简单的意思

def some_function (...):
    ...

some_function = complex_decorator(stuff)(some_function)

所以complex_decorator需要是一个返回函数的函数。它返回的函数需要接受一个函数并返回一个新函数! (是的，这应该会让你在头几次遇到它时头晕目眩。但这都是合乎逻辑的。)

现在你的复杂装饰器是memo_cyclic，它太聪明了一半。让我们看看是否可以通过评论和数字来解决它。请尝试按数字顺序阅读评论。它们通常从外到内，因此在尝试阅读函数内部之前请跳过函数下方。

# 1) This is a recursive cache that will avoid repeated work and
#    also replace infinite cycles with a failure value that is
#    f_cycle(whatever, the, arguments, were)
def memo_cyclic(f_cycle):
    # 3) decorator will take our original function, and returns the
    #    replacement.  By possibly confusing coincidence, the
    #    function was originally called f before (global namespace)
    #    and is locally called f here in scope.  But it would work
    #    just fine if we locally called it g.
    def decorator(f):
        # 5) cache will have the values that we have produced
        #    before so that we can return them instead of
        #    having to calculate them a second time.  This trick
        #    is called "memoizing"
        cache = {}
        # 6) f_memo will be our replacement for f.  Note that *args
        #    here just means, "Turn whatever list of arguments we got
        #    before into an array."
        def f_memo(*args):
            #  9) A tuple is the same as an array except that it can't
            #     change.  Because it can't change, Python will let us
            #     use it as the key to a dictionary.
            args = tuple(args)
            # 10) And now we check if the tuple is in the cache.  If
            #     we have received this set of arguments before, the
            #     cache will be filled and we skip this.  Else we have
            #     work to do.
            if args not in cache:
                # 11) We set the value to return upon hitting an
                #     infinite loop.  Note that *args here means
                #     "turn a list back into a list of arguments
                #     before calling the function".
                cache[args] = f_cycle(*args)
                # 12) And now we recursively do the original
                #     calculation.  Note that when f calls itself
                #     recursively, it will call what is bound to
                #     the name f.  Which will _actually_ be the
                #     function f_memo.  Which means that if it
                #     WOULD have gone into an infinite loop, it
                #     will INSTEAD return the failure value.  (In
                #     our case, infinity.)
                cache[args] = f(*args)
            # 13) And whether we just calculated it, or had it
            #     from before, the answer should be cache[args].
            return cache[args]

        # 7) As a nicety, we make f_memo report itself as whatever
        #    name f had for itself.  This will, for example, make
        #    stack backtraces look nicer.
        f_memo.__name__ = f.__name__

        # 8) Returning f_memo here with f_cycle and the old f
        #    bound to it tells Python to make it become the new f.
        return f_memo

    # 4) Returning decorator here with f_cycle already bound is what
    #    tells python to replace f with decorator(f).
    return decorator

fail = float("infinity")

# 2) f_cycle will be a function that takes any arguments and
#    returns infinity.
@memo_cyclic(lambda *args: fail)
def f (...)
    ...