python - 超出最大递归深度，但仅在使用装饰器时

Question

我正在编写一个程序来计算 Python 中的 Levenshtein 距离。我实现了记忆化，因为我递归地运行算法。我的原始函数在函数本身中实现了内存。这是它的样子:

# Memoization table mapping from a tuple of two strings to their Levenshtein distance
dp = {}

# Levenshtein distance algorithm
def lev(s, t):

  # If the strings are 0, return length of other
  if not s:
    return len(t)
  if not t:
    return len(s)

  # If the last two characters are the same, no cost. Otherwise, cost of 1
  if s[-1] is t[-1]:
    cost = 0
  else:
    cost = 1

  # Save in dictionary if never calculated before
  if not (s[:-1], t) in dp:
    dp[(s[:-1], t)] = lev(s[:-1], t)
  if not (s, t[:-1]) in dp:
    dp[(s, t[:-1])] = lev(s, t[:-1])
  if not (s[:-1], t[:-1]) in dp:
    dp[(s[:-1], t[:-1])] = lev(s[:-1], t[:-1])

  # Returns minimum chars to delete from s, t, and both
  return min(dp[(s[:-1], t)] + 1,
             dp[(s, t[:-1])] + 1,
             dp[(s[:-1], t[:-1])] + cost)

这行得通!但是，我找到了一种方法来内存 using decorators .我尝试将此技术应用到我的算法中:

# Memoization table mapping from a tuple of two strings to their Levenshtein distance
def memoize(func):
  memo = {}
  def wrap(s, t):
    if (s, t) not in memo:
      memo[(s, t)] = func(s, t)
    return memo[(s, t)]
  return wrap

# Levenshtein distance algorithm
@memoize # lev = memoize(lev)
def lev(s, t):

  # If the strings are 0, return length of other
  if not s:
    return len(t)
  if not t:
    return len(s)

  # If the last two characters are the same, no cost. Otherwise, cost of 1
  if s[-1] is t[-1]:
    cost = 0
  else:
    cost = 1

  # Returns minimum chars to delete from s, t, and both
  return min(lev(s[:-1], t) + 1,
             lev(s, t[:-1]) + 1,
             lev(s[:-1], t[:-1]) + cost)

对我来说，这看起来更清晰，也更容易混淆。我以为这两者在功能上是等价的，但是当我运行带有装饰器的版本时，我惊讶地发现我得到了一个RecursionError: maximum recursion depth exceeded。

我到底错过了什么？使用装饰器在功能上不等价吗？我尝试通过添加 sys.setrecursionlimit(1500) 进行修复，这很有效，但这是一个 hack，并没有解释为什么两者的功能不同。

注意:我使用一段 lorem ipsum 作为维基百科中 s 和 t 的测试字符串:

Lorem ipsum dolor sit amet, consectetur adipiscing elit, sed do eiusmod tempor incididunt ut labore et dolore magna aliqua. Ut enim ad minim veniam, quis nostrud exercitation ullamco laboris nisi ut aliquip ex ea commodo consequat. Duis aute irure dolor in reprehenderit in voluptate velit esse cillum dolore eu fugiat nulla pariatur. Excepteur sint occaecat cupidatat non proident, sunt in culpa qui officia deserunt mollit anim id est labour.

我知道对于更长的字符串，我的第一个函数将失败。我只想知道为什么装饰的首先失败。谢谢!

Answer 1

考虑原始代码中发生的堆栈帧(函数调用)。它们看起来像:

lev(s, t)
-> lev(..., ...)
   -> lev(..., ...)
       -> lev(..., ...)
           -> lev(..., ...)

在您的内存版本中，它们显示为:

wraps(s, t)
-> lev(..., ...)
   -> wraps(s, t)
      -> lev(..., ...)
          -> wraps(s, t)
             -> lev(..., ...)
                -> wraps(s, t)
                   -> lev(..., ...)
                      -> wraps(s, t)
                         -> lev(..., ...)

也就是说，您的堆栈帧将是原来的两倍大，因为每个“调用”实际上调用了两个函数。因此，您将更早地耗尽堆栈帧限制。