एक पॉलिमॉर्फिक प्रकार हस्ताक्षर प्रदर्शन को कम क्यों करता है?

Question

यहाँ फिबोनैकी संख्या की गणना करने के लिए एक सरल समारोह है:

fib :: [Int] 
fib = 1 : 1 : zipWith (+) fib (tail fib) 

GHCi में मैं जल्दी से श्रृंखला की गणना कर सकते हैं। वास्तव में, कुछ प्रयोगों से पता चलता है कि गणना लगभग रैखिक समय में चलती है।

ghci> last $ take 100000 fib 
354224848179261915075   -- takes under a second 

अगर मैं प्रकार हस्ताक्षर बदलने के बजाय बहुरूपी होने के लिए:

fib :: Num a => [a] 
fib = 1 : 1 : zipWith (+) fib (tail fib) 

फिर एल्गोरिथ्म धीमी हो जाती है। वास्तव में, ऐसा लगता है कि यह अब घातीय समय में चलता है!

क्या पॉलिमॉर्फिक प्रकार हस्ताक्षर पर स्विच करना मतलब है कि सूची प्रत्येक चरण में पूरी तरह से पुनः संयोजित की जा रही है? यदि हां, तो क्यों?

Answer 1

यह शब्दकोश अनुवाद के कारण है।

fib :: [Int] 

एक शीर्ष स्तर स्थिर है।

लेकिन इस:

fib :: Num a => [a] 
fib = 1 : 1 : zipWith (+) fib (tail fib) 

सिर्फ एक शीर्ष स्तर समारोह है, जो रनटाइम पर एक Num शब्दकोश को लागू किया जाएगा है। इसलिए जैसा:

fib d = 1 : 1 : zipWith (d.+) (fib d) (tail (fib d)) 

तो अगर आप किसी भी अनुकूलन के बिना इस संकलन, इस तरह कि कोई विशेषज्ञता भी हो सकता है, आप घातीय समय मिथ्या के साथ, अंत के रूप में सूची प्रत्येक समारोह कॉल पर, खरोंच से पुनर्निर्माण किया गया है जाएगा - यह अब आलसी डेटा संरचना नहीं है।

Answer 2

हां, पॉलीमोर्फिक प्रकार हस्ताक्षर का अर्थ है कि इसे प्रत्येक चरण में पुनः संयोजित किया जा रहा है। कोर GHC-7.4.2 द्वारा उत्पादित -O2 साथ:

lvl_rcZ :: GHC.Integer.Type.Integer 
[GblId, Str=DmdType] 
lvl_rcZ = __integer 1 

Rec { 
PolyFib.fib [Occ=LoopBreaker] 
    :: forall a_a9W. GHC.Num.Num a_a9W => [a_a9W] 
[GblId, Arity=1, Str=DmdType L] 
PolyFib.fib = 
    \ (@ a_aal) ($dNum_aam :: GHC.Num.Num a_aal) -> 
    GHC.Types.: 
     @ a_aal 
     (GHC.Num.fromInteger @ a_aal $dNum_aam lvl_rcZ) 
     (GHC.Types.: 
     @ a_aal 
     (GHC.Num.fromInteger @ a_aal $dNum_aam lvl_rcZ) 
     (GHC.List.zipWith 
      @ a_aal 
      @ a_aal 
      @ a_aal 
      (GHC.Num.+ @ a_aal $dNum_aam) 
      (PolyFib.fib @ a_aal $dNum_aam) 
      (case PolyFib.fib @ a_aal $dNum_aam of _ { 
       [] -> GHC.List.tail1 @ a_aal; 
       : _ xs_abD -> xs_abD 
      }))) 
end Rec } 

कारण यह है कि यह प्रत्येक प्रकार Num से संबंधित के लिए फिबोनैकी संख्या की एक सूची कैश करने के लिए संभव नहीं है, और fib स्पष्ट रूप से, एक बहुरूपी मूल्य है इसलिए यह बिल्कुल कैश नहीं मिलता है।

आप प्रत्येक प्रकार पर गणना के लिए कम से कम इसे कैश करने के लिए चाहते हैं, एक स्थानीय सूची

pfibs :: Num a => [a] 
pfibs = res 
    where 
    res = 1 : 1 : zipWith (+) res (tail res) 

का उपयोग करता है प्रत्येक गणना के लिए कैशिंग के बाद से अब सूची में monomorphic है (ताकि pfibs !! 500 जैसे तेज है) प्रत्येक गणना। यह अभी भी प्रत्येक क्वेरी के लिए पुन: संकलित किया जाएगा (जब तक कि आप इसे एक मोनोमोर्फिक नाम से बांध न दें), लेकिन प्रत्येक एकल सूची तत्व के लिए नहीं।

*PolyFib> pfibs !! 999999 :: Int 
-4249520595888827205 
(0.31 secs, 137462088 bytes)