दिलचस्प पोस्ट
किसी अन्य एप्लिकेशन में गतिविधि कैसे प्रारंभ करें? तेजी से: जब एक सेल में एक बटन टैप किया जाता है तो indexpath.row कैसे मिलता है? संग्रहीत कार्यविधि से कई पंक्तियों को वापस कैसे करें? (ओरेकल पीएल / एसक्यूएल) क्या एक * ख * नियमित है? Ggplot में एक पूर्व परिभाषित रंग पैलेट का उपयोग करना कैसे एक विधि संदर्भ विधेयक को नकारना स्विफ्ट में दृश्य नियंत्रकों के बीच डेटा कैसे पहुंचा? एंड्रॉइड में टेक्स्ट की लंबाई को सीमित करें चर और विधियों के साथ अंडरस्कोर बनाम डबल अंडरस्कोर विधि स्थैतिक बनाया जा सकता है, लेकिन क्या यह चाहिए? अल्पविराम से अलग होने वाली सूची के रूप में MySQL परिणाम कैसे Android में datepicker संवाद में अधिकतम तारीख सेट? jQuery मानक और बेस्ट प्रैक्टिस कैसे एक तत्व अन्य तत्वों अतिव्यापी है की जांच करने के लिए? पॉइंटर के संदर्भ में और एक सूचक के संदर्भ में अंतर

इस फीबोनासी समारोह को कैसे याद किया गया है?

क्या इस फाइबोनैचि फ़ंक्शन को याद किया गया है?

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

और संबंधित नोट पर, यह संस्करण क्यों नहीं है?

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

वेब के समाधान से एकत्रित समाधान "इस फीबोनासी समारोह को कैसे याद किया गया है?"

हास्केल में मूल्यांकन तंत्र ज़रूरत होती है : जब एक मान की आवश्यकता होती है, तो इसकी गणना की जाती है, और इसे फिर से पूछा जाने पर तैयार रखा जाता है अगर हम कुछ सूची को परिभाषित करते हैं, xs=[0..] और बाद में अपने 100 वां तत्व, xs!!99 लिए पूछें, सूची में 100 वें स्लॉट को "फ्लेशेड आउट" किया जाता है, जो अब 99 नंबर रखता है, अगली पहुंच के लिए तैयार है।

यही वह चाल है, "चलने वाली एक सूची" का शोषण किया जा रहा है। सामान्य दोगुनी-पुनरावृत्ति फिबोनैकी परिभाषा में, fib n = fib (n-1) + fib (n-2) , फ़ंक्शन स्वयं को शीर्ष से दो बार फोन करता है, जिससे घातीय विस्फोट होता है। लेकिन उस चाल के साथ, हम अंतरिम परिणामों के लिए एक सूची तैयार करते हैं, और "सूची के माध्यम से" जाते हैं:

 fib n = (xs!!(n-1)) + (xs!!(n-2)) where xs = 0:1:map fib [2..] 

यह चाल उस सूची को पैदा करने के लिए पैदा की जाती है, और उस सूची को fib करने के लिए कॉल के बीच (कूड़ा संग्रह के माध्यम से) दूर जाने का कारण नहीं है। इसे प्राप्त करने का सबसे आसान तरीका, उस सूची को नाम देना है। "यदि आप इसे नाम देते हैं, तो यह रह जाएगा।"


आपका पहला संस्करण एक मोनोमोर्फिक स्थिरता को परिभाषित करता है, और दूसरा एक बहुरूपिक फ़ंक्शन को परिभाषित करता है। एक बहुरूपिक कार्य भिन्न प्रकारों के लिए एक ही आंतरिक सूची का उपयोग नहीं कर सकता है, जिसकी आवश्यकता हो सकती है, इसलिए कोई साझाकरण नहीं , अर्थात् कोई मेमोअनाइजेशन नहीं।

पहले संस्करण के साथ, कंपाइलर हमारे साथ उदार हो रहा है, उस निरंतर उपविभाजन ( map fib' [0..] निकालकर) और यह एक अलग साझा करने योग्य इकाई बना रहा है, लेकिन ऐसा करने के लिए कोई दायित्व नहीं है। और वास्तव में ऐसे मामले हैं जहां हम ऐसा नहीं करना चाहते हैं कि हमारे लिए स्वचालित रूप से

( संपादित करें 🙂 इन फिर से लिखने पर विचार करें:

 fib1 = f fib2 n = fn fib3 n = fn where where where fi = xs !! ifi = xs !! ifi = xs !! i xs = map fib' [0..] xs = map fib' [0..] xs = map fib' [0..] fib' 1 = 1 fib' 1 = 1 fib' 1 = 1 fib' 2 = 1 fib' 2 = 1 fib' 2 = 1 fib' i=fib1(i-2)+fib1(i-1) fib' i=fib2(i-2)+fib2(i-1) fib' i=f(i-2)+f(i-1) 

तो वास्तविक कहानी नेस्टेड स्कोप परिभाषाओं के बारे में है पहली परिभाषा के साथ कोई बाहरी गुंजाइश नहीं है, और तीसरा सावधान है कि बाह्य- fib3 3 को कॉल करने के लिए नहीं, बल्कि समान-स्तर f

fib2 का एक नया fib2 अपनी नेस्टेड परिभाषाएं पैदा कर रहा है क्योंकि उनमें से किसी को (सिद्धांत में) अलग अलग परिभाषित किया जा सकता है, n के मूल्य (विटस और fib2 के लिए fib2 करने के लिए) के आधार पर अलग अलग परिभाषित किया गया है। पहले परिभाषा के साथ पर निर्भर करने के लिए कोई n नहीं है, और तीसरे के साथ एक निर्भरता होती है, लेकिन प्रत्येक अलग कॉल को fib3 कॉल में कॉल करता f जो केवल एक ही स्तरीय से परिभाषा को कॉल करने के लिए सावधान है, आंतरिक fib3 इस विशिष्ट आवेश से, इसलिए fib3 उस आमंत्रण के लिए fib3 पुन: उपयोग (यानी साझा किया गया) हो जाता है।

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

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

संक्षेप में उत्तर है, यह एक संकलक चीज़ है 🙂

मैं पूरी तरह से निश्चित नहीं हूँ, लेकिन यहां एक शिक्षित अनुमान है:

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

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

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

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

दूसरा मामला बिल्कुल क्यों काम करता है, इस बारे में अधिक जानकारी के लिए, एक पुनरावर्ती परिभाषित सूची (ज़िप के मामले में तंतुओं) को समझें ।

सबसे पहले, ghc-7.4.2 के साथ, ओ -8 के साथ संकलित, गैर-ज्ञात संस्करण इतना बुरा नहीं है, फ़िबोनैचि संख्याओं की आंतरिक सूची अभी भी समारोह में प्रत्येक शीर्ष-स्तरीय कॉल के लिए याद की जाती है। लेकिन यह नहीं है, और उचित रूप से, विभिन्न शीर्ष-स्तरीय कॉलों में याद नहीं किया जा सकता है। हालांकि, दूसरे संस्करण के लिए, सूची को कॉल में साझा किया जाता है।

यह मोनोमोर्फिज़्म प्रतिबंध के कारण है

सबसे पहले एक सरल पैटर्न बाध्यकारी (केवल नाम, कोई तर्क नहीं) द्वारा बाध्य है, इसलिए मोनोमोर्फिज़्म प्रतिबंध द्वारा इसे एक मोनोमोर्फिक प्रकार प्राप्त करना होगा। अनुमानित प्रकार है

 fib :: (Num n) => Int -> n 

और इस तरह की एक बाधा चूक (डिफ़ॉल्ट रूप से घोषणा के अभाव में अन्यथा कह रही है) Integer , प्रकार को फिक्स करना

 fib :: Int -> Integer 

इस प्रकार वहाँ केवल एक सूची है (प्रकार [Integer] ) को याद रखना।

दूसरे को फ़ंक्शन तर्क के साथ परिभाषित किया जाता है, इस प्रकार यह बहुरूपता बना रहता है, और अगर कॉलों में आंतरिक सूचियों को याद किया जाता है, तो प्रत्येक सूची में प्रत्येक सूची के लिए एक सूची को याद रखना होगा। यह व्यावहारिक नहीं है

मोनोमोर्फिज़्म प्रतिबंध के साथ दोनों संस्करणों को संकलित करें, या समान प्रकार के हस्ताक्षर के साथ, और दोनों ही एक ही व्यवहार को दर्शाते हैं। (यह पुराने कंपाइलर संस्करणों के लिए सही नहीं था, मुझे नहीं पता कि यह संस्करण पहले किसने किया था।)

आपको हास्केल के लिए मेमोआइज़ फ़ंक्शन की आवश्यकता नहीं है केवल अनुभवजन्य प्रोग्रामिंग भाषा को फ़ंक्शन की आवश्यकता होती है। हालांकि, हास्केल कार्यात्मक लैंग और …

तो, यह बहुत तेजी से फिबोनैकी एल्गोरिथ्म का उदाहरण है:

 fib = zipWith (+) (0:(1:fib)) (1:fib) 

zipWith मानक प्रस्ताव से कार्य है:

 zipWith :: (a->b->c) -> [a]->[b]->[c] zipWith op (n1:val1) (n2:val2) = (n1 + n2) : (zipWith op val1 val2) zipWith _ _ _ = [] 

परीक्षा:

 print $ take 100 fib 

आउटपुट:

 [1,2,3,5,8,13,21,34,55,89,144,233,377,610,987,1597,2584,4181,6765,10946,17711,28657,46368,75025,121393,196418,317811,514229,832040,1346269,2178309,3524578,5702887,9227465,14930352,24157817,39088169,63245986,102334155,165580141,267914296,433494437,701408733,1134903170,1836311903,2971215073,4807526976,7778742049,12586269025,20365011074,32951280099,53316291173,86267571272,139583862445,225851433717,365435296162,591286729879,956722026041,1548008755920,2504730781961,4052739537881,6557470319842,10610209857723,17167680177565,27777890035288,44945570212853,72723460248141,117669030460994,190392490709135,308061521170129,498454011879264,806515533049393,1304969544928657,2111485077978050,3416454622906707,5527939700884757,8944394323791464,14472334024676221,23416728348467685,37889062373143906,61305790721611591,99194853094755497,160500643816367088,259695496911122585,420196140727489673,679891637638612258,1100087778366101931,1779979416004714189,2880067194370816120,4660046610375530309,7540113804746346429,12200160415121876738,19740274219868223167,31940434634990099905,51680708854858323072,83621143489848422977,135301852344706746049,218922995834555169026,354224848179261915075,573147844013817084101] 

समय बीत गया: 0.00018 एस