हास्केल: आंशिक रूप से आलसी मूल्यांकन वाले परिणाम

Question

मेरे पास एक बहुत बड़ा निर्णय पेड़ है। इसका उपयोग निम्नानुसार किया जाता है:

-- once per application start 
t :: Tree 
t = buildDecisionTree 
-- done several times 
makeDecision :: Something -> Decision 
makeDecision something = search t something 

यह निर्णय पेड़ स्मृति में फिट होने के लिए बहुत बड़ा तरीका है। लेकिन, आलसी मूल्यांकन के लिए धन्यवाद, यह केवल आंशिक रूप से मूल्यांकन किया जाता है।

समस्या यह है कि ऐसे परिदृश्य हैं जहां पूरे पेड़ का मूल्यांकन करने के लिए सभी संभावित निर्णयों की कोशिश की जाती है। यह समाप्त नहीं होगा, लेकिन स्मृति मेमोरी या तो कारण नहीं होना चाहिए। इसके अलावा, अगर इस प्रक्रिया को निरस्त कर दिया गया है, तो स्मृति उपयोग कम नहीं होता है, क्योंकि एक विशाल उप-राशि का अभी भी मूल्यांकन किया जाता है।

हर बार पेड़ का पुनर्मूल्यांकन करना होगा हर बार makeDecision कहा जाता है, लेकिन यह कैशिंग निर्णयों के लाभों को खो देगा और makeDecision को काफी धीमा कर देगा।

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

Answer 1

शुद्ध हैकेल में यह संभव नहीं है, प्रश्न Can a thunk be duplicated to improve memory performance? देखें (जैसा कि @shang द्वारा इंगित किया गया है)। हालांकि, आप इसे आईओ के साथ कर सकते हैं।

हम मॉड्यूल हेड के साथ शुरू करते हैं और केवल उस प्रकार और फ़ंक्शंस को सूचीबद्ध करते हैं जो इस मॉड्यूल को बनाना चाहिए (जो unsafePerformIO का उपयोग करेगा) सुरक्षित। बिना असुरक्षित पैराफॉर्मियो के ऐसा करना भी संभव है, लेकिन इसका मतलब यह होगा कि उपयोगकर्ता को आईओ में अपना अधिक कोड रखना होगा।

{-# LANGUAGE ExistentialQuantification #-} 
module ReEval (ReEval, newReEval, readReEval, resetReEval) where 

import Data.IORef 
import System.IO.Unsafe 

हम जानते हैं कि एक तरीका है कि सभी साझा करने से बचाता है, समारोह और एक दूसरे से दूर तर्क रख कर में कोई मान संग्रहीत करता है, और केवल समारोह लागू होते हैं जब हम मूल्य चाहते हैं एक डेटा प्रकार परिभाषित करते हुए शुरू करते हैं। नोट unsharedValueद्वारा दिए गए मान साझा किया जा सकता है, लेकिन अन्य आमंत्रण की वापसी मान के साथ नहीं (समारोह संभालने कुछ गैर तुच्छ कर रही है):

data Unshared a = forall b. Unshared (b -> a) b 

unsharedValue :: Unshared a -> a 
unsharedValue (Unshared f x) = f x 

अब हम द्वारा रीसेट करने संगणना के बारे में हमारी डेटा के प्रकार को परिभाषित । हमें गणना और वर्तमान मूल्य को स्टोर करने की आवश्यकता है। उत्तरार्द्ध IORef में संग्रहीत है, क्योंकि हम इसे रीसेट करने में सक्षम होना चाहते हैं।

data ReEval a = ReEval { 
    calculation :: Unshared a, 
    currentValue :: IORef a 
    } 

एक ReEval बॉक्स में कोई मान लपेट के लिए, हम एक समारोह और एक बहस की आवश्यकता है। क्यों न केवल a -> ReEval a? क्योंकि पैरामीटर को साझा करने से रोकने का कोई तरीका नहीं होगा।

newReEval :: (b -> a) -> b -> ReEval a 
newReEval f x = unsafePerformIO $ do 
    let c = Unshared f x 
    ref <- newIORef (unsharedValue c) 
    return $ ReEval c ref 

पढ़ना आसान है: बस IORef से मूल्य प्राप्त करें। unsafePerformIO का यह उपयोग सुरक्षित है क्योंकि हम हमेशा unsharedValue c का मान प्राप्त करेंगे, हालांकि इसकी एक अलग "प्रति" है।

readReEval :: ReEval a -> a 
readReEval r = unsafePerformIO $ readIORef (currentValue r) 

और अंततः रीसेटिंग। मैंने इसे आईओ मोनैड में छोड़ा, क्योंकि यह unsafePerformIO में लपेटने वाले अन्य फ़ंक्शन से कम सुरक्षित नहीं होगा, लेकिन पर उपयोगकर्ता नियंत्रण देने का यह सबसे आसान तरीका है जब रीसेटिंग वास्तव में होती है।आप जोखिम नहीं लेना चाहते हैं कि resetReEval पर आपकी सभी कॉल आलसी देरी हो रही हैं जब तक कि आपकी मेमोरी समाप्त न हो या यहां तक ​​कि अनुकूलित भी हो क्योंकि उपयोग करने के लिए कोई वापसी मूल्य नहीं है।

resetReEval :: ReEval a -> IO() 
resetReEval r = writeIORef (currentValue r) (unsharedValue (calculation r)) 

यह मॉड्यूल का अंत है। यहाँ उदाहरण कोड है:

import Debug.Trace 
import ReEval 
main = do 
    let func a = trace ("func " ++ show a) negate a 
    let l = [ newReEval func n | n <- [1..5] ] 
    print (map readReEval l) 
    print (map readReEval l) 
    mapM_ resetReEval l 
    print (map readReEval l) 

और यहाँ आप यह क्या उम्मीद करता है कि देख सकते हैं:

$ runhaskell test.hs 
func 1 
func 2 
func 3 
func 4 
func 5 
[-1,-2,-3,-4,-5] 
[-1,-2,-3,-4,-5] 
func 1 
func 2 
func 3 
func 4 
func 5 
[-1,-2,-3,-4,-5]