अधिकतम रिकर्सन गहराई पार हो गई, लेकिन केवल सजावट

Question

का उपयोग करते समय मैं पाइथन में लेवेनशेटिन दूरी की गणना करने के लिए एक प्रोग्राम लिख रहा हूं। मैंने यादों को लागू किया क्योंकि मैं एल्गोरिदम को पुनरावर्ती रूप से चला रहा हूं। मेरे मूल कार्य ने समारोह में ही ज्ञापन लागू किया। यहां यह दिखता है:

# 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) जोड़कर एक फिक्स का प्रयास किया और यह काम करता है, लेकिन यह एक हैक है और यह समझ में नहीं आता कि दोनों फ़ंक्शन अलग-अलग क्यों हैं।

नोट: मैं और टी के लिए अपने परीक्षण तारों के रूप में lorem ipsum में से एक पैरा उपयोग कर रहा हूँ विकिपीडिया से:,

Lorem Ipsum मातम AMET बैठते हैं, consectetur adipiscing elit sed eiusmod tempor है incididunt ut labore एट dolore Magna aliqua। इस साइट पर क्लिक करने के लिए, इस तरह के अभ्यास के लिए उपयोग करने के लिए आवेदन कर रहे हैं। Voluptate velit esse cillum dolore eu fugiat nulla pariatur में reprehenderit में Duis aute irure dolor। Excepteur sint occaakat cupidatat गैर proident, चुपके में चुपचाप के रूप में काम कर रहे हैं।

मैं समझता हूं कि लंबे तारों के लिए, मेरा पहला कार्य विफल हो जाएगा। मैं सिर्फ यह जानना चाहता हूं कि सजाया गया पहला क्यों विफल रहता है। धन्यवाद!

Answer 1

अपने मूल कोड में होने वाले स्टैक फ्रेम (फ़ंक्शन कॉल) पर विचार करें। वे के रूप में प्रकट आप में

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

memoized संस्करण:

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

है यही कारण है, अपने ढेर फ्रेम दो बार के रूप में बड़ा हो जाएगा, के रूप में प्रत्येक कॉल "" वास्तव में दो कार्यों का आह्वान वे कुछ ऐसी दिखाई देगी। इस प्रकार आप पहले स्टैक फ्रेम सीमा को समाप्त कर देंगे।

Answer 2

यह एक अनंत रिकर्सन समस्या की तरह दिखता है, लेकिन ऐसा नहीं है। आप बस वास्तव में गहराई से recursing कर रहे हैं, और सजावट इसे गहरा बनाता है।

आपके द्वारा परिभाषित lev फ़ंक्शन को सीधे कॉल करने के बजाय, प्रत्येक कॉल wrap, और wraplev पर कॉल करता है। इससे आपका कॉल गहराई से दोगुना हो जाता है। यदि आपने सजावट का उपयोग नहीं किया है और आपके इनपुट बड़े हो गए हैं तो भी आप इस समस्या में भाग लेते थे।

इसे ठीक करने के लिए, आपको शायद एक गैर-पुनरावर्ती प्रोग्राम संरचना पर स्विच करना होगा, या तो नीचे की गतिशील प्रोग्रामिंग शैली का उपयोग करके या पुनरावृत्ति को पुनरावृत्ति में परिवर्तित करके और मैन्युअल रूप से स्टैक को बनाए रखना होगा।

Answer 3

अपने कोड को समझने का प्रयास करते हुए, मैंने कुछ संशोधन किए। कुछ भी बड़ा नहीं, सिर्फ वरीयता का मामला।

मैं केवल एक लाइन बदल दिया है: के रूप में है यह एक

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

के लिए

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

, अपने कोड किसी भी प्रत्यावर्तन समस्या

संपादित परीक्षण यह पूरी स्ट्रिंग के साथ के बिना चलाता है आप उपयोग कर रहे हैं, मैं भी रिकर्सन सीमा समस्या में भाग गया। निश्चित रूप से, यह गहरा हो जाता है।

: क्योंकि तुम अजगर 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): 
    ... 
    ...