यह कोड शीर्ष स्तर पर निर्दिष्ट दो (पारस्परिक रूप से रद्द) अनंत सूचियों की सामग्री का योग करता है:
{-# language BangPatterns #-}
module Main where
unending1 :: [Int]
unending1 = cycle [1]
unending2 :: [Int]
unending2 = cycle [negate 1]
main :: IO ()
main = do
let summator :: Int -> [Int] -> [Int] -> Int
summator !acc (i1 : rest1) (i2 : rest2) =
if acc > 100
then acc -- never happens
else summator (acc+i1+i2) rest1 rest2
print (summator 0 unending1 unending2)
मैं इस कोड को बिना किसी अनुकूलन और कम ढेर आकार के संकलित करता हूं, जैसे:
ghc -O0 -with-rtsopts="-M10m" Main.hs
मेरा अंतर्ज्ञान यह है कि यह कोड स्मृति रिसाव का कारण बनता है, क्योंकि सारांश कार्य दो सूचियों को "भौतिक" करने का प्रयास करेगा, और उन दोनों के प्रमुख शीर्ष-स्तर पर हैं, इसलिए उन्हें त्याग नहीं किया जाएगा।
हालांकि जब मैं प्रोग्राम निष्पादित करता हूं तो ऐसा लगता है कि यह बिना किसी समस्या के अनिश्चित काल तक चलता है।
मैं कहाँ गलत हूँ?
संपादित करें। -ddump-simpl का उपयोग करके उत्पन्न कोर का निरीक्षण करने पर, सूचियां शीर्ष स्तर पर बनी हुई प्रतीत होती हैं। उदाहरण के लिए:
Result size of Tidy Core = {terms: 77, types: 52, coercions: 0}
-- RHS size: {terms: 5, types: 3, coercions: 0}
unending1 :: [Int]
[GblId, Str=DmdType]
unending1 =
cycle
@ Int (GHC.Types.: @ Int (GHC.Types.I# 1#) (GHC.Types.[] @ Int))
2 जवाब
जैसा कि ची ने उत्तर दिया, cycle की परिभाषा के कारण आपका कोड निरंतर स्थान पर चलता है।
हालांकि, यह ghc -O0 के साथ cycle xs = xs ++ cycle xs के साथ भी निरंतर स्थान पर चलता है, क्योंकि शीर्ष-स्तरीय थंक्स (निरंतर आवेदक फॉर्म, सीएएफ-एस) कचरा एकत्र किया जा सकता है। क्लोजर की सूचना तालिका में "स्थैतिक संदर्भ सारणी" होती है, जो स्थिर बंदों को सूचीबद्ध करती है जैसे कि
- बंद करने का कोड उनका उल्लेख करता है
- वे या तो शीर्ष-स्तरीय थंक हैं या उनका कोड ट्रांज़िटिव रूप से शीर्ष-स्तरीय थंक्स को संदर्भित करता है
दस्तावेज़ीकरण यहां। यदि जीसी रूट्स से शीर्ष-स्तरीय थंक्स तक नहीं पहुंचा जा सकता है (जिसमें थ्रेड-स्टेट ऑब्जेक्ट्स के ढेर शामिल हैं, तो हमारे मामले में main निष्पादन के तहत बंद होना), ढेर ऑब्जेक्ट्स जो वे इंगित करते हैं उन्हें छोड़ दिया जाता है।
GHC.List से:
cycle :: [a] -> [a]
cycle [] = errorEmptyList "cycle"
cycle xs = xs' where xs' = xs ++ xs'
ध्यान दें कि रिकर्सन में फ़ंक्शन कॉल शामिल नहीं है, लेकिन एक सूची मान xs' शामिल है।
जब पूरी तरह से मजबूर किया जाता है, तो इसे स्मृति में एक पिछड़े सूचक के साथ एक परिपत्र लिंक्ड-सूची के रूप में दर्शाया जाना चाहिए। तब केवल एक सीमित मात्रा में स्मृति की आवश्यकता होती है।
उदाहरण के लिए प्रयास करें अपना खुद का cycle परिभाषित करना:
cycle' xs = xs ++ cycle' xs
चूंकि जीएचसी स्वचालित संस्मरण नहीं करता है, इसलिए इसे स्मृति में एक असीमित सूची उत्पन्न करनी चाहिए।
दरअसल, जीएचसीआई (अडॉप्टिमाइज्ड) में भी, यह मेरी मशीन पर 70M से कम रहता है
> let list1 :: [Int] ; list1 = cycle [1,2,3]
> list1 !! (4*10^9)
2
जबकि यह फट जाता है (>1GB):
> let list2 :: [Int] ; list2 = cycle' [1,2,3]
> list2 !! (4*10^7)
2
संबंधित सवाल
नए सवाल
haskell
हास्केल एक कार्यात्मक प्रोग्रामिंग भाषा है जिसमें मजबूत स्थैतिक टाइपिंग, आलसी मूल्यांकन, व्यापक समानता और संक्षिप्तता समर्थन और अद्वितीय अमूर्त क्षमताओं की विशेषता है।