जीएचसी ऑप्टिमाइज़ेशन

Question

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

इस समारोह 0.03 के बारे में सेकंड लेता है mfib 30 गणना करने के लिए: mfib 30 के लिए

let mfib = (map fib [0..] !!) 
    where 
    fib 0 = 0 
    fib 1 = 1 
    fib x = mfib (x-1) + mfib (x-2) 

इस समारोह के बारे में 3 सेकंड लेता है:

let mfib i = map fib [0..] !! i 
    where 
    fib 0 = 0 
    fib 1 = 1 
    fib x = mfib (x-1) + mfib (x-2) 

मैं इसे GHC इनलाइन के साथ क्या करना है अनुमान लगा रहा हूँ नियम और मिलान प्रदर्शन प्राप्त करने के लिए इनलाइन/नोलाइनलाइन प्रागमा जोड़ने की कोशिश कर रहे हैं।

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

Answer 1

desugared कोड को देखते समय इन मतभेदों को समझना आसान है, इसलिए यहां दो कार्यों के आंशिक रूप से desugared संस्करण हैं।

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

बनाम

let mfib = \i -> 
       let fib 0 = 0 
        fib 1 = 1 
        fib x = mfib (x-1) + mfib (x-2) 
       in map fib [0..] !! i 

ध्यान दें कि दूसरे कार्यक्रम में, अभिव्यक्ति map fib [0..]\i -> ... अंदर है, इसलिए इसे होगा (सामान्य रूप से अनुकूलन के बिना,) i के प्रत्येक मान के लिए मूल्यांकन किया। देखें When is memoization automatic in GHC Haskell?

Answer 2

नहीं, इसमें इनलाइनिंग के साथ कुछ लेना देना नहीं है। अंतर यह है कि mfib = (map fib [0..] !!) में कोई तर्क नहीं है। यह अभी भी पाठ्यक्रम का एक कार्य है, लेकिन उस फ़ंक्शन का मूल्यांकन करने से पहले किसी भी तर्क को पारित करने की आवश्यकता नहीं होती है। विशेष रूप से, इस mfib का मूल्यांकन fib सूची को इस तरह से तैयार करेगा कि इसे सभी सूचकांक के लिए पुन: उपयोग किया जा सके।

ओटीओएच, mfib i = map fib [0..] !! i का अर्थ है कि पूरे where ब्लॉक केवल तभी माना जाएगा जब आप वास्तव में i तर्क देते हैं।

दोनों अलग-अलग होते हैं यदि आप कई बार बार-बार फ़ंक्शन का मूल्यांकन करते हैं। दुर्भाग्यवश दूसरे संस्करण के लिए, फ़ंक्शंस का स्वयं का पुनरावृत्ति पहले से ही इसे बार-बार कॉल करता है! तो mfib (x-1) + mfib (x-2) को mfib (x-1), और फिर का पूरा काम mfib (x-2) का पूरा काम करने की आवश्यकता है। तो mfib nmfib (n-1) की दो बार कम्प्यूटेशनल लागत से अधिक लेता है, इसलिए mfib ∈ हे (2 ⁿ)।

यह अविश्वसनीय रूप से अपर्याप्त है, क्योंकि mfib (x-2) में से अधिकांश शर्तें mfib (x-1) में पहले से ही हैं और इन्हें फिर से उपयोग किया जा सकता है। खैर, यह वही है जो आपका पहला संस्करण करता है, क्योंकि यह fib सूची को एक बार और सभी इंडेक्स के लिए गणना करता है, इसलिए mfib (x-1) का मूल्यांकन पहले से ही अधिकांश काम करेगा जो कि mfib (x-2) द्वारा फिर से पढ़ा जा सकता है, जो बहुपद तक जटिलता को कम करता है।