आपकी पसंदीदा भाषा गहरी रिकर्सन कैसे संभालती है?

Question

मैंने हाल ही में पाइथन सीखना शुरू किया और मैं 1000 गहरी रिकर्सन सीमा (डिफ़ॉल्ट रूप से) खोजने के लिए आश्चर्यचकित था। यदि आप इसे 30000 के बराबर पर्याप्त सेट करते हैं, तो यह सी की तरह सेगमेंटेशन गलती के साथ दुर्घटनाग्रस्त हो जाता है। हालांकि, सी काफी अधिक है।

(अजगर लोगों को बताते हैं कि आप हमेशा पुनरावृत्ति वालों के लिए पुनरावर्ती कार्यों में बदल सकते हैं और है कि वे हमेशा के लिए तेजी से कर रहे हैं जल्दी कर रहे हैं। यही कारण है कि 100% सच है। यह वास्तव में क्या मेरे सवाल यद्यपि के बारे में है नहीं है।)

मैंने पर्ल में एक ही प्रयोग की कोशिश की और लगभग 10 मिलियन रिकर्सन ने अपने सभी 4 गीगा रैम का उपभोग किया और मैंने कोशिश करने के लिए^सी का उपयोग किया। स्पष्ट रूप से पर्ल सी स्टैक का उपयोग नहीं करता है, लेकिन जब यह रिकर्स करता है तो यह हास्यास्पद मात्रा में स्मृति का उपयोग करता है - इस बात पर विचार करते हुए कि यह कॉल करने के लिए कितना काम करना है, इस पर बहुत चौंकाने वाला नहीं है।

मैंने पाइक में कोशिश की और लगभग 2 सेकंड में 100,000,000 रिकर्सन प्राप्त करने के लिए पूरी तरह से हैरान था। मुझे नहीं पता कि यह कैसे किया गया, लेकिन मुझे संदेह है कि यह पुनरावृत्ति को पुनरावृत्ति प्रक्रिया में फटकार कर रहा है - ऐसा लगता है कि यह कोई अतिरिक्त स्मृति का उपभोग नहीं करता है। [नोट: पाईक तुच्छ मामलों समतल करता है, लेकिन और अधिक जटिल वालों पर segfaults, या तो मुझे बताया गया हूँ।]

मैं इन अन्यथा बेकार कार्यों के लिए इस्तेमाल किया:

int f(int i, int l) { if(i<l) return f(i+1,l); return i; } 

sub f { return f($_[0]+1, $_[1]) if $_[0]<$_[1]; return $_[0] }; 

def f(i,l): 
    if i<l: 
    return f(i+1,l) 
    return i 

मैं बहुत उत्सुक कैसे अन्य भाषाओं (उदाहरण के लिए, PHP, रूबी, जावा, लुआ, ओकम्ल, हास्केल) रिकर्सन को संभालते हैं और वे इसे इस तरह क्यों संभालते हैं। इसके अतिरिक्त, कृपया ध्यान दें कि क्या फ़ंक्शन "पूंछ-रिकर्सिव" है (टिप्पणी देखें)।

Fatal error: Maximum function nesting level of '100' reached, aborting!

संपादित करें:: इससे पहले कि यह मर जाता है

Answer 1

"द अजगर लोगों को बताते हैं कि आप हमेशा पुनरावृत्ति वालों के लिए पुनरावर्ती कार्यों में बदल सकते हैं जल्दी कर रहे हैं और वे हमेशा के लिए तेजी से कर रहे हैं कि"

यह सच है, लेकिन अगर यह सब है कि के रूप में वास्तव में के रूप में आसान है, क्यों क्या पाइथन मेरे लिए ऐसा नहीं करता है, ताकि मेरा कोड जितना संभव हो उतना सरल दिख सके? (मैं यह पाइथन कार्यान्वयन करने वालों को स्लैम नहीं करना चाहता, लेकिन क्योंकि जवाब समस्या को बताता है)।

रिकर्सन ऑप्टिमाइज़ेशन 14 वीं शताब्दी या कुछ के बाद से कार्यात्मक भाषाओं में मौजूद हैं। हास्केल, सीएएमएल, लिस्प कार्यान्वयन सभी आम तौर पर कम से कम पूंछ रिकर्सिव फ़ंक्शंस को पुनरावृत्तियों में परिवर्तित करते हैं: आप मूल रूप से ऐसा करके यह कर सकते हैं कि यह संभव है, यानी कि फ़ंक्शन को पुन: व्यवस्थित किया जा सकता है कि रिकर्सिव कॉल के अलावा रिटर्न वैल्यू के अलावा कोई स्थानीय चर उपयोग नहीं किया जाता है । वापसी से पहले रिकर्स किए गए रिटर्न वैल्यू पर कुछ काम करने पर यह संभव बनाने के लिए एक चाल है, एक अतिरिक्त "संचयक" पैरामीटर पेश करना है। सरल शब्दों में इसका मतलब यह है कि काम "अप" के तरीके से "डाउन" तरीके से प्रभावी ढंग से किया जा सकता है: विवरण के लिए 'फ़ंक्शन पूंछ-रिकर्सिव कैसे बनाएं' के लिए चारों ओर खोजें।

एक पूंछ में एक पूंछ रिकर्सिव फ़ंक्शन को मोड़ने का वास्तविक विवरण मूल रूप से आपके कॉल कन्वेंशन के साथ जिगर करने के लिए है, जैसे आप पैरामीटर सेट करके और फ़ंक्शन की शुरुआत में वापस कूदकर, "कॉल निष्पादित" कर सकते हैं, परेशान किए बिना उन सभी चीजों को उस क्षेत्र में सहेजने के लिए जो आप जानते हैं कि आप कभी भी उपयोग नहीं करेंगे। असेंबलर शब्दों में, आपको कॉलर-सेव रजिस्टर्स को संरक्षित करने की आवश्यकता नहीं है यदि डेटा-फ्लो विश्लेषण आपको बताता है कि वे कॉल से परे अप्रयुक्त हैं, और यह स्टैक पर कुछ भी है: आपको स्टैक पॉइंटर को स्थानांतरित करने की आवश्यकता नहीं है कॉल पर अगर आपको "रिक्त" बिट स्टैक को अगले रिकर्सन/पुनरावृत्ति द्वारा स्क्रीबल्ड नहीं किया जाता है।

पाइथन लोगों को कैसे पारदर्शी करने के विपरीत, एक सामान्य पुनरावर्ती कार्य को पुनरावृत्ति में परिवर्तित करना मामूली नहीं है: उदाहरण के लिए यदि यह एक सरल दृष्टिकोण में गुणात्मक रूप से रिकर्सिव है तो आपको अभी भी एक ढेर की आवश्यकता होगी।

मनोविज्ञान एक उपयोगी तकनीक है, हालांकि, मनमाने ढंग से पुनरावर्ती कार्यों के लिए, यदि आप संभव दृष्टिकोण में रूचि रखते हैं तो आप देखना चाहेंगे। इसका अर्थ यह है कि प्रत्येक बार एक समारोह का मूल्यांकन किया जाता है, तो आप परिणाम को कैश में चिपकाते हैं। रिकर्सन को अनुकूलित करने के लिए इसका उपयोग करने के लिए, मूल रूप से, यदि आपका रिकर्सिव फ़ंक्शन "डाउन" की गणना करता है, और आप इसे याद करते हैं, तो आप उस लूप को जोड़कर इसका मूल्यांकन कर सकते हैं जो फ़ंक्शन के प्रत्येक मान की गणना करने के बाद "अप" की गणना करता है जब तक आप पहुंच नहीं जाते लक्ष्य। यह बहुत कम स्टैक स्पेस का उपयोग करता है बशर्ते ज्ञापन कैश आपके लिए आवश्यक सभी मानों को पकड़ने के लिए पर्याप्त है: उदाहरण के लिए यदि f (n) f (n-1), f (n-2) और f (n) पर निर्भर करता है -3) आपको केवल कैश में 3 मानों के लिए स्थान की आवश्यकता है: जैसे ही आप ऊपर जाते हैं, आप सीढ़ी को दूर ला सकते हैं। यदि एफ (एन) एफ (एन -1) और एफ (एन/2) पर निर्भर करता है, तो आपको कैश में बहुत सी जगह की आवश्यकता होती है, लेकिन एक अपरिवर्तित रिकर्सन में स्टैक के लिए आप अभी भी कम से कम उपयोग करेंगे।

Answer 2

पीएचपी 100 की एक डिफ़ॉल्ट सीमा होती है आप ini_set('xdebug.max_nesting_level', 100000); साथ सीमा को बदल सकते हैं, लेकिन अगर आप 1150 के बारे में पुनरावृत्तियों पीएचपी दुर्घटनाओं से ऊपर जाना:

[Fri Oct 24 11:39:41 2008] [notice] Parent: child process exited with status 3221225477 -- Restarting.

Answer 3

इस धागे के अनुसार, around 5,000,000 जावा, 1 जीबी रैम के साथ। (और वह, हॉटस्पॉट के 'क्लाइंट' संस्करण के साथ)

वह 300Mo के stack (-Xss) के साथ था।

-server option के साथ, यह बढ़ाया जा सकता है।

कोई भी प्रत्येक परत पर स्टैक ओवरहेड को कम करने के लिए कंपाइलर (with JET उदाहरण के लिए) को अनुकूलित करने का प्रयास कर सकता है।

Answer 4

सी #/.NET एक विशेष सेट परिस्थितियों में पूंछ रिकर्सन का उपयोग करेगा। (सी # संकलक एक tailcall opcode फेंकना नहीं है, लेकिन JIT will implement tail recursion in some cases।

श्री बोर्डे also has a post on this topic। बेशक, CLR लगातार बदल रहा है और .NET 3.5 और 3.5SP1 साथ यह पूंछ के संबंध में फिर से परिवर्तित हो सकती है कॉल

Answer 5

विजुअल डेटाफ्लेक्स ओवरफ़्लो ढेर करेगा।

Answer 6

कुछ गैर रोगजनक मामलों (जैसे आपकी) में, (नवीनतम) लुआ tail call recursion का उपयोग करेगा, यानी। यह सिर्फ ढेर में डेटा धक्का दिए बिना कूद जाएगा। तो रिकर्सन लूप की संख्या लगभग असीमित हो सकती है। (छ बुला और ग्राम च बुला ... च)

function g(i, l) 
    if i >= l then 
     return i 
    end 
    return g(i+1, l) 
end 

और यहां तक ​​कि कोशिश की क्रॉस-प्रत्यावर्तन:

function f(i, l) 
    if i < l then 
     return f(i+1, l) 
    end 
    return i 
end 

local val1 = arg[1] or 1 
local val2 = arg[2] or 100000000 
print(f(val1 + 0, val2 + 0)) 

इसके अलावा साथ

:

साथ परीक्षण किया गया।

विंडोज़ पर, लुआ 5.1 इसे चलाने के लिए लगभग 1.1 एमबी (स्थिर) का उपयोग करता है, कुछ सेकंड में समाप्त होता है।

Answer 7

एफ # इंटरैक्टिव कंसोल में निम्नलिखित का उपयोग करना, यह एक दूसरे से कम में भाग गया:

let rec f i l = 
    match i with 
    | i when i < l -> f (i+1) l 
    | _ -> l 

f 0 100000000;; 

मैं तो एक सीधे अनुवाद अर्थात

let rec g i l = if i < l then g (i+1) l else l 

g 0 100000000;; 

एक ही परिणाम है, लेकिन अलग अलग संकलन की कोशिश की।

यह वही है च जब सी # करने के लिए अनुवाद में की तरह लग रहा है:

int f(int i, int l) 
{ 
    while(true) 
    { 
    int num = i; 
    if(num >= l) 
     return l; 
    int i = num; 
    l = l; 
    i = i + 1; 
    } 
} 

जी, लेकिन इस के लिए अनुवाद किया है:

int g(int i, int l) 
{ 
    while(i < l) 
    { 
    l = l; 
    i++; 
    } 
    return l; 
} 

ऐसा नहीं है कि दो कार्यों हैं कि दिलचस्प है मूल रूप से वही एफ # कंपाइलर द्वारा अलग-अलग प्रस्तुत किया जाता है। यह भी दिखाता है कि एफ # कंपाइलर में पूंछ-पुनरावर्ती अनुकूलन है। इस प्रकार यह लूप होना चाहिए जब तक कि मैं 32-बिट पूर्णांक की सीमा तक नहीं पहुंच जाता।

Answer 8

यह भाषा प्रश्न से अधिक कार्यान्वयन प्रश्न है। कुछ (स्टूपीड) सी कंपाइलर कार्यान्वयनकर्ता को अपने कॉल स्टैक को 1000 तक सीमित करने से कुछ भी नहीं रोक रहा है। वहां बहुत सारे छोटे प्रोसेसर हैं जिनके पास बहुत से लोगों के लिए स्टैक स्पेस नहीं होगा।

(अजगर लोगों को बताते हैं कि आप हमेशा पुनरावृत्ति वालों के लिए पुनरावर्ती कार्यों में बदल सकते हैं और है कि वे हमेशा के लिए तेजी से कर रहे हैं जल्दी कर रहे हैं। यही कारण है कि 100% सच है। यह वास्तव में क्या मेरे सवाल यद्यपि के बारे में है नहीं है।)

शायद वे कहते हैं कि, लेकिन यह बिल्कुल सही नहीं है। रिकर्सन को हमेशा पुनरावृत्ति में परिवर्तित किया जा सकता है, लेकिन कभी-कभी इसे स्टैक के मैन्युअल उपयोग की भी आवश्यकता होती है। उन परिस्थितियों में, मैं रिकर्सिव संस्करण को तेजी से देख सकता था (मान लीजिए कि आप सरल अनुकूलन करने के लिए पर्याप्त स्मार्ट हैं, जैसे रिकर्सिव रूटीन के बाहर अनियंत्रित घोषणाएं खींचना)। आखिरकार, स्टैक आसपास की प्रक्रिया कॉल को धक्का देता है एक अच्छी तरह से बाध्य समस्या है कि आपके कंपाइलर को अच्छी तरह से अनुकूलित करने के बारे में पता होना चाहिए। मैन्युअल स्टैक ऑपरेशंस, दूसरी तरफ, आपके कंपाइलर में विशेष अनुकूलन कोड नहीं होने वाले हैं, और उपयोगकर्ता के इंटरफ़ेस सैनिटी चेक के सभी प्रकार के लिए उत्तरदायी हैं जो अतिरिक्त चक्र उठाएंगे।

यह मामला हो सकता है कि पाइथन में पुनरावृत्त/ढेर समाधान हमेशा तेज है। यदि ऐसा है, तो यह पाइथन की विफलता है, रिकर्सन की नहीं।

Answer 9

Perl कोड पर लगातार सुधार करने के लिए यह एक निरंतर आकार का ढेर बनाने के लिए एक तरीका है। आप इसे goto का विशेष रूप उपयोग करके करते हैं।

sub f{ 
    if($_[0] < $_[1]){ 

    # return f($_[0]+1, $_[1]); 

    @_ = ($_[0]+1, $_[1]); 
    goto &f; 

    } else { 
    return $_[0] 
    } 
} 

जब इसे पहले कहा जाता है तो यह ढेर पर स्थान आवंटित करेगा। फिर यह अपने तर्क बदल देगा, और स्टैक पर कुछ भी जोड़ने के बिना, subroutine को पुनरारंभ करें। इसलिए यह दिखाएगा कि उसने कभी भी इसे स्वयं नहीं कहा, इसे एक पुनरावृत्ति प्रक्रिया में बदल दिया।

---

आप Sub::Call::Recur मॉड्यूल का भी उपयोग कर सकते हैं। जो कोड को समझने में आसान बनाता है, और छोटा।

use Sub::Call::Recur; 
sub f{ 
    recur($_[0]+1, $_[1]) if $_[0] < $_[1]; 
    return $_[0]; 
} 

Answer 10

मैं काफी कार्यात्मक प्रोग्रामिंग के एक प्रशंसक हूँ, और के बाद से उन भाषाओं के सबसे पूंछ कॉल अनुकूलन लागू, आप जितना आप :-P

तरह के रूप में हालांकि, व्यावहारिक रूप से recurse कर सकते हैं, मैं बहुत सारे जावा का उपयोग करना है और पायथन का भी बहुत उपयोग करना है। पता नहीं जावा की सीमा क्या है, लेकिन पाइथन के लिए मैंने वास्तव में एक सजावट को लागू करने के लिए योजना बनाई है (लेकिन अभी तक इसे नहीं किया है) जो पूंछ कॉल सजाए गए फ़ंक्शन को अनुकूलित करेगा। मैं इस योजना की पुनरावृत्ति को अनुकूलित करने के लिए योजना नहीं बना रहा था, लेकिन मुख्य रूप से पाइथन बाइटकोड को गतिशील रूप से पैच करने और पाइथन आंतरिक के बारे में और अधिक सीखने के लिए एक अभ्यास के रूप में। Heres कुछ itneresting लिंक: http://lambda-the-ultimate.org/node/1331 और http://www.rowehl.com/blog/?p=626

Answer 11

एक पुराने सफेद मैकबुक पर गहरे लाल रंग का 1.9.2dev (2010-07-11 संशोधन 28618) [x86_64-darwin10.0.0] चल रहा है:

def f 
    @i += 1 
    f 
end 

@i = 0 

begin 
    f 
rescue SystemStackError 
    puts @i 
end 

आउटपुट 9353 के लिए मेरा मतलब है, रूबी स्टैक पर 10,000 से कम कॉल के साथ बाहर निकलती है।

जैसे पार प्रत्यावर्तन के साथ

,:

def f 
    @i += 1 
    g 
end 

def g 
    f 
end 

यह आधे समय में बाहर क्रेप्स, 4677 में (~ = 9353/2)।

मैं एक proc में पुनरावर्ती कॉल लपेटकर द्वारा कुछ और पुनरावृत्तियों बाहर निचोड़ कर सकते हैं:

def f 
    @i += 1 
    yield 
end 

@i = 0 
@block = lambda { f(&@block) } 

begin 
    f(&@block) 
rescue SystemStackError 
    puts @i 
end 

जो बाहर erroring से पहले 4850 अप करने के लिए हो जाता है।

Answer 12

clojure पूंछ रिकर्सन "रिकूर" के लिए एक विशेष रूप प्रदान करता है, इसका उपयोग केवल अस्थि के पूंछ स्थानों में किया जा सकता है। अन्यथा यह जावा की तरह व्यवहार करता है और संभवतः एक स्टैकवरफ्लो एक्सेप्शन फेंक देगा।