"फ़्लोट आउट" का अर्थ क्या है?

Question

Haskell wiki I read that this पर:

fib = 
    let fib' 0 = 0 
     fib' 1 = 1 
     fib' n = fib (n - 1) + fib (n - 2) 
    in (map fib' [0 ..] !!) 

इस तुलना में अधिक कुशल है:

fib x = 
    let fib' 0 = 0 
     fib' 1 = 1 
     fib' n = fib (n - 1) + fib (n - 2) 
    in map fib' [0 ..] !! x 

वजह से, "दूसरे मामले मिथ्या 'है (फिर से) के लिए हर तर्क एक्स परिभाषित में, इस प्रकार यह नहीं कर सकते बाहर निकल जाओ। "

मुझे समझ में नहीं आता कि इसका क्या अर्थ है।

1. "फ़्लोट आउट" का क्या अर्थ है? यह एक अनुकूलन कैसा है?
2. fib'fib के प्रत्येक आमंत्रण के लिए फिर से परिभाषित क्यों किया जा रहा है?
3. क्या यह एक ईटा-विस्तार है या नहीं?

Answer 1

यह बहुत अच्छा स्पष्टीकरण नहीं है।

"बाहर मंगाई" का अर्थ है कि में:

\x -> let y = ... in z 

अगर ...एक्स का उल्लेख नहीं करता तो यह लैम्ब्डा की बाहर जारी किया जा सकता है:

let y = ... in \x -> z 

यह जिसका मतलब है केवल एक बार गणना की जाएगी, जो ... महंगा है तो बहुत समय बचा सकता है। हालांकि, जीएचसी इस तरह के अनुकूलन करने के बारे में रूढ़िवादी है, क्योंकि वे अंतरिक्ष लीक पेश कर सकते हैं। (हालांकि यह दूसरी परिभाषा के लिए ऐसा करता है यदि आप इसे एक प्रकार का हस्ताक्षर देते हैं, क्योंकि डैनियल फिशर अपने जवाब में बताते हैं।)

हालांकि यह स्वचालित अनुकूलन के बारे में नहीं है। पहला स्निपेट लैम्ब्डा के बाहर fib' को परिभाषित करता है, जबकि दूसरा इसे अंदर परिभाषित करता है (लैम्ब्डा fib x = ... में अंतर्निहित है, जो fib = \x -> ... के बराबर है), जो उद्धरण कह रहा है।

यहां तक ​​कि यह वास्तव में प्रासंगिक नहीं है, हालांकि; क्या प्रासंगिक है कि पहले स्निपेट में, map fib' [0 ..] लैम्ब्डा के बाहर होता है, और इसलिए इसका परिणाम लैम्ब्डा के सभी अनुप्रयोगों के बीच साझा किया जाता है (उस कोड में, "लैम्ब्डा" (!!) के आंशिक अनुप्रयोग से उत्पन्न होता है)। बाद में, यह लैम्ब्डा के अंदर है, और fib के प्रत्येक एप्लिकेशन के लिए पुन: संकुचित होने की संभावना है।

अंतिम परिणाम यह है कि पूर्व कार्यान्वयन मूल्यों को कैश करता है और इसलिए बाद के मुकाबले कहीं अधिक कुशल होता है। ध्यान दें कि पहली स्निपेट की दक्षता इस तथ्य पर निर्भर है कि fib' सीधे रिकर्स नहीं करता है, बल्कि इसके बजाय fib के माध्यम से, और इसलिए ज्ञापन से लाभ प्राप्त होता है।

यह ईटा-विस्तार से संबंधित है; बाद वाला स्निपेट पहले का ईटा-विस्तार है। लेकिन आपके द्वारा उद्धृत बयान में यह नहीं बताया गया है कि क्या हो रहा है।

ध्यान दें कि यह कार्यान्वयन-विशिष्ट व्यवहार है, और हास्केल के अर्थशास्त्र का हिस्सा नहीं है। हालांकि, सभी उचित कार्यान्वयन इस तरह से व्यवहार करेंगे।

Answer 2

ehird के जवाब बातें बहुत अच्छी तरह से बताते हैं, लेकिन वहाँ एक बिंदु

अंतिम परिणाम पूर्व कार्यान्वयन मूल्यों कैश और अब तक अधिक उत्तरार्द्ध से कुशल है कि है।

जो कभी-कभी गलत होता है।

आप (मैं केवल -O2, नहीं -O1 जाँच की, और निश्चित रूप से केवल GHC) अनुकूलन के साथ या तो परिभाषा युक्त मॉड्यूल संकलन, तो इसके कई मामलों पर विचार करने के हैं:

1. प्रकार के बिना पहली परिभाषा हस्ताक्षर
2. प्रकार हस्ताक्षर के साथ दूसरी परिभाषा fib :: Int -> Integer
3. बहुरूपी प्रकार के साथ पहली परिभाषा fib :: Num a => Int -> a
4. बिना प्रकार हस्ताक्षर दूसरी परिभाषा
5. प्रकार हस्ताक्षर fib :: Num a => Int -> a

साथ दूसरी परिभाषा मामले 1 में, monomorphism प्रतिबंध प्रकार fib :: Int -> Integer पैदा करता है और सूची map fib' [0 .. ]fib के सभी आमंत्रण पर साझा किया जाता है। इसका मतलब है कि यदि आपने कभी fib (10^6) से पूछताछ की है, तो आपके पास स्मृति में पहले मिलियन (+1) फिबोनाची संख्याओं की एक सूची है, और यह केवल तभी एकत्र की जाएगी जब कचरा कलेक्टर निर्धारित कर सके कि इसका अब उपयोग नहीं किया जा रहा है। यह अक्सर एक स्मृति रिसाव है।

मामले 2 में, परिणाम (ing कोर) व्यावहारिक रूप से मामला 1.

मामले 4 में समान है, सूची (बेशक fib के विभिन्न उच्च-स्तरीय आमंत्रण के बीच साझा नहीं की है, परिणाम कर सकते हैं कई प्रकार हैं, इसलिए साझा करने के लिए कई सूचियां होंगी), लेकिन प्रति शीर्ष स्तर के आमंत्रण के बाद इसे तुरंत चालू किया जाता है और fib' से कॉल के लिए पुन: उपयोग किया जाता है, इसलिए fib n की गणना करने के लिए O (n) जोड़ों और O (n^2) चरणों की आवश्यकता होती है सूचि। ये इतना बुरा नहीं है। जब गणना पूरी हो जाती है तो सूची एकत्र की जाती है, इसलिए कोई स्थान रिसाव नहीं होता है।

केस 3 व्यावहारिक रूप से 4.

प्रकरण 5 के समान है, फिर भी, अनुभवहीन प्रत्यावर्तन से भी बदतर है। चूंकि यह स्पष्ट रूप से बहुलक है और सूची लैम्ब्डा के अंदर बंधी हुई है, सूची को रिकर्सिव कॉल के लिए पुन: उपयोग नहीं किया जा सकता है, प्रत्येक रिकर्सिव कॉल एक नई सूची बनाता है ...