最大再帰深度を超えましたが、デコレータを使用した場合のみ

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) 

私には、これはよりクリーンで混乱が少ないようです。私は2つが機能的に同等であると思ったが、デコレータを使ってバージョンを実行したとき、私はRecursionError: maximum recursion depth exceededを得たことに驚いた。

正確に何が欠けていますか？デコレータを機能的に同等のものに使用していませんか？私はsys.setrecursionlimit(1500)を追加して修正を試みましたが、これはうまくいきますが、それはハックであり、2つの機能が異なっている理由を説明していません。

注：私はウィキペディアからsとtのための私のテスト文字列としてLoremのイプサムの1つの段落を使用しています：

Loremのイプサム嘆きをAMET座る、consectetur adipiscing ELIT、eiusmod temporんsedのincididunt UT laboreらdolore magna aliqua。最小限に抑えて、練習や練習をすることができます。大気中に放出された栄養素は、栄養補助食品中に存在する。例外的な兆候を見せている人は、善意ではないと主張しています。

さらに長い文字列の場合、私の最初の機能は失敗することを理解しています。私はちょうど装飾されたものが最初に失敗する理由を知りたい。ありがとう！

Answer 1

元のコードで発生しているスタックフレーム（関数呼び出し）について考えてみましょう。あなたは彼らのように見えるメモ化バージョン

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

：それぞれは、実際には2つの関数を呼び出す「コール」としてあなたのスタックフレームは、2倍の大きなり、ある

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

を彼らは次のようになります。したがって、スタックフレームの制限を先に使い果たしてしまいます。

Answer 2

このは、無限の再帰問題のように見えますが、そうではありません。あなたは本当に深く再帰しており、デコレータはそれをもっと深くしています。

lev関数を直接呼び出す代わりに、すべての呼び出しはwrap、wrapはlevとなります。これにより、コールスタックは2倍になります。あなたがデコレータを使用せずに入力が大きくなった場合は、この問題に遭遇しました。

これを修正するには、ボトムアップの動的プログラミングスタイルを使用するか、再帰を反復に変換して手動でスタックを維持することによって、非再帰的なプログラム構造に切り替える必要があります。

Answer 3

コードを理解しようとすると、私はいくつかの変更を加えました。何も大きくはありません。好みの問題です。

私は一行変更：ようになり、あなたのコードは、文字列全体を持つ任意の再帰の問題

EDITテストそれなしで実行されます。この1

if s[-1] == t[-1]: 

ため

if s[-1] is t[-1]: 

をあなたが使用している、私も再帰制限の問題に遭遇した。確かに、それは深くなる。

を：あなたは、Python 3を（私は質問タグに見るように）、あなたが代わりにカスタム memoize機能の functools.lru_cacheを使用することができます使用しているため、それよりも

import sys 
sys.setrecursionlimit(10000) 

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 

@memoize 
def lev(s, t): 
    len_s, len_t = len(s), len(t) 
    if len_s==0: return len_t 
    if len_t==0: return len_s 
    cost = 0 if s[-1] == t[-1] else 1 
    return min(lev(s[:-1], t) + 1, 
       lev(s, t[:-1]) + 1, 
       lev(s[:-1], t[:-1]) + cost) 

s = "Lorem ibsum +++" 
t = "Loren ipsum ..." 
print(lev(s, t))    # 5 

その他：

は、これらの2行を追加します。

from functools import lru_cache 

@lru_cache(maxsize=None) 
def lev(s, t): 
    ... 
    ...