गतिशील प्रोग्रामिंग और आलसी कंप्यूटिंग

डायनेमिक प्रोग्रामिंग कई जटिल समस्याओं को हल करने में एक महत्वपूर्ण दृष्टिकोण है, जो कार्य को उप-भागों में विभाजित करने और एक बार इन उप-प्रकारों को हल करने के आधार पर होता है, भले ही वे कई अन्य उप-भाग का हिस्सा हों। उन लोगों के लिए जो केवल कार्यात्मक प्रोग्रामिंग में महारत हासिल करने के लिए शुरू कर रहे हैं, अक्सर सवाल उठता है: “ यदि आप परिणामों को बचाने के लिए चर का उपयोग नहीं करते हैं तो उप-कार्यों को फिर से हल करने से कैसे बचें? "। इस समस्या में, कार्यात्मक प्रोग्रामिंग की एक विशेषता - चर की कमी - सबप्रॉबल्म को हल करने के परिणामों को कैश करना मुश्किल बनाता है, लेकिन एक अन्य विशेषता - आलसी कंप्यूटिंग की मदद करेगी।

पकड़ने की समस्या पर विचार करें:

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

इस प्रकार, एक कोशिका के गटर को खोजने के लिए, आपको इसके पड़ोसी (यदि यह स्वयं एक गटर नहीं है) के गटर को खोजने की आवश्यकता है, और यह स्पष्ट है कि कई अलग-अलग कोशिकाओं से पानी इकट्ठा हो सकता है और एक ही गटर में एक ही मार्ग से बह सकता है।
बल्कि एक सरल पुनरावर्ती एल्गोरिथ्म का ख्याल आता है:

 drainOf सेल = 
   सबसे कम मामला। की सेल
     कुछ भी नहीं → सेल
     बस nb → drainOf nb

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

 प्रिंट (drainOf सेल)
 प्रिंट (drainOf सेल)

लेकिन निम्नलिखित कोड में, फ़ंक्शन को केवल एक बार बुलाया जाएगा:

 चलो नाली = drainOf सेल
 ड्रेन प्रिंट करें
 ड्रेन प्रिंट करें

यानी हमें किसी तरह यह इंगित करने की आवश्यकता है कि हमारा मतलब समान भाव से है, तो आलसी गणना हमारे लिए काम करेगी।

 कोशिकाएं = ((1,1), (चौड़ाई, ऊंचाई))

 ऊँचाई :: (इंट, इंट) → इंट

 - यहाँ यह है, सभी कोशिकाओं की नालियों की एक सरणी!  लेकिन इसकी गणना आलस्य से की जाती है
 - यानी  अभी तक यह केवल ड्रेनऑफ के लिए कॉल की एक सूची है, लेकिन इसके परिणाम नहीं हैं
 नालियां = सरणी कोशिकाएं [(सेल, ड्रेनऑफ सेल) |  सेल cell रेंज सेल]
  
 drainOf सेल = 
   सबसे कम मामला। की सेल
     कुछ भी नहीं → सेल
     बस nb → नालियाँ!  nb - स्टॉक ऐरे के तत्व तक पहुंच
     - यहाँ पहली कॉल पर, drainOf की गणना घटित होगी,
     - और दूसरे पर - कैश्ड परिणाम की वापसी

 निम्नतमन्यूजबोरोफ़ (x, y) =
   पड़ोसियों को फ़िल्टर करने दो (inRange cells) 
                         (x, y-1), (x + 1, y), (x, y + 1), (x-1, y)]
       न्यूनतम = न्यूनतम (पड़ोसियों की तुलना करें)
   में
       यदि ऊँचाई सबसे कम ≥ ऊँचाई (x, y)
             फिर कुछ नहीं
             और सबसे कम

यह सब, मुझे आशा है कि आप समझ गए होंगे कि आलसी कंप्यूटिंग क्या है।

UPD: मैंने पूर्ण कार्यक्रम और इसके आउटपुट को जोड़ने का फैसला किया, ताकि निराधार न हो।

 डेटा आयात करें
 आयात Debug.Trace (ट्रेस)
 आयात नियंत्रण। मोनाड (forM_)
 डेटा आयात करें। न्यूनतम (न्यूनतम, पारगमन)
 आयात Data.Function (पर)

 - सरल डेटा -

 कोशिकाएं = (1,1), (3,3)

 altitudes = listArray कोशिकाएं $ concat $ transpose [
     [१०, 10, १०],
     [१५, ३, १५],
     [२०, २५, २०]]

 - सामान्य कार्य -

 ऊँचाई :: (इंट, इंट) → इंट
 ऊंचाई सेल = ऊंचाई!  सेल

 निम्नतमन्यूजबोरोफ़ (x, y) =
   पड़ोसियों को फ़िल्टर करने दो (inRange cells) 
                         (x, y-1), (x + 1, y), (x, y + 1), (x-1, y)]
       न्यूनतम = न्यूनतम (पड़ोसियों की तुलना करें)
   में
       यदि ऊँचाई सबसे कम ≥ ऊँचाई (x, y)
             फिर कुछ नहीं
             और सबसे कम

 PrintArray arrest =
     let (sx, sy), (ex, eye) = सीमाएं गिरफ्तारी
         PrintRow y = forM_ [sx..ex] (λ x → putStr (शो (गिरफ्तारी! (x, y)) ++ "\ t"))
     में
         forM_ [sy..ey] (λ y → PrintRow y »putStrLn" ")

 मुख्य = 
   PrintArray ऊंचाई
      putStrLn "- नालियाँ -------------"
      प्रिंटअरे नालियां
      putStrLn "- नालियाँ - ------------"
      प्रिंटअरे नालियाँ ra

 - सरल पुनरावृत्ति -

 नालियां = सरणी कोशिकाएं [(सेल, ड्रेनऑफ सेल) |  सेल cell रेंज सेल]

 drainOf सेल |  ट्रेस ("drainOf" ++ शो सेल) गलत = अपरिभाषित
 drainOf सेल = 
   सबसे कम मामला। की सेल
     कुछ भी नहीं → सेल
     बस nb → drainOf nb

 - आलसी कैशिंग -

 नालियाँ cells = सरणी कोशिकाएँ [(कोशिका, अपवाह | कोशिका) |  सेल cell रेंज सेल]

 drainOf O सेल |  ट्रेस ("drainOf ++" ++ शो सेल) गलत = अपरिभाषित
 drainOf O सेल = 
   सबसे कम मामला। की सेल
     कुछ भी नहीं → सेल
     बस nb → नालियां ra!  nb

परिणाम:

 १० 10 १०	
 १५ ३ १५	
 २० २५ २०	
 - नालियाँ -------------
 drainOf (1,1)
 drainOf (2.1)
 drainOf (2.2)
 drainOf (2.1)
 drainOf (2.2)
 drainOf (3.1)
 drainOf (2.1)
 drainOf (2.2)
 (2.2) (2.2) (2.2)	
 drainOf (1,2)
 drainOf (2.2)
 drainOf (2.2)
 drainOf (3.2)
 drainOf (2.2)
 (2.2) (2.2) (2.2)	
 drainOf (1.3)
 drainOf (1,2)
 drainOf (2.2)
 drainOf (2,3)
 drainOf (2.2)
 drainOf (3.3)
 drainOf (3.2)
 drainOf (2.2)
 (2.2) (2.2) (2.2)	
 - नालियाँ ------------
 drainOf '(1,1)
 drainOf '(2.1)
 drainOf '(2,2)
 drainOf '(3.1)
 (2.2) (2.2) (2.2)	
 drainOf '(1,2)
 drainOf '(3.2)
 (2.2) (2.2) (2.2)	
 drainOf '(1,3)
 drainOf '(2,3)
 drainOf '(3.3)
 (2.2) (2.2) (2.2)	

जैसा कि आप देख सकते हैं, पहले विकल्प ने प्रत्येक सेल के स्टॉक की बार-बार गणना की, जबकि दूसरे विकल्प ने ठीक एक बार किया।