हास्केल फाइबोनैचि लगता धीमी

मैं हास्केल सीख रहा हूँ, और मैं एक साधारण फाइबोनैचि समारोह लिखा है: GHCi आरईपीएल मैं कुछ संख्या के साथ गड़बड़ के आसपास सकता है मेंहास्केल फाइबोनैचि लगता धीमी

fib :: Int -> Int 

fib 1 = 1 
fib 0 = 0 
fib n = (fib (n-1)) + (fib (n-2))

ठीक संकलित करने के लिए लगता है, और लोड हो रहा है इस स्क्रिप्ट । मैं

fib 33

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

फिब 33 विशेष रूप से कर नहीं लगा रहा है। जवाब 4 मिलियन से भी कम है। तो मुझे लगता है कि मेरा कोड बहुत अच्छी तरह लिखा नहीं गया है या जिस तरह से मैं रिकर्सन कर रहा हूं, उसके साथ कुछ समस्या है (ठीक है, यह अच्छी तरह से लिखा नहीं गया है कि यह नकारात्मक नकारात्मक पूर्णांक नहीं लेता है)। सवाल यह है, यह धीमा क्यों है? किसी भी मदद की सराहना की।

स्रोत

2014-12-17 Anonymous

यह सवाल CodeReview के लिए एक अच्छा एक हो रहा है। – Alexander

अपने कोड को देखते समय, बस कल्पना करें कि उदाहरण के लिए कितनी बार 'fib (5)' की गणना की जाती है। प्रत्येक पुनरावृत्ति, आप फिर से सभी "आंतरिक" फाइबोनैकी संख्याओं की गणना करते हैं। – WeSt

आपको क्लासिक आलसी अनंत सूची संस्करण का उपयोग करना चाहिए: 'fibs = 0: 1: zipWith (+) fibs (पूंछ fibs) '' fib n = fibs !! n' के साथ। देखें [फिबोनैकी अनुक्रम के बारे में हैकेल विकी] (https://www.haskell.org/haskellwiki/The_Fibonacci_sequence)।यह मनोरंजक है कि फिबोनैकी इस अनुक्रम के लिए प्रसिद्ध है, जो उस पुस्तक में थोड़ा सा अभ्यास था जिसके लिए उसे प्रसिद्ध होना चाहिए, जिसने पश्चिमी यूरोप में जगह मूल्य पेश किया। – AndrewC

मूल्यांकन आपके अपेक्षा से अधिक समय लेता है क्योंकि आपका फ़ंक्शन memoization का उपयोग नहीं करता है। उदाहरण देखें this question या that question यादों का उपयोग करते हुए हास्केल में फाइबोनैकी फ़ंक्शन को परिभाषित करने के उत्तरों के जवाब के लिए।

स्रोत

2014-12-17 15:59:24

ज्ञापन लिंक ने इस मुद्दे को बहुत अच्छी तरह से समझाया। –

दोनों प्रश्न और उनके उत्तर बल्कि गूढ़ हैं। * * पाठ्यपुस्तक मेटोड के बारे में क्या? –

@ एनएम। आपके द्वारा उपयोग की जाने वाली पाठ्यपुस्तक के आधार पर यह पता चल सकता है कि हैकेलविकि लिंक 'पाठ्यपुस्तक विधि' (अनुभाग 'रिकर्सन के साथ ज्ञापन') में दिखाता है। –

क्या आप उस समय की तुलना अन्य भाषाओं में करते थे?

यह रिकर्सिव एल्गोरिदम है जिसमें ओ (2^एन) जटिलता है। एन = 33 पर जो कॉल की एक बड़ी राशि देता है। यदि आप मानते हैं कि इस तरह के कॉल के लिए कितने मिलीसेकंड या नैनोसेकंड थे तो आपको वास्तविक प्रदर्शन के रूप में एक बहुत ही उल्लेखनीय उत्तर के साथ छोड़ दिया गया है।

याद रखें, कि कुछ कंपाइलर्स/निष्पादन वातावरण फ़ंक्शन रिटर्न मानों को कैश कर सकता है (फ़्रीरिक को बेहतर स्मृति थी कि इसे कैसे कहा जाता है: ज्ञापन), जो इस एल्गोरिदम के मामले में प्रदर्शन में सुधार करता है। इस मामले में ऐसा नहीं होता है, इसलिए उन सभी 2^एन रिकर्सिव कॉल होते हैं।

स्रोत

2014-12-17 16:00:54 Gerino

तकनीकी रूप से, इसकी जटिलता 'ओ (फाइब एन)' इसलिए लगभग ओ (1.68^एन) 'है, जो 'ओ (2^एन)' से थोड़ा बेहतर है। यह आपके बिंदु को प्रभावित नहीं करता है, हालांकि: इसकी जटिलता अभी भी घातीय है इसलिए रिकर्सिव कॉल की मात्रा जल्दी ही अप्रत्याशित हो जाती है। – chi

आपका एल्गोरिदम बहुत अच्छा नहीं है। आप ओ (एन) तक, स्मृतिकरण का उपयोग करके इसे थोड़ा सा सुधार सकते हैं। विभाजन का उपयोग करना और जीत, आप हे करने के लिए (लॉग एन) प्राप्त कर सकते हैं:

import Data.Matrix 

fib :: Integer -> Integer 
fib n = ((fromLists [[1,1],[1,0]])^n) ! (1,2)

विचार है, कि गुणन, साहचर्य है, इसलिए आप रणनीतिक स्थानों पर अपने ब्रेसिज़ डाल सकते हैं:

5^10 = (5 * 5 * 5 * 5 * 5) * (5 * 5 * 5 * 5 * 5) = (5 * 5 * 5 * 5 * 5)^2 = ((5 * 5) * (5 * 5) * 5)^2 = ((5 * 5)^2 * 5)^2 = (((5^2)^2) * 5)^2

समान पैटर्न लागू किया जा सकता है मैट्रिक्स गुणा करने के लिए। और हास्केल ने इसे पहले से ही अपनी डिफ़ॉल्ट लाइब्रेरी में (^) के लिए कार्यान्वित किया है।

यह वास्तव में काम करता है:

map fib [1..21] 
--! [1,1,2,3,5,8,13,21,34,55,89,144,233,377,610,987,1597,2584,4181,6765,10946]

स्रोत

2014-12-17 17:02:59

हास्केल फाइबोनैचि लगता धीमी

उत्तर

संबंधित मुद्दे