पिछली गर्मियों में मैंने इसमें भाग लिया था संहिता की गूगल समर - Google की ओर से छात्रों के लिए एक कार्यक्रम। हर साल, आयोजक कई ओपन सोर्स परियोजनाओं का चयन करते हैं, जिनमें ऐसे प्रसिद्ध संगठन भी शामिल हैं Boost.org и लिनक्स फाउंडेशन. Google इन परियोजनाओं पर काम करने के लिए दुनिया भर से छात्रों को आमंत्रित करता है। 

Google Summer of Code 2019 में एक प्रतिभागी के रूप में, मैंने लाइब्रेरी के भीतर एक प्रोजेक्ट किया शैवाल संगठन के साथ हास्केल.ओआरजी, जो हास्केल भाषा विकसित कर रहा है - सबसे प्रसिद्ध कार्यात्मक प्रोग्रामिंग भाषाओं में से एक। शैवाल एक पुस्तकालय है जो प्रतिनिधित्व करता है सुरक्षित टाइप करें हास्केल में ग्राफ़ के लिए प्रतिनिधित्व। इसका उपयोग, उदाहरण के लिए, में किया जाता है अर्थ - एक जीथब लाइब्रेरी जो कोड के आधार पर सिमेंटिक ट्री, कॉल और निर्भरता ग्राफ़ बनाती है और उनकी तुलना कर सकती है। मेरा प्रोजेक्ट उस प्रतिनिधित्व के लिए द्विदलीय ग्राफ़ और एल्गोरिदम के लिए एक प्रकार-सुरक्षित प्रतिनिधित्व जोड़ना था। 

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

मेरे बारे में

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

एल्गोरिथम के कार्यान्वयन के बारे में

प्रस्तावना

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

प्रश्नगत कोड के साथ पुल अनुरोध पाया जा सकता है यहां.

आप मेरे काम के परिणामों के बारे में पढ़ सकते हैं (अंग्रेजी में) यहां.

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

द्विपक्षीयता के लिए ग्राफ़ की जाँच करना 

द्विदलीयता के लिए ग्राफ़ की जाँच करने के लिए एक एल्गोरिदम आमतौर पर सबसे सरल ग्राफ़ एल्गोरिदम में से एक के रूप में एल्गोरिदम पर एक पाठ्यक्रम में दिया जाता है। उनका विचार सीधा है: पहले हम किसी तरह बाएं या दाएं हिस्से में शीर्ष डालते हैं, और जब एक विरोधाभासी किनारा मिलता है, तो हम दावा करते हैं कि ग्राफ द्विदलीय नहीं है।

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

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

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

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

गणना की शुद्धता

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

मोनैड्स गणनाओं को दर्शाने का एक तरीका है प्रभाव हास्केल में. यह बताना कि वे कैसे काम करते हैं, इस पोस्ट के दायरे से बाहर है। एक अच्छा और स्पष्ट विवरण अंग्रेजी में पढ़ा जा सकता है यहां.

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

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

• या तो ea एक गणना है जो प्रकार a का मान लौटाती है या प्रकार e का अपवाद फेंकती है। इस सन्यासी का व्यवहार अनिवार्य भाषाओं में अपवाद प्रबंधन के समान है: त्रुटियों को पकड़ा या आगे बढ़ाया जा सकता है। मुख्य अंतर यह है कि मोनाड को हास्केल में मानक पुस्तकालय में पूरी तरह से तार्किक रूप से कार्यान्वित किया जाता है, जबकि अनिवार्य भाषाएं आमतौर पर ऑपरेटिंग सिस्टम तंत्र का उपयोग करती हैं।
• राज्य एसए एक गणना है जो प्रकार ए का मान लौटाती है और प्रकार एस की परिवर्तनीय स्थिति तक पहुंच रखती है।
• शायद एक। हो सकता है मोनैड एक गणना व्यक्त करता है जिसे किसी भी समय कुछ भी नहीं लौटाकर बाधित किया जा सकता है। हालाँकि, हम हो सकता है प्रकार के लिए मोनाडप्लस वर्ग के कार्यान्वयन के बारे में बात करेंगे, जो विपरीत प्रभाव व्यक्त करता है: यह एक गणना है जिसे किसी भी समय एक विशिष्ट मान लौटाकर बाधित किया जा सकता है।

एल्गोरिथम का कार्यान्वयन

हमारे पास दो डेटा प्रकार हैं, ग्राफ़ ए और बिग्राफ एब, जिनमें से पहला प्रकार ए के मानों के साथ लेबल किए गए शीर्षों के साथ ग्राफ़ का प्रतिनिधित्व करता है, और दूसरा प्रकार ए और दाएं के मानों के साथ लेबल किए गए बाईं ओर के शीर्षों के साथ द्विदलीय ग्राफ़ का प्रतिनिधित्व करता है। -साइड वर्टिस को टाइप बी के मानों के साथ लेबल किया गया है।

ये शैवाल पुस्तकालय के प्रकार नहीं हैं। शैवाल के पास अप्रत्यक्ष द्विदलीय ग्राफ़ के लिए कोई प्रतिनिधित्व नहीं है। मैंने स्पष्टता के लिए इस तरह के प्रकार बनाए।

हमें निम्नलिखित हस्ताक्षरों वाले सहायक कार्यों की भी आवश्यकता होगी:

-- Список соседей данной вершины.
neighbours :: Ord a => a -> Graph a -> [a]

-- Построить двудольный граф по графу и функции, для каждой вершины
-- выдающей её долю и пометку в новой доле, игнорируя конфликтные рёбра.
toBipartiteWith :: (Ord a, Ord b, Ord c) => (a -> Either b c)
                                         -> Graph a
                                         -> Bigraph b c

-- Список вершин в графе
vertexList :: Ord a => Graph a -> [a]
Сигнатура функции, которую мы будем писать, выглядит так:

type OddCycle a = [a]
detectParts :: Ord a => Graph a -> Either (OddCycle a) (Bigraph a a)

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

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

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

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

मैंने इतना जटिल प्रकार क्यों चुना? दो कारण। सबसे पहले, कार्यान्वयन अनिवार्यता के समान ही होता है। दूसरा, हमें विषम लूप को पुनर्स्थापित करने के लिए रिकर्सन से वापस लौटते समय संघर्ष के मामले में रिटर्न वैल्यू में हेरफेर करने की आवश्यकता है, जो कि शायद मोनाड में करना बहुत आसान है।

इस प्रकार हमें यह कार्यान्वयन प्राप्त होता है।

{-# LANGUAGE ExplicitForAll #-}
{-# LANGUAGE ScopedTypeVariables #-}

data Part = LeftPart | RightPart

otherPart :: Part -> Part
otherPart LeftPart  = RightPart
otherPart RightPart = LeftPart

type PartMap a = Map.Map a Part
type OddCycle a = [a]

toEither :: Ord a => PartMap a -> a -> Either a a
toEither m v = case fromJust (v `Map.lookup` m) of
                    LeftPart  -> Left  v
                    RightPart -> Right v

type PartMonad a = MaybeT (State (PartMap a)) [a]

detectParts :: forall a. Ord a => Graph a -> Either (OddCycle a) (Bigraph a a)
detectParts g = case runState (runMaybeT dfs) Map.empty of
                     (Just c, _)  -> Left  $ oddCycle c
                     (Nothing, m) -> Right $ toBipartiteWith (toEither m) g
    where
        inVertex :: Part -> a -> PartMonad a
        inVertex p v = ((:) v) <$> do modify $ Map.insert v p
                                      let q = otherPart p
                                      msum [ onEdge q u | u <- neigbours v g ]

        {-# INLINE onEdge #-}
        onEdge :: Part -> a -> PartMonad a
        onEdge p v = do m <- get
                        case v `Map.lookup` m of
                             Nothing -> inVertex p v
                             Just q  -> do guard (q /= p)
                                           return [v]

        processVertex :: a -> PartMonad a
        processVertex v = do m <- get
                             guard (v `Map.notMember` m)
                             inVertex LeftPart v

        dfs :: PartMonad a
        dfs = msum [ processVertex v | v <- vertexList g ]

        oddCycle :: [a] -> [a]
        oddCycle c = tail (dropWhile ((/=) last c) c)

व्हेयर ब्लॉक एल्गोरिथम का मूल है। मैं समझाने की कोशिश करूंगा कि इसके अंदर क्या हो रहा है.

• इनवर्टेक्स डेप्थ-फर्स्ट सर्च का हिस्सा है जहां हम पहली बार वर्टेक्स पर जाते हैं। यहां हम वर्टेक्स को एक शेयर नंबर निर्दिष्ट करते हैं और सभी पड़ोसियों पर ऑनएज चलाते हैं। यह वह जगह भी है जहां हम कॉल स्टैक को पुनर्स्थापित करते हैं: यदि एमसुम ने कोई मान लौटाया है, तो हम वहां वर्टेक्स वी दबाते हैं।
• ऑनएज वह हिस्सा है जहां हम किनारे पर जाते हैं। इसे प्रत्येक किनारे के लिए दो बार कहा जाता है। यहां हम जांचते हैं कि क्या दूसरी तरफ के शिखर का दौरा किया गया है, और यदि नहीं तो वहां का दौरा करेंगे। यदि दौरा किया जाता है, तो हम जाँचते हैं कि क्या किनारा परस्पर विरोधी है। यदि ऐसा है, तो हम मान लौटाते हैं - रिकर्सन स्टैक के बिल्कुल शीर्ष पर, जहां वापसी पर अन्य सभी कोने रखे जाएंगे।
• प्रोसेसवर्टेक्स प्रत्येक शीर्ष के लिए जांच करता है कि क्या उस पर दौरा किया गया है और यदि नहीं तो उस पर इनवर्टेक्स चलता है।
• dfs सभी शीर्षों पर प्रोसेसवर्टेक्स चलाता है।

बस इतना ही।

इनलाइन शब्द का इतिहास

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

जीएचसी कोर आउटपुट को पढ़ने में एक सप्ताह बिताने के बाद, मैं स्पष्ट इनलाइन की एक पंक्ति के साथ समस्या को ठीक करने में सक्षम था। जीएचसी 8.4.4 और जीएचसी 8.6.5 के बीच किसी बिंदु पर ऑप्टिमाइज़र ने अपने आप ऐसा करना बंद कर दिया।

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

आगे क्या हुआ?

फिर मैंने हॉपक्रॉफ्ट-कार्प एल्गोरिथ्म को अन्य भिक्षुओं के साथ लागू किया, और वह कार्यक्रम का अंत था।

Google समर ऑफ कोड के लिए धन्यवाद, मुझे कार्यात्मक प्रोग्रामिंग में व्यावहारिक अनुभव प्राप्त हुआ, जिससे न केवल मुझे अगली गर्मियों में जेन स्ट्रीट में इंटर्नशिप प्राप्त करने में मदद मिली (मुझे यकीन नहीं है कि यह जगह हैबर के जानकार दर्शकों के बीच भी कितनी प्रसिद्ध है, लेकिन यह एक है कुछ में से जहां आप गर्मियों में कार्यात्मक प्रोग्रामिंग में संलग्न हो सकते हैं), लेकिन मुझे इस प्रतिमान को व्यवहार में लागू करने की अद्भुत दुनिया से भी परिचित कराया, जो पारंपरिक भाषाओं में मेरे अनुभव से काफी अलग है।

स्रोत: www.habr.com