आलसी कंप्यूटिंग

हास्केल के "कॉलिंग कार्ड" में से एक स्थगित, या आलसी, कंप्यूटिंग है। भाषा की यह विशेषता न केवल कई संभावनाओं को खोलती है, बल्कि कुछ समस्याएं भी पैदा करती है, खासकर कार्यक्रमों की गति के साथ।

इस लेख में मैं यह समझाने की कोशिश करूंगा: आलसी कंप्यूटिंग क्या है, उनका क्या उपयोग किया जा सकता है और उनका उपयोग करते समय प्रदर्शन हानि से कैसे बचा जा सकता है।

आलसी कंप्यूटिंग क्या है?

सामान्य, आलसी नहीं, प्रोग्रामिंग भाषाओं में, गणनाएं सख्त हैं - अर्थात, फ़ंक्शन के तर्कों का मूल्यांकन फ़ंक्शन के निष्पादित होने से पहले किया जाता है।
उदाहरण के लिए, कुछ सार सख्त प्रोग्रामिंग भाषा में:

max(5+3, 4*4) ->
max(8, 4*4) ->
max(8, 16)
16

और हस्केल सहित आलसी भाषाओं में, गणनाएं स्थगित कर दी जाती हैं। सभी गणना (कुछ I / O कार्यों को छोड़कर) तुरंत नहीं की जाती हैं, लेकिन वास्तविक आवश्यकता होने तक स्थगित कर दी जाती हैं।
हास्केल में एक ही उदाहरण:

max (5+3) (4*4) ->
let x = 5+3; y = 4*4 in if x >= y then x else y ->
let x = 8; y = 4*4 in if 8 >= y then 8 else y ->
let x = 8; y = 16 in if 8 >= 16 then 8 else 16 ->
16

यह उदाहरण स्पष्ट रूप से दिखाता है कि उप-संदर्भों (5 + 3 और 4 * 4) की गणना को अंतिम, अर्थात् उस क्षण तक स्थगित कर दिया गया था जब तक कि उनकी तुलना नहीं की जानी थी।
यहां, गणना को रन बनाने वाले "बल" को कंसोल पर आउटपुट माना जा सकता है, अर्थात। आईओ। लेकिन यह एकमात्र तरीका नहीं है।

वादे

इस उदाहरण को लें:

let z = (sum [1..10], reverse "haskell") in ...
(आगे हम मानते हैं कि z का उपयोग भाग में किया जाता है, अन्यथा अभिव्यक्ति का मूल्यांकन बिल्कुल नहीं किया जाएगा)

z एक वादा (eng। थंक) है, बस एक गणना मूल्य नहीं है।
और अगर हम नमूना z के साथ तुलना करेंगे तो क्या होगा?

 let z = (sum [1..10], reverse "haskell") (x, y) = z in ... 

पहले, z एक सरल वादा है, जैसा कि पिछले उदाहरण में है, लेकिन ताकि कंपाइलर यह सत्यापित कर सके कि z वास्तव में पैटर्न से मेल खाता है, उसे z को फ़ॉर्म में "विस्तार" करना होगा: (**, **) । x और y युग्म z के घटकों के अनुरूप वादे हैं।
नमूने के साथ एक और तुलना जोड़ें:

 let z = (sum [1..10], reverse "haskell") (x, y) = z 'l':ys = y in ... 

यह सत्यापित करने के लिए कि y एक सूची है, संकलक इसका मूल्यांकन फॉर्म में ** : ** : ** : **
फिर, वह पहले वादे की गणना करता है: 'l' : **
और सुनिश्चित करें कि y 'l' से शुरू होने वाली एक सूची है, यह पैटर्न से मेल खाता है: 'l':ys = 'l':**
इस उदाहरण में, y बाकी सूची y के अनुरूप वादा होगा।

आइए देखें कि सभी उदाहरणों में z के लिए गणना की गहराई कैसे बदल गई है:

**
(**, **)
(**, 'l':**)

z की आंशिक रूप से गणना की गई थी, और जैसा कि आप अनुमान लगा सकते हैं, हास्केल में लगभग सभी मूल्यों की गणना इस तरह से की जा सकती है। उदाहरण के लिए, एक जोड़ी के लिए सबसे छोटी संभव गणना केवल निर्माता का मूल्यांकन करने के लिए है: (**, **) । एक सूची के लिए, यह **:** या [] है। लेकिन इस फार्म की संख्या मौजूद नहीं है - वे या तो गणना की जाती हैं या नहीं।
जब मूल्य पूरी तरह से गणना नहीं की जाती है, तो वे कहते हैं कि यह कमजोर हेड नॉर्मल फॉर्म (WHNF) में है, और जब पूरी तरह से, तब नॉर्मल फॉर्म में । WHNF में मूल्य, जब पूरी तरह से गणना की जाती है, तो "सामान्य रूप में" चला जाता है। उदाहरण के लिए, यदि हम स्क्रीन पर z प्रदर्शित करते हैं, तो उसका सामान्य रूप होगा (55,"lleksah") । जाहिर है, ऐसे मान जिनके निर्माता के पास कोई तर्क नहीं है, वे WHNF में नहीं हो सकते। अर्थात्, प्रकार जैसे कि बूल, ऑर्ड, इंट, आदि में WHNF नहीं है, और प्रकार हो सकता है, [a], या तो, आदि। की है।

आलसी कार्य

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

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

const 5 undefined
Just undefined

और ये परिणाम देगा:

length undefined
head undefined

आलसी पैटर्न तुलना

न केवल कार्य आलसी हो सकते हैं, बल्कि नमूने के साथ तुलना भी कर सकते हैं। उस नमूने की सख्त तुलना के विपरीत जिसकी हमने पहले ही जांच की है, आलसी लोग गणना करने के वादे नहीं करते हैं, अर्थात, वे संकलन के दौरान उन्हें "तैनात" नहीं करते हैं।
उदाहरण के लिए:

> let f ~(x, y) = 1
> f undefined
1

यहाँ ~(x, y) आलसी पैटर्न है। इसमें एक आलसी फ़ंक्शन के तर्क के समान संपत्ति है: जब हम वहां अपरिभाषित गुजरते हैं, तो एक त्रुटि उत्पन्न नहीं होती है।
एक नमूने के साथ इस तरह की तुलना Control.Arrow में मिल सकती है:

(***) fg ~(x, y) = (fx, gy)

> (const 1 *** const 2) undefined
(1, 2)

लेकिन आपको यह याद रखने की आवश्यकता है कि आलसी पैटर्न का उपयोग केवल तभी किया जाना चाहिए जब प्रकार का एक निर्माता हो।
उदाहरण के लिए:

head' :: [a] -> a
head' ~[] = undefined
head' ~(x:xs) = x

चूँकि हमने बताया कि जब तक यह आवश्यक नहीं है तब तक फ़ंक्शन तर्क की गणना करना आवश्यक नहीं है, यह पता लगाना संभव नहीं है कि हमारे सामने क्या है: एक खाली सूची या इसके लिंक में से एक। फ़ंक्शन हमेशा अपरिभाषित वापस आ जाएगा, क्योंकि पहली अभिव्यक्ति में हमने एक अकाट्य पैटर्न का उपयोग किया था।

आलसी कंप्यूटिंग का उपयोग करना

मांग की गणना

आलसी कंप्यूटिंग का सबसे स्पष्ट प्लस यह है कि यदि कुछ आवश्यक नहीं है, तो इसकी गणना नहीं की जाएगी।
उदाहरण के लिए:

(&&) False _ = False
(&&) True a = a

यदि और फ़ंक्शन का पहला तर्क गलत है, तो दूसरे की गणना क्यों करें यदि यह पहले से ही स्पष्ट है कि परिणाम गलत होगा? शायद दूसरे तर्क के अर्थ का पता लगाने के लिए, यह बहुत समय लेने वाली गणनाओं को ले जाएगा, जिन्हें लैंस संतुलन का उपयोग करके टाला जा सकता है।

कल्पना करें कि आप 3 सबसे छोटी सूची आइटम ढूंढना चाहते हैं।
हास्केल में, यह इस तरह किया जा सकता है:

take 3 (sort xs)

लेकिन एक सख्त भाषा में, यह बेकार है, क्योंकि आपको पूरी सूची को क्रमबद्ध करना होगा। लेकिन आलसी गणनाओं के साथ, हम सूची को तीसरे तत्व के आधार पर क्रमबद्ध करते हैं और बंद कर देते हैं क्योंकि यह गणना जारी रखने के लिए समझ में नहीं आता है।

Memoization

निम्नलिखित कार्य पर विचार करें:

plus a = a+a

> plus (5+3)
16

5 और 3 का योग कितनी बार गणना की गई है? सही उत्तर: एक बार। पहले (5 + 3) - सिर्फ एक वादा, लेकिन जब इसे प्लस फ़ंक्शन के लिए पारित किया गया था, तो इसकी गणना की गई थी और उनके जवाब ने वादे को ही बदल दिया। जब दूसरी बार किसी के मूल्य की आवश्यकता होती है, तो कार्यक्रम ने बिना किसी गणना के, पूर्व के वादे से तैयार परिणाम लिया। यह आलसी कंप्यूटिंग के सबसे महत्वपूर्ण गुणों में से एक है - संस्मरण। एक आलसी भाषा में एक वादा केवल एक बार गणना की जाती है, और फिर गणना के परिणाम "वादे को ओवरराइट" करता है, जिससे कार्यक्रम को बस फिर से गणना करने के बिना, उत्तर का पता लगाने का अवसर मिलता है।
आलसी कंप्यूटिंग की यह संपत्ति डायनेमिक प्रोग्रामिंग में एप्लिकेशन ढूंढती है, जिसे आर्टिकल डायनेमिक प्रोग्रामिंग और लेजी कंप्यूटिंग में अच्छी तरह से दिखाया गया था।

अनंत और लूपिंग डेटा संरचनाएं

आस्थगित कंप्यूटिंग का एक और काफी प्रसिद्ध अनुप्रयोग अनंत डेटा संरचनाओं का निर्माण है।

> [1, 3..] !! 10
21

यहां हम विषम संख्याओं की एक अंतहीन सूची बनाते हैं, और इसके 10 वें तत्व को लेते हैं।

एक उदाहरण अधिक जटिल है:

> fibs = 1:1:zipWith (+) fibs (tail fibs)
> fibs !! 100
573147844013817084101

अनंत सूचियाँ बनाना केवल इसलिए संभव है क्योंकि उनकी गणना तुरंत नहीं की जाती है। दूसरे उदाहरण में, फाइब पहले 1:1:** , लेकिन जब हम इस सूची के निम्नलिखित तत्वों का अनुरोध करते हैं, तो कार्यक्रम को तब तक वादे पूरे करने होंगे जब तक कि हमारी जरूरत पूरी नहीं हो जाती। एक वादा दूसरों को जन्म दे सकता है, इसलिए एक छोटी सूची और वादे से, फाइबोनैचि संख्याओं की एक विशाल श्रृंखला में तंतु बदल सकते हैं।

अब चक्रीय डेटा संरचनाओं पर चलते हैं।

data List a = List {value :: a, next :: List a}

हम इस प्रकार के दो तत्वों को एक अंगूठी में कैसे जोड़ते हैं ताकि एक वस्तु का अगला क्षेत्र दूसरे को इंगित करे?
यदि हम इसे अनिवार्य भाषा में करना चाहते हैं, तो हम पॉइंटर्स का उपयोग करेंगे, लेकिन हास्केल में कोई पॉइंटर्स नहीं हैं। तो ऐसी संरचना कैसे बनाएं?
बहुत सरल:

let x = List "x" y
y = List "y" x
in x

वह सब है। चूंकि सूची अगला फ़ील्ड आलसी है (हमें याद रखना चाहिए कि टाइप कंस्ट्रक्टर एक ही फ़ंक्शन है, और इसके तर्क आलसी हो सकते हैं) इस तरह की "रिंग" बनाने से प्रोग्राम को पूरे ढांचे की गणना करने के प्रयासों में फ़्रीज़ नहीं होगा।

> value . next $ x
"y"

आलसी I / O

केवल सरल I / O फ़ंक्शन वास्तव में सख्त हैं, और बाकी आलसी हैं। यह मक्खी पर फाइलों को पढ़ना और लिखना संभव बनाता है, जैसे कि एक पाइपलाइन पर, बफ़र्स के उपयोग के बिना।
उदाहरण के लिए:

import Data.Char

main = print . map toUpper =<< getContents

कार्यक्रम ऊपरी पाठ में आते ही प्रदर्शित होगा।

आलसी कम्प्यूटिंग का उपयोग कर समस्याएं

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

लेकिन गणना को कम आलसी बनाने के तरीके हैं, जिन्हें अब हम मानते हैं।

seq

इस सरल उदाहरण पर विचार करें:

 main = print . sum' $ [1..1e6] sum' [] = 0 sum' (l:ls) = l + sum' ls 

यहां हम 1 से 1e6 तक संख्याओं का योग पाते हैं और इसे कंसोल पर प्रिंट करते हैं। लेकिन यदि आप कार्यक्रम चलाने की कोशिश करते हैं, तो आपको यह संदेश दिखाई देगा:

$ ./test
Stack space overflow: current size 8388608 bytes.
Use `+RTS -Ksize -RTS' to increase it.

स्टैक ओवरफ्लो क्यों होता है? आइए देखें कि राशि 'फंक्शन की गणना कैसे की जाएगी:
1 + (1 + (1 + ... (1 + sum' [])))

चूँकि sum' ls की गणना में देरी हो रही है, हमें ढेर सारे नेस्टेड वादे मिलते हैं जो स्टैक पर जगह लेते हैं। इससे छुटकारा पाने के लिए, आपको किसी भी तरह की गणना करने का वादा करना होगा, संचित नहीं। और इसके लिए हमारे पास एक seq फ़ंक्शन है। इसमें दो तर्क दिए गए हैं, जिनमें से पहला मूल्यांकन किया गया है, और दूसरा वापस लौटाया गया है। आइए इसे यहां लागू करने का प्रयास करें।

सबसे पहले, हम पूंछ पुनरावृत्ति का उपयोग करने के लिए राशि 'फ़ंक्शन को फिर से लिखते हैं:

 main = print . sum' $ [1..1e6] sum' ls = go 0 ls where go n [] = n go n (l:ls) = go (l + n) ls 

अब अतिरिक्त गणना करना मुश्किल नहीं होगा:

 main = print . sum' $ [1..1e6] sum' ls = go 0 ls where go n [] = n go n (l:ls) = let s = l + n in s `seq` go s ls 

Seq बाद में स्थगित करने के बजाय, राशि की गणना करने के लिए बाध्य करता है।

$ ./test
5.000005e11

अब त्रुटि नहीं होती है।

आइए थोड़ा जटिल उदाहरण का प्रयास करें: तत्वों के योग के अलावा, हम उनकी संख्या की गणना भी करते हैं।

 main = print . sum' $ [1..1e6] sum' ls = go (0, 0) ls where go (n, d) [] = (n, d) go (n, d) (l:ls) = let t = (l + n, d + 1) in t `seq` go t ls 

$ ./test
Stack space overflow: current size 8388608 bytes.
Use `+RTS -Ksize -RTS' to increase it.

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

 main = print . sum' $ [1..1e6] sum' ls = go (0, 0) ls where go (n, d) [] = (n, d) go (n, d) (l:ls) = let s = l + n d' = d + 1 in s `seq` d' `seq` go (s, d') ls 

$ ./test
(5.000005e11,1000000)

थोड़ा बदसूरत, लेकिन यह काम करता है। स्थिति जब आपको किसी चीज़ की पूरी तरह से गणना करने की आवश्यकता होती है, तो यह बहुत दुर्लभ नहीं है, इसलिए इसके लिए एक विशेष मॉड्यूल बनाया गया था। आइए इसे आजमाएँ:

 import Control.DeepSeq (deepseq) main = print . sum' $ [1..10^6] sum' :: [Integer] -> (Integer, Int) sum' ls = go (0, 0) ls where go (n, d) [] = (n, d) go (n, d) (l:ls) = let t = (l + n, d + 1) in t `deepseq` go t ls 

डीपसेक फ़ंक्शन सामान्य रूप तक मानों की पूरी तरह से गणना करता है।

बैंग पैटर्न

कठोरता के अधिक सुविधाजनक संकेत के लिए, एक संकलक विस्तार बनाया गया था - बैंग पैटर्न। यह आपको केवल विस्मयादिबोधक बिंदु द्वारा तर्क की गंभीरता को इंगित करने की अनुमति देता है। इस एक्सटेंशन का उपयोग करके, हम अपने कोड को इस तरह दोबारा लिख ​​सकते हैं:

 {-# LANGUAGE BangPatterns #-} main = print . sum' $ [1..10^6] sum' :: [Integer] -> (Integer, Int) sum' ls = go (0, 0) ls where go (!n, !d) [] = (n, d) go (!n, !d) (l:ls) = go (l + n, d + 1) ls 

सब कुछ पहले की तरह काम करेगा।
बैंग पैटर्न हमें न केवल फ़ंक्शन तर्कों की गंभीरता को निर्दिष्ट करने की अनुमति देता है, बल्कि डेटा संरचनाओं के क्षेत्र भी, उदाहरण के लिए:

 {-# LANGUAGE BangPatterns #-} data SPair ab = SPair !a !b deriving Show main = print . sum' $ [1..10^6] sum' :: [Integer] -> SPair Integer Int sum' ls = go (SPair 0 0) ls where go (SPair nd) [] = SPair nd go (SPair nd) (l:ls) = go (SPair (l + n) (d + 1)) ls 

$ ./test
SPair 500000500000 1000000

SPair एक सख्त युगल है। इसके क्षेत्रों के मूल्यों की हमेशा गणना की जाएगी, जो फिर से, वादों को जमा करने की अनुमति नहीं देता है।

निष्कर्ष

इस लेख में, मैंने समझाने की कोशिश की कि आलसी कंप्यूटिंग का सामना कैसे किया जाए। मुझे आशा है कि इसे पढ़ने के बाद, आप यह समझना शुरू कर देंगे कि आस्थगित गणनाओं को लागू करने के लिए कहां और कैसे सबसे अच्छा है, उन्हें बिल्कुल क्यों आवश्यक है।

प्रयुक्त सामग्री की सूची

हास्केल / आलस्य
रूपरेखा और अनुकूलन