गैर pointfree शैली काफी हद तक धीमी है

Question

मैं निम्नलिखित, हास्केल में वें फिबोनैकी संख्या की गणना के लिए बार-बार उद्धृत कोड:

fibonacci :: Int -> Integer 
fibonacci = (map fib [0..] !!) 
    where fib 0 = 0 
      fib 1 = 1 
      fib n = fibonacci (n-2) + fibonacci (n-1) 

इस का उपयोग करना, मैं इस तरह के रूप में कॉल कर सकते हैं:

ghci> fibonacci 1000 

और लगभग तात्कालिक उत्तर प्राप्त करें।

हालांकि, इतना है कि यह pointfree शैली में नहीं है, अगर मैं उपरोक्त कोड संशोधित अर्थात

fibonacci :: Int -> Integer 
fibonacci x = (map fib [0..] !!) x 
    where fib 0 = 0 
      fib 1 = 1 
      fib n = fibonacci (n-2) + fibonacci (n-1) 

यह काफी हद तक धीमी है। इस हद तक कि

ghci> fibonacci 1000 

लटका जैसे कॉल।

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

Answer 1

अंतर का निरीक्षण करने के लिए, आपको शायद कोर को देखना चाहिए। मेरा अनुमान है कि यह (लगभग) की तुलना करने पर निर्भर करता

let f = map fib [0..] in \x -> f !! x 

\x -> let f = map fib [0..] in f !! x 

के बाद हर मंगलाचरण पर खरोंच से f recompute होगा। पूर्व प्रत्येक आमंत्रण के लिए प्रभावी रूप से उसी f को कैशिंग नहीं करता है।

ऐसा होता है कि इस विशिष्ट मामले में, जीएचसी ऑप्टिमाइज़ेशन सक्षम होने के बाद, दूसरे को अनुकूलित करने में सक्षम था।

ध्यान दें कि जीएचसी हमेशा इस परिवर्तन को निष्पादित नहीं करता है, क्योंकि यह हमेशा अनुकूलन नहीं होता है। पहले इस्तेमाल किया जाने वाला कैश हमेशा स्मृति में रखा जाता है। यह काम पर निर्भर करता है, स्मृति की बर्बादी का कारण बन सकता है।

Answer 2

मैंने इसे खोजने की कोशिश की लेकिन बाहर मारा। मुझे लगता है कि मेरे पास घर पर मेरे पीसी पर है। जो मैंने पढ़ा था वह था कि निश्चित बिंदु का उपयोग करने वाले कार्य स्वाभाविक रूप से तेज़ थे। निश्चित बिंदु का उपयोग करने के अन्य कारण हैं। मुझे इस पुनरावृत्ति फाइबोनैकी समारोह को लिखने में एक का सामना करना पड़ा। मैं देखना चाहता था कि एक पुनरावृत्ति संस्करण कैसे करेगा, मुझे एहसास हुआ कि मेरे पास मापने के लिए कोई तैयार तरीका नहीं था। मैं एक हास्केल neophyte हूँ। लेकिन किसी के परीक्षण के लिए यहां एक पुनरावृत्ति संस्करण है। मैं इसे परिभाषित करने के लिए नहीं मिला जब तक कि मैंने पहले अंतिम कार्य के बाद डॉट का उपयोग नहीं किया। मैं इसे और कम नहीं कर सका। [0,1] पैरामीटर तय किया गया है और पैरामीटर मान के रूप में आपूर्ति नहीं किया जाना है।

Prelude> fib = last . flip take (iterate (\ls -> ls ++ [last ls + last (init ls)]) [0,1]) 
Prelude> fib 25 

[0,1,1,2,3,5,8,13,21,34,55,89,144,233,377,610,987,1597,2584,4181,6765,10946,17711,28657,46368,75025]