🧝🏾 🔻 🕉️ हम एक कार्यात्मक शैली में यैंडेक्स.इंटरव्यू कार्यों को हल करते हैं 👩‍🚒 ⏰ 👌🏼

कुछ महीने पहले, यैंडेक्स के ब्लॉग में एक लेख दिखाई दिया था जिसमें साक्षात्कार के एल्गोरिथम अनुभाग के पारित होने पर चर्चा की गई थी। अन्य बातों के अलावा, इस लेख में, यैंडेक्स द्वारा अपने उम्मीदवारों को दिए गए कार्यों के समान एक विशेष प्रतियोगिता के लिए एक लिंक दिया गया था।

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

कौन परवाह करता है कि अंततः इसके बारे में क्या आया, बिल्ली का स्वागत है।

A. पत्थर और गहने

लोअरकेस लैटिन अक्षरों की दो पंक्तियाँ दी गई हैं: स्ट्रिंग जे और स्ट्रिंग एस। स्ट्रिंग जे में शामिल अक्षर "गहने" हैं और स्ट्रिंग एस में शामिल "पत्थर" हैं। यह निर्धारित करना आवश्यक है कि एस से कितने वर्ण एक साथ "गहने" हैं। सीधे शब्दों में, आपको यह जाँचने की आवश्यकता है कि S के कितने अक्षर J में हैं।

पहला कार्य एक वार्म-अप है, हम इसे "माथे पर" हल करेंगे। हम फ़ंक्शन ज्वेलरी को परिभाषित करते हैं :: स्टिंग -> स्ट्रिंग -> इंट , जो दूसरे तर्क द्वारा पारित सूची के दृढ़ संकल्प का उपयोग करते हुए, पहली सूची में संसाधित किए जा रहे आइटम के सभी मामलों को प्रस्तुत करता है। इन उद्देश्यों के लिए, हम elemInt फ़ंक्शन को elem फ़ंक्शन के आधार पर परिभाषित करते हैं, जो अंतिम के विपरीत, True या गलत नहीं लौटेगा, लेकिन नंबर 0 या 1. मुख्य फ़ंक्शन में, आपको केवल दो लाइनें पढ़ने की आवश्यकता है, उन्हें संबंधित फ़ंक्शन में पास करें और परिणाम प्रिंट करें। परीक्षण प्रणाली का निर्णय ठीक है, हम दूसरे कार्य को पास करते हैं।

jeweleryCount :: String -> String -> Int jeweleryCount j = foldr ((+).(elemInt j)) 0 where elemInt sx = fromEnum $ elem xs main :: IO () main = do j <- getLine s <- getLine print $ jeweleryCount js

इसे और अन्य कार्यों को हल करने के लिए स्रोत कोड भी जीथब रिपॉजिटरी में उपलब्ध है।

B. लगातार इकाइयाँ

बाइनरी वेक्टर में इकाइयों का सबसे लंबा अनुक्रम खोजना और इसकी लंबाई प्रिंट करना आवश्यक है।

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

इनपुट डेटा को पढ़ने के लिए, हम फ़ंक्शन getUserInputs :: IO [Char] को परिभाषित करते हैं, जिसमें हम पहले नंबर n - सूची का आकार पढ़ते हैं, और फिर कॉम्बिनेटर प्रतिकृति का उपयोग करके हम एक फ़ंक्शन प्राप्त करते हैं जो फ़ंक्शन को कॉल करेगा << get> getLine n बार और परिणाम को एक सूची में मर्ज करें ।

 import Control.Monad (replicateM) onesCount :: [Char] -> Int onesCount xs = onesCount' xs 0 0 where onesCount' "" max curr | max > curr = max | otherwise = curr onesCount' (x:xs) max curr | x == '1' = onesCount' xs max $ curr + 1 | curr > max = onesCount' xs curr 0 | otherwise = onesCount' xs max 0 getUserInputs :: IO [Char] getUserInputs = do n <- read <$> getLine :: IO Int replicateM n $ head <$> getLine main :: IO () main = do xs <- getUserInputs print $ onesCount xs

हम निर्णय भेजते हैं, फैसला ठीक है। हम आगे बढ़ते हैं।

C. डुप्लिकेट निष्कासन

गैर-घटते क्रम में दिए गए 32-बिट पूर्णांक का एक सरणी दिया गया है। इससे सभी पुनरावृत्ति को हटाने के लिए आवश्यक है।

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

 import Control.Monad initial :: IO Int initial = do a <- read <$> getLine print a return a deleteDoubles :: Int -> Int -> IO() deleteDoubles 0 _ = return () deleteDoubles ta = do b <- read <$> getLine unless (a == b) $ print b deleteDoubles (t-1) b main :: IO () main = do t <- read <$> getLine unless (t < 1) $ initial >>= deleteDoubles (t-1)

हम समाधान भेजते हैं, यह सभी परीक्षणों को पास करता है, और ऐसा लगता है कि हम अगले कार्य पर आगे बढ़ सकते हैं, लेकिन मेरी राय में, आईओ मोनड में काम करने वाले फ़ंक्शन का पुनरावर्ती कॉल संक्षिप्त से अधिक भ्रामक है। आइए इसे सुधारने का प्रयास करें।

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

 import Control.Monad deleteDoubles' _ [] = [] deleteDoubles' prev (x:xs) | prev /= x = x:(deleteDoubles' x xs) | otherwise = deleteDoubles' x xs deleteDoubles (x:xs) = x:deleteDoubles' x xs getUserInputs :: Int -> IO [Int] getUserInputs t = replicateM t $ read <$> getLine main :: IO () main = do t <- read <$> getLine unless (t < 1) $ (deleteDoubles <$> getUserInputs t) >>= mapM_ print

मैं एक समाधान भेज रहा हूं, और पहली निराशा यह है कि कार्यक्रम प्रयुक्त मेमोरी की सीमा से अधिक होने के कारण 193 परीक्षा पास नहीं करता है। मुख्य गलती पूरी सूची को स्मृति के रूप में पूरी तरह से पढ़ना है। हम इससे बचने की कोशिश करेंगे और पहले और दूसरे संस्करणों के एक निश्चित संकर को लागू करेंगे।

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

एक फ़ंक्शन जो प्रिंट करता है या उसके तर्कों के आधार पर परिणाम को प्रिंट नहीं करता है, जिसके बाद वह अपना दूसरा तर्क लौटाता है, जो IO मोनड में लिपटा है, काफी सरल है, आइए इसे चरण कहते हैं:

 step :: Int -> Int -> IO Int step fst snd = unless (fst == snd) (print snd) >> return snd

हमने पता लगाया कि क्या प्रिंट करना है या नहीं, यह पारित मूल्यों पर निर्भर करता है, लेकिन रीडिंग को व्यवस्थित कैसे करें? ऐसा करने के लिए, हम monadic convolution function foldM का उपयोग करते हैं :: (Foldable t, Monad m) => (b -> a -> mb) -> b -> ta -> mb , जो पढ़ने के कार्यों की सूची पर लागू होता है।
फ़ंक्शन के प्रकार से, हम ध्यान देते हैं कि प्रत्येक चरण में फ़ंक्शन के पिछले अनुप्रयोग के परिणाम का "अनपैकिंग" स्वयं फ़ोल्डर के हुड के तहत होता है। इस प्रकार, प्रत्येक चरण में हमें केवल वर्तमान सूची आइटम (वास्तव में, अगला नंबर पढ़ें) की बाइंड ऑपरेटर ( >> = ) का उपयोग करके और इसे पिछले चरण के साथ पास करने के लिए एक सामान्य गणना शुरू करने की आवश्यकता है। नतीजतन, हमें निम्नलिखित कार्यक्रम मिलते हैं

 step :: Int -> Int -> IO Int step fst snd = unless (fst == snd) (print snd) >> return snd initial :: IO Int initial = do a <- read <$> getLine print a return a getUserInputs t = replicate t $ read <$> getLine main :: IO () main = do t <- read <$> getLine unless (t < 1) $ do init <- initial foldM_ ((=<<) . step) init $ getUserInputs (t-1)

डी। ब्रैकेट अनुक्रम की पीढ़ी

एक पूर्णांक दिया गया n। यह लंबाई 2 ordered n के सभी सही ब्रैकेट अनुक्रमों को प्राप्त करने के लिए आवश्यक है, लेक्सिकोग्राफिक रूप से आदेशित किया गया है (देखें https://ru.wikipedia.org/wiki/Lexographic_order )।
टास्क में केवल कोष्ठक का उपयोग किया जाता है।
एक समाधान प्राप्त करना उचित है जो प्रतिक्रिया में सही ब्रैकेट अनुक्रमों की कुल संख्या के आनुपातिक समय में काम करता है, और एक ही समय में n के लिए आनुपातिक क्षमता का उपयोग करता है।

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

एक पुनरावर्ती कार्य को परिभाषित करें: ':: Int -> Int -> [[चार]] , जो दूसरे तर्क के रूप में लगाए जाने वाले कोष्ठक की संख्या को लेता है, और खुले पैरेंटेस की संख्या जो पहले तर्क के रूप में सेट होने के लिए निर्धारित है। पुनरावर्तन चरण के लिए, हमें दो सहायक कार्यों की आवश्यकता है: संभव - अगले चरण में रखी जाने वाली कोष्ठक की एक सूची देता है, और चरण - आवश्यक मापदंडों के साथ उत्पन्न फ़ंक्शन के लिए एक पुनरावर्ती कॉल करता है।

 import Control.Monad(mapM_) generate :: Int -> [String] generate = generate' 0 where generate' _ 0 = [[]] generate' an = [x:xs | x <- possible, xs <- step x] where step '(' = generate' (a + 1) (n - 1) step ')' = generate' (a - 1) (n - 1) possible | n == a = ")" | a == 0 = "(" | otherwise = "()" main :: IO () main = do n <- read <$> getLine let result = generate $ n * 2 mapM_ putStrLn result

हम समाधान भेजते हैं, और हम समझते हैं कि हमने उस प्रतिबंध को ध्यान में नहीं रखा था जो प्रोग्राम द्वारा उपयोग की जाने वाली मेमोरी की मात्रा पर लगाया गया था - उपयोग की गई मेमोरी की सीमा से अधिक होने के कारण समाधान 14 वीं परीक्षा पास नहीं करता है।

हम जनरेट फ़ंक्शन को संशोधित करते हैं ताकि सही ब्रैकेट अनुक्रमों की पूरी सूची का निर्माण करने के बजाय, यह उन्हें तुरंत स्क्रीन पर प्रदर्शित करे। ऐसा करने के लिए, हमें फ़ंक्शन में तीसरा तर्क जोड़ना होगा - वर्तमान चरण के लिए निर्मित अनुक्रम का एक टुकड़ा। मैं ध्यान देता हूं कि इस कार्यान्वयन में हम अनुक्रम को रिवर्स ऑर्डर में बनाएंगे - यह हमें सूची निर्माणकर्ता का उपयोग करने की अनुमति देगा ( :) इसके बजाय अधिक महंगा संघनन ऑपरेटर ( ++ )।

 import Control.Monad(mapM_) generate :: Int -> IO() generate = generate' "" 0 where generate' xs _ 0 = putStrLn $ reverse xs generate' xs an | n == a = step ')' | a == 0 = step '(' | otherwise = step '(' >> step ')' where step '(' = generate' ('(':xs) (a + 1) (n - 1) step ')' = generate' (')':xs) (a - 1) (n - 1) main :: IO () main = do n <- read <$> getLine generate $ n * 2

ई। अनाग्राम

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

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

आवश्यक सरणियों के निर्माण के लिए, हम फ़ंक्शन हिस्ट का उपयोग करते हैं :: (Ix a, Num b) => (a (a) -> [a] -> सरणी ab , जो तत्वों की हस्तांतरित सूची के अनुसार और जिस सीमा तक ये तत्व होते हैं, एक सरणी बनाते हैं। जो सूची से तत्वों की पुनरावृत्ति की संख्या को संग्रहीत करता है। यह फ़ंक्शन, हालांकि Data.Array मॉड्यूल में शामिल नहीं है, अक्सर एक और, पहले से ही लाइब्रेरी फ़ंक्शन, संचयन का उपयोग करने के उदाहरण के रूप में दिया जाता है। हम केवल इसके कार्यान्वयन की प्रतिलिपि बना सकते हैं और मुख्य लिख सकते हैं - एरे चार इंट के लिए समानता के लिए तुलना का लाभ पहले से ही परिभाषित है। मैं आपका ध्यान एक अच्छी सुविधा की ओर आकर्षित करता हूं - एक इंडेक्स के रूप में हम न केवल पूर्णांकों का उपयोग कर सकते हैं, बल्कि कक्षा Ix के किसी भी प्रतिनिधि का उपयोग कर सकते हैं। हमारे मामले में, चार इस भूमिका में एक प्राकृतिक भूमिका निभाता है।

 import Data.Array hist :: (Ix a, Num b) => (a,a) -> [a] -> Array ab hist bnds is = accumArray (+) 0 bnds [(i, 1) | i<-is, inRange bnds i] main = do arr1 <- hist ('a','z') <$> getLine arr2 <- hist ('a','z') <$> getLine if (arr1 == arr2) then print 1 else print 0

F. मर्ज k क्रमबद्ध सूची

दिए गए गैर-ऋणात्मक पूर्णांकों के k सरणियों को गैर-घटते क्रम में क्रमबद्ध किया गया है, जिनमें से प्रत्येक 100 से अधिक नहीं है। यह उनके विलय के परिणाम का निर्माण करने के लिए आवश्यक है: मूल सरणी के सभी तत्वों वाले गैर-घटते क्रम में क्रमबद्ध एक सरणी।
प्रत्येक सरणी की लंबाई 10 of k से अधिक नहीं है।
यदि हम मानते हैं कि इनपुट सरणियाँ लंबाई n की हैं, तो समय k लॉग (k) if n, के लिए समाधान कार्य करने का प्रयास करें।

दो क्रमबद्ध सूचियों को जोड़ना एक क्लासिक सूची कार्य है और हास्केल प्रोग्रामिंग पर कई पाठ्यक्रमों में शामिल है। उदाहरण के लिए, इसे निम्नानुसार हल किया जा सकता है।

 merge :: [Int] -> [Int] -> [Int] merge [] ys = ys merge xs [] = xs merge (x:xs) (y:ys) | x < y = x:merge xs (y:ys) | otherwise = y:merge (x:xs) ys

खैर, हम दो सूचियों को मर्ज कर सकते हैं। और सूचियों की सूची के साथ हमें क्या करना चाहिए? इस फ़ंक्शन के साथ इसे हल करें! इस प्रकार, हम सभी सूचियों को एक में जोड़ देंगे, और हमें केवल इसे प्रिंट करना होगा।

निर्णय

 import Control.Monad merge :: [Int] -> [Int] -> [Int] merge [] ys = ys merge xs [] = xs merge (x:xs) (y:ys) | x < y = x:merge xs (y:ys) | otherwise = y:merge (x:xs) ys mergeLists :: [[Int]] -> [Int] mergeLists = foldl merge [] getUserInputs :: Int -> IO [[Int]] getUserInputs t = replicateM t $ do n <- getLine return $ tail $ read <$> words n main :: IO () main = do k <- read <$> getLine lists <- getUserInputs k let res = mergeLists lists mapM_ (putStrLn . show) res

हालाँकि, इस समाधान में दो गंभीर समस्याएं हैं - कम्प्यूटेशनल जटिलता आवश्यक है - O (k (log (k) ) n) के बजाय O (k ^ 2 O n) की तुलना में अधिक है, साथ ही यह अतिरिक्त मेमोरी का उपयोग करता है। परिणामस्वरूप, यह समाधान उपयोग किए गए मेमोरी की सीमा से अधिक होने के कारण परीक्षण संख्या 17 में विफल रहता है - अनुमत 10Mb के बजाय 17.27Mb।

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

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

इस प्रकार, हमारे पास निम्नलिखित कार्यक्रम हैं:

निर्णय

 import qualified Data.Sequence as Seq import qualified Data.Set as Set import Control.Monad import Data.Foldable mergeLists :: Set.Set (Int, Int) -> Seq.Seq [Int] -> IO () mergeLists set seq | Set.null set = return () | otherwise = do let ((val, idx), set') = Set.deleteFindMin set print val if null (Seq.index seq idx) then mergeLists set' seq else mergeLists (Set.insert (head (Seq.index seq idx), idx) set') (Seq.adjust tail idx seq) getUserInputs :: Int -> IO [[Int]] getUserInputs t = replicateM t $ do n <- getLine return $ tail $ read <$> words n main :: IO () main = do t <- read <$> getLine lists <- getUserInputs t let init_seq = Seq.fromList (filter (not . null) lists) let init_heap = Set.fromList (zipWith (,) (toList (fmap head init_seq)) [0..]) mergeLists init_heap $ tail <$> init_seq

हम समाधान भेजते हैं और यह पता लगाते हैं कि भले ही कार्यक्रम में 17 मेमोरी पर 17.27Mb के बजाय कम मेमोरी (10.26Mb) की खपत शुरू हुई थी, फिर भी यह सीमा पूरी नहीं की। इसका कारण इस तथ्य में निहित है कि इस निर्णय के साथ, एक या दूसरे तरीके से, हमें पूरे इनपुट डेटा को मेमोरी में पढ़ना होगा। आइए इस समस्या के तीसरे समाधान की मदद से इससे बचने की कोशिश करें - गिनती के आधार पर छंटनी।

हमने पिछली विपर्यय समस्या को हल करते समय आने वाले पात्रों की संख्या की गिनती पहले ही कर ली है। इसके अलावा, इसे हल करने में, हम Data.Array का उपयोग करेंगे । सबसे पहले, हम addToArray :: Array Int Int -> [Int] -> Array Int Int फ़ंक्शन लागू करते हैं, जो सूची से मानों के अनुरूप होने वाले सूचकांकों पर मान बढ़ाकर मौजूदा एक के आधार पर एक सरणी बनाता है।

 addToArray :: Array Int Int -> [Int] -> Array Int Int addToArray acc elems = accum (+) acc [(i, 1) | i<-elems]

फिर, हम दोहराए गए हटाने की समस्या में हमारे पास जाने वाले दृष्टिकोण का उपयोग करेंगे - मोनडिक कनवल्शन का उपयोग करते हुए, क्रमिक रूप से AddToArray फ़ंक्शन को k स्रोत सरणियों में लागू करना। और ... हमें 17 वीं परीक्षा में 10.26Mb का समान परिणाम मिलता है। और फिर यह याद करने का समय है कि स्वीकृत कटौती क्रम के अनुसार फोल्ड (जिसका एनालॉग फोल्डम है ) पहले नेस्टेड अभिव्यक्तियों की पूरी श्रृंखला का विस्तार करेगा और उसके बाद ही उनकी सक्रिय गणना के लिए आगे बढ़ेगा। जैसा कि आप जानते हैं, इस तथ्य का मुकाबला करने के लिए, Data.List मॉड्यूल फोल्ड फ़ंक्शन को कार्यान्वित करता है, जो फ़ंक्शन seq :: a -> b -> b का उपयोग करता है, जो पहले तर्क को कमजोर सिर को सामान्य रूप देता है, अर्थात, इसे बाहरी हिस्से में कम कर देता है - फ़ंक्शन या कंस्ट्रक्टर का मान, और फिर दूसरा ( https://www.ibm.com/developerworks/ru/library/l-haskell4/index.html ) लौटाता है। हमारे पास फोल्डम फंक्शन को स्वतंत्र रूप से लागू करने के अलावा कोई विकल्प नहीं है।

 foldM' :: (Monad m) => (a -> b -> ma) -> a -> [b] -> ma foldM' _ z [] = return z foldM' fz (x:xs) = do z' <- fzx z' `seq` foldM' fz' xs

नतीजतन, 17 वीं परीक्षा में इस्तेमाल की गई स्मृति की मात्रा लगभग आधी हो गई और 5.64Mb की मात्रा! यद्यपि 17 वीं और 18 वीं परीक्षाओं को सफलतापूर्वक पारित किया गया था, इस कार्यान्वयन ने उसी कारण से 19 वीं परीक्षा पास नहीं की थी कि स्मृति सीमा पार हो गई थी - 10.25Mb।

ठीक है, आगे बढ़ें - हमने Data.Array.Unboxed की कोशिश नहीं की है। इस प्रकार के सरणियाँ इसमें उल्लेखनीय हैं, मानक के विपरीत, यह मानों को स्वयं संग्रहीत कर सकता है, न कि उनकी ओर संकेत करने के बजाय ( https://wiki.haskell.org/Arrays#Unboxed_arrays )। इसके कारण, ऐसे सरणियों में मेमोरी की जगह कम होती है और वे अधिक कुशल होते हैं। उनका उपयोग करने के लिए, हमें केवल आयात और फ़ंक्शन प्रकारों को बदलने की आवश्यकता है, क्योंकि Data.Array और Data.Array.Unboxed अपरिवर्तनीय IArray सरणियों के एक इंटरफ़ेस को लागू करते हैं।

हम एक समाधान भेज रहे हैं - मेमोरी की खपत 4.5 गुना घटकर 2.26 एमबी हो गई है, लेकिन यह समय सीमा पार नहीं हुई है - निष्पादन का समय 1.05 सेकंड था। इससे क्या जोड़ा जा सकता है? इस तथ्य को देखते हुए कि शेष परीक्षणों का निष्पादन समय समान रहता है, मुझे लगता है कि इसका कारण यह नहीं है कि बॉक्सिंग की तुलना में अनबॉक्स्ड सरणी धीमी निकली, बल्कि विशेष रूप से परीक्षण प्रणाली में। ऐसा लगता है कि जैसे ही एक प्रतिबंध का उल्लंघन किया जाता है, कार्य बाधित हो जाता है। हालाँकि, बहुत ही दुर्लभ मामलों में, यह कार्यान्वयन अभी भी ०.९ cases सेकंड के परिणाम के साथ १ ९वीं परीक्षा पास करता है, लेकिन समय सीमा से अधिक होने के कारण २० नंबर की परीक्षा में भी विफल रहता है।

उसके बाद मैंने संचित फ़ंक्शन के असुरक्षित एनालॉग का उपयोग करने की कोशिश की, जो सिद्धांत में तेज़ होना चाहिए, विभिन्न बफरिंग विधियाँ ( hSetBuffering :: हैंडल -> बफ़रकोड -> IO () फ़ंक्शन), परस्पर IOrray सरणियाँ, लेकिन इनमें से किसी भी तरीके से कोई परिणाम नहीं मिला। ।

मैं यह मानने के लिए इच्छुक नहीं हूं कि हास्केल के लिए सीमाएं बहुत कसकर तय की गई हैं, और मुझे उम्मीद है कि अभी भी एक समाधान है जो सभी परीक्षण पास करेगा। प्रोजेक्ट रिपॉजिटरी में, मैंने इस समस्या को हल करने के लिए (Array और IOArray के साथ) कोड के कई अलग-अलग संस्करण पोस्ट किए, शायद यह एक समाधान के लिए शुरुआती बिंदु होगा जो सभी परीक्षणों को पास करेगा।

निष्कर्ष

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

क्या कार्यात्मक दृष्टिकोण ऐसी समस्याओं को हल करने के लिए सुविधाजनक था? ईमानदारी से कहूं तो मुझे दोहरी धारणा है। एक ओर, अधिकांश समस्याओं के समाधान बहुत संक्षिप्त हो गए, और खुद हास्केल के अभिव्यंजक उपकरण, साथ ही साथ उनके समृद्ध मानक पुस्तकालय ने इसमें महत्वपूर्ण भूमिका निभाई। दूसरी ओर, कोई यह स्वीकार नहीं कर सकता है कि ज्यादातर मामलों में खपत संसाधनों का प्रबंधन एक निश्चित समस्या हो सकती है, जो दिए गए प्रतिबंधों में समस्या को हल करने की अनुमति नहीं देगा।

हम एक कार्यात्मक शैली में यैंडेक्स.इंटरव्यू कार्यों को हल करते हैं