विभाजित करें और जीतें, साथ ही हास्केल में अंतहीन धाराएं

सभी पाठकों को नमस्कार!
नीचे मेरी बात यह है कि हमारे विश्वविद्यालय में हास्केल पाठ्यक्रम की स्लाइड्स के अध्याय 14 को मैंने कैसे समझा।
इसलिए, आज हम निम्नलिखित दो विषयों के बारे में बात करेंगे:

• दि डिवाइड एंड कॉनकॉल प्रिंसिपल
• अंतहीन प्रवाह के साथ काम करें

इस क्षेत्र के विशेषज्ञ, कृपया टिप्पणी करें और अगर अशुद्धि है तो सही करें। मुझे टिप्पणियों में प्रश्नों का उत्तर देने में खुशी होगी।

फूट डालो और जीतो

संभवतः आप पहले ही प्रोग्रामिंग में "डिवाइड एंड कॉनकर" के सिद्धांत को कई बार देख चुके हैं। यदि समस्या प्राथमिक है , तो उसे तुरंत हल करें। यदि नहीं, तो इसे छोटी "उप-समस्याओं" में विभाजित करें और ऐसा तब तक करें जब तक कि सभी समस्याएं प्राथमिक न हों। सभी प्रारंभिक समस्याओं को हल करने के बाद, उन्हें मूल समस्या का समाधान प्राप्त करने के लिए "कनेक्ट" होना चाहिए।
समस्या को (और सभी उप-समस्याओं को) टाइप p , और सभी समाधानों में टाइप s । यह एक उच्च-क्रम फ़ंक्शन divideAndConquer को खोजने के लिए आवश्यक है जो टाइप p की समस्या को स्वीकार करता है और परिणामस्वरूप टाइप s समाधान का उत्पादन करता है। ऐसा करने के लिए, हमें सहायक कार्यों (= divideAndConquer तत्वों) की आवश्यकता है जो divideAndConquer एल्गोरिथ्म के कार्य को कार्यान्वित करते हैं, अर्थात्:

 indiv :: p -> Bool 

यह फ़ंक्शन प्रश्न का उत्तर देता है: "क्या समस्या को कई उप-समस्याओं में विभाजित करना संभव है?" यदि हाँ, तो True पर लौटें। यदि नहीं, तो यह समस्या प्राथमिक है, और इसे solve फ़ंक्शन का उपयोग करके हल किया जा सकता है।

 solve :: p -> s 

जैसा कि नाम से ही स्पष्ट है, यह फ़ंक्शन प्राथमिक समस्या को हल करता है और टाइप s का समाधान तैयार करता है।

 divide :: p -> [p] 

यदि समस्या प्राथमिक नहीं है, तो हम इसे कई उप-समस्याओं में विभाजित करते हैं, अर्थात्। एक समस्या p हम कई समस्याएं [p] , जिन्हें हल करना बहुत आसान है।

 combine :: p -> [s] -> s 

सभी प्रारंभिक समस्याओं को हल करने के बाद, उन्हें एक ही समाधान में इकट्ठा करना आवश्यक है। आप यहां p क्यों पूछते हैं? कभी-कभी, समस्या का हिस्सा पहले से ही समाधान का हिस्सा होता है जिसे अंतिम उत्तर के लिए उपयोग किया जाना चाहिए (हम इसे नीचे दिए गए उदाहरण में देखेंगे)।

तो यह सार्वभौमिक divideAndConquer divideAndConquer दिखता divideAndConquer ? फ़ंक्शन की परिभाषा इस प्रकार है:

 divideAndConquer :: (p -> Bool) -> (p -> s) -> (p -> [p]) -> (p -> [s] -> s) -> p -> s 

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

 divideAndConquer :: (p -> Bool) -> (p -> s) -> (p -> [p]) -> (p -> [s] -> s) -> p -> s divideAndConquer indiv solve divide combine initPb = dAC initPb where dAC pb | indiv pb = solve pb | otherwise = combine pb (map dAC (divide pb)) 

यदि समस्या (pb) को छोटी उप-समस्याओं में विभाजित नहीं किया जाता है, तो हम इसे indiv pb = solve pb । यदि यह है, तो हम इस समस्या को साझा करते हैं, इसे हल करते हैं और परिणामों को जोड़ते हैं।

आइए देखें कि quickSort उदाहरण का उपयोग करके इस तरह के फ़ंक्शन को कैसे लागू किया quickSort । त्वरित सॉर्ट फ़ंक्शन उन तत्वों की एक सरणी को स्वीकार करता है जिनकी तुलना की जा सकती है और समान तत्वों के साथ एक सरणी का निर्माण करता है, लेकिन क्रमबद्ध क्रम में:

 quickSort :: Ord a => [a] -> [a] 

अब हमें विशेष रूप से क्विक सॉर्ट के लिए divideAndConquer एल्गोरिथ्म के हमारे चार तत्वों पर निर्णय लेने की आवश्यकता है। समस्या को तब अविभाज्य (= indiv) माना जाता है जब सरणी की लंबाई 1 से कम या बराबर होती है। त्वरित छँटाई में समस्याओं के लिए ऐसा कोई समाधान (= हल) नहीं होता है, क्योंकि यदि सरणी की लंबाई 1 है, तो यह सरणी क्रमबद्ध है। आप एक सरणी को विभाजित (= विभाजित) कर सकते हैं: पहला तत्व ले लो और दो सरणियों का निर्माण करें - एक सभी तत्वों के साथ <= पहला तत्व का, दूसरा सभी तत्वों के साथ> पहला तत्व का। सॉर्ट किए गए सरणियों (= गठबंधन) को निम्नानुसार संयोजित करें: पहला तत्व मध्य में रखा गया है, इसके बाईं ओर सभी इस तत्व से कम संख्या में हैं, और दाईं ओर सभी संख्याएं इस तत्व से बड़ी हैं।
DivideAndConquer के मुख्य चार घटकों को परिभाषित करने के बाद, आप सुरक्षित रूप से एक फ़ंक्शन लिख सकते हैं:

 quickSort :: Ord a => [a] -> [a] quickSort lst = divideAndConquer indiv solve divide combine lst where indiv ls = length ls <= 1 solve = id divide (l:ls) = [[x | x <- ls, x <= l], [x | x <- ls, x > l]] combine (l:_) [l1,l2] = l1 ++ [l] ++ l2 

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

 fib :: Integer -> Integer fib n = divideAndConquer indiv solve divide combine n where indiv n = (n==0) || (n==1) solve n | n == 0 = 0 | n == 1 = 1 | otherwise = error "Input argument must be >= 0" divide n = [n-2, n-1] combine _ [l1,l2] = l1 + l2 

दुर्भाग्य से, इस फ़ंक्शन में घातीय जटिलता है, और इस समस्या को हल करने के लिए अधिक कुशल तरीके हैं।

निष्कर्ष

divideAndConquer एल्गोरिथ्म में 4 indiv, solve, divide, combine होते हैं: indiv, solve, divide, combine । यदि किसी भी समस्या के लिए आप उन सभी को निर्धारित कर सकते हैं, तो आप सुरक्षित रूप से इस पद्धति का उपयोग कर सकते हैं। हालांकि, यह मत भूलो कि "विभाजित और जीतना" हमेशा समस्या का इष्टतम समाधान नहीं है।

अंतहीन धाराएँ

हास्केल की एक विशेषता यह है कि यह अंतहीन थ्रेड्स के साथ काम कर सकता है। इस मामले में धारा "अनंत सरणी" का पर्याय है (संलग्न आलसी सूची)। उदाहरण के लिए, [1..] सभी प्राकृतिक संख्याओं की एक सरणी है। ऐसी धाराएँ आपको "आलसी मूल्यांकन" करने की अनुमति देती हैं।
आइए एक एल्गोरिथ्म लिखने की कोशिश करें जो सभी primes (= primes की धारा) पैदा करता है। हम एराटोस्थनीज की छलनी का उपयोग करके एक प्रमुख की गणना करेंगे। विचार यह है कि दो से "अनंत" तक सभी प्राकृतिक संख्याओं की एक सरणी है। बाईं ओर की संख्या हमेशा एक प्रमुख संख्या होती है। जब भी हम एक अभाज्य संख्या लेते हैं, हम सूची से उन सभी संख्याओं को हटा देते हैं जो इस संख्या से शेष के बिना विभाज्य हैं, अर्थात्। के साथ शुरू:
2, 3, 4, 5, 6, 7, 8, 9, 10, 11...
संख्या 2 अभाज्य है, उन सभी संख्याओं को पार करें जो 2 से विभाज्य हैं:
2, 3, 5, 7, 9, 11...
संख्या 3 प्रधान है, उन सभी संख्याओं को पार करें जिन्हें 3 से विभाजित किया गया है:
2, 3, 5, 7, 11...
आदि

चलनी (= छलनी) एक सरणी लेती है और उपरोक्त ऑपरेशन करती है:

 sieve :: [Integer] -> [Integer] sieve (x:xs) = x : sieve [y | y <- xs, mod yx > 0] 

अब primes (= primes) की धारा इस प्रकार लिखी जा सकती है:

 primes :: [Integer] primes = sieve [2..] 

अब, जब कॉल करते हैं, तो primes कंसोल के लिए primes होंगे। यह कैसे काम करता है?
primes
->> sieve [2..]
->> 2 : sieve [y | y <- [3..], mod y 2 > 0]
->> 2 : 3 : sieve [z | z <- [y | y <- [4..], mod y 2 >0], mod z 3 > 0]
->> ...
->> 2 : 3 : sieve [ z | z <- [5, 7, 9..], mod z 3 > 0]
->> ...
->> 2 : 3 : sieve [5, 7, 11, ...
->> ...

"अच्छा, अच्छा, फिर क्या?" आप पूछते हैं। इस तरह के प्रवाह के साथ कैसे काम करना है, उनके साथ क्या संचालन किया जा सकता है?
तथाकथित "नमूनाकरण" सिद्धांत है, जो आपको अनंत धारा से केवल कुछ तत्वों का चयन करने की अनुमति देता है, उदाहरण के लिए:

• take 5 primes ->> [2,3,5,7,11] पहले 5 प्राइम
• primes !! 42 ->> 191 primes !! 42 ->> 191 42 वें प्रधान
• ((take 5) . (drop 5)) primes ->> [13,17,19,23,29] छठे से 10 वें तक के प्राइम

"फ़िल्टरिंग" का सिद्धांत, जो आपको उदाहरण के लिए, प्रिम्स के सेट का सबसेट चुनने की अनुमति देता है:

• filter (>1000) primes ->> [1009,1013,1019,... सभी प्राइम 1000 से अधिक हैं
• [n | n <- primes, hasThreeOnes n] ->> [1117,1151,1171,1181,1511,... [n | n <- primes, hasThreeOnes n] ->> [1117,1151,1171,1181,1511,... सभी [n | n <- primes, hasThreeOnes n] ->> [1117,1151,1171,1181,1511,... जहां तीन होते हैं ( hasThreeOnes फ़ंक्शन hasThreeOnes कार्यान्वयन पाठक की कल्पना के लिए छोड़ दिया hasThreeOnes )

इस प्रकार का एक छोटा नोट: filter (<10) primes ->> [2,3,5,7, कभी भी इसका निष्पादन पूरा नहीं करेगा, क्योंकि फ़िल्टर यह नहीं जानता कि संख्या 10 से कम होगी या नहीं और उनकी खोज जारी है। बढ़ते कार्यों के लिए, इसे इस तरह से किया जा सकता है: takeWhile (<10) primes ->> [2,3,5,7] ।

"परिवर्तन" का सिद्धांत, जो धारा की प्रत्येक संख्या के लिए एक निश्चित क्रिया करता है, उदाहरण के लिए:

• [n*n | n <- primes] ->> [4,9,25,49,... [n*n | n <- primes] ->> [4,9,25,49,... primes के वर्गों की धारा
• [n-1 | n <- primes] ->> [1,2,4,6,... [n-1 | n <- primes] ->> [1,2,4,6,... अभाज्य संख्याओं के अग्रदूतों की धारा
• [sum [2..n] | n <- primes] ->> [2,5,14,27,65,90,... [sum [2..n] | n <- primes] ->> [2,5,14,27,65,90,... सरल से दो तक प्राकृतिक संख्याओं की धारा।

निष्कर्ष

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

• नमूना
• छानने
• परिवर्तन