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

Google समर अफ कोड 2019 मा एक सहभागीको रूपमा, मैले पुस्तकालय भित्र एउटा परियोजना गरें एल्गा संगठन संग Haskell.org, जसले हास्केल भाषाको विकास गरिरहेको छ - सबैभन्दा प्रसिद्ध कार्यात्मक प्रोग्रामिङ भाषाहरू मध्ये एक। Alga प्रतिनिधित्व गर्ने पुस्तकालय हो सुरक्षित टाइप गर्नुहोस् Haskell मा ग्राफ को लागी प्रतिनिधित्व। यो प्रयोग गरिन्छ, उदाहरणका लागि, मा अर्थपूर्ण - एक Github पुस्तकालय जसले कोडको आधारमा सिमेन्टिक रूखहरू, कल र निर्भरता ग्राफहरू बनाउँछ र तिनीहरूलाई तुलना गर्न सक्छ। मेरो परियोजना द्विपक्षीय ग्राफ र त्यस प्रतिनिधित्वको लागि एल्गोरिदमहरूको लागि एक प्रकार-सुरक्षित प्रतिनिधित्व थप्न थियो। 

यस पोष्टमा म हस्केलमा द्विपक्षीयताको लागि ग्राफ जाँच गर्नको लागि एल्गोरिदमको कार्यान्वयनको बारेमा कुरा गर्नेछु। यद्यपि एल्गोरिथ्म सबैभन्दा आधारभूत मध्ये एक हो, यसलाई कार्यात्मक शैलीमा सुन्दर ढंगले कार्यान्वयन गर्नले मलाई धेरै पुनरावृत्तिहरू लियो र धेरै कामको आवश्यकता थियो। नतिजाको रूपमा, म मोनाड ट्रान्सफर्मरको साथ कार्यान्वयनमा बसे। 

मेरो बारेमा

मेरो नाम Vasily Alferov हो, म सेन्ट पीटर्सबर्ग HSE मा चौथो वर्षको विद्यार्थी हुँ। पहिले ब्लगमा लेखेको थिएँ प्यारामिटराइज्ड एल्गोरिदमको बारेमा मेरो परियोजनाको बारेमा и ZuriHac को यात्रा को बारे मा। अहिले म इन्टर्नशिपमा छु बर्गन विश्वविद्यालय नर्वे मा, जहाँ म समस्या को दृष्टिकोण मा काम गर्दैछु सूची रङ। मेरो रुचिहरूमा प्यारामिटराइज्ड एल्गोरिदम र कार्यात्मक प्रोग्रामिङ समावेश छ।

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

Foreword

कार्यक्रममा सहभागी विद्यार्थीहरूलाई ब्लग गर्न दृढतापूर्वक प्रोत्साहित गरिन्छ। तिनीहरूले मलाई ब्लगको लागि प्लेटफर्म प्रदान गरे Haskell को गर्मी। यो लेख अनुवाद हो लेख, मैले त्यहाँ जुलाईमा अंग्रेजीमा लेखेको, छोटो प्रस्तावनाको साथ। 

प्रश्नमा कोडको साथ पुल अनुरोध फेला पार्न सकिन्छ यहाँ.

तपाईले मेरो कामको नतिजाहरू पढ्न सक्नुहुन्छ (अंग्रेजीमा) यहाँ.

यो पोष्टले पाठकलाई कार्यात्मक प्रोग्रामिङमा आधारभूत अवधारणाहरूसँग परिचित छ भनी मान्दछ, यद्यपि म समय आउँदा प्रयोग गरिएका सबै सर्तहरू सम्झने प्रयास गर्नेछु।

द्विपक्षीयताका लागि ग्राफहरू जाँच गर्दै 

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

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

यदि उही विभाजनमा परेका ठाडोहरू बीचको किनारा छ भने, ग्राफमा एक अजीब चक्र फेला पार्न गाह्रो छैन, जुन द्विपक्षीय ग्राफमा व्यापक रूपमा ज्ञात (र स्पष्ट रूपमा) असम्भव छ। अन्यथा, हामीसँग सही विभाजन छ, जसको अर्थ ग्राफ द्विपक्षीय छ।

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

यसरी, हामी निम्न योजनामा ​​आएका छौं। हामी गहिराई-पहिलो खोज प्रयोग गरेर ग्राफको ठाडो पार गर्छौं र तिनीहरूलाई सेयरहरू असाइन गर्छौं, हामी किनारासँगै अघि बढ्दा सेयरको संख्या परिवर्तन गर्छौं। यदि हामीले पहिले नै सेयर तोकिएको भर्टेक्समा सेयर असाइन गर्ने प्रयास गर्छौं भने, हामी सुरक्षित रूपमा भन्न सक्छौं कि ग्राफ द्विपक्षीय छैन। सबै ठाडोहरूलाई साझा तोकिएको क्षण र हामीले सबै किनारहरू हेरेका छौं, हामीसँग राम्रो विभाजन छ।

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

हास्केलमा हामी मान्दछौं कि सबै गणनाहरू छन् सफा। यद्यपि, यदि यो साँच्चै मामला हो भने, हामीसँग स्क्रिनमा केहि छाप्ने कुनै तरिका हुनेछैन। बिल्कुलै, सफा गणना यति अल्छी छ कि त्यहाँ एक छैन सफा केहि गणना गर्न कारणहरू। कार्यक्रममा हुने सबै गणनाहरू कुनै न कुनै रूपमा बाध्य छन् "अशुद्ध" मोनाड IO।

मोनाडहरू गणनाको प्रतिनिधित्व गर्ने तरिका हो प्रभावहरू Haskell मा। तिनीहरूले कसरी काम गर्छन् भन्ने व्याख्या यस पोस्टको दायराभन्दा बाहिर छ। अंग्रेजीमा राम्रो र स्पष्ट विवरण पढ्न सकिन्छ यहाँ.

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

त्यहाँ धेरै प्रभावहरू छन् र प्रत्येकको आफ्नै मोनाड छ। यो एक धेरै बलियो र सुन्दर सिद्धान्त हो: सबै मोनाडहरूले एउटै इन्टरफेस लागू गर्दछ। हामी निम्न तीन मोनाडहरूको बारेमा कुरा गर्नेछौं:

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

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

हामीसँग दुईवटा डेटा प्रकारहरू छन्, ग्राफ ए र बिग्राफ ab, जसमध्ये पहिलोले टाइप a को मानहरूसँग लेबल गरिएका ठाडोहरूसहित ग्राफहरू प्रतिनिधित्व गर्दछ, र दोस्रोले टाइप a र दायाँको मानहरूसँग लेबल गरिएको बायाँ-साइड ठाडोहरूसहित द्विपक्षीय ग्राफहरू प्रतिनिधित्व गर्दछ। - प्रकार b को मानहरूसँग लेबल गरिएको छेउछेउहरू।

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

हामीलाई निम्न हस्ताक्षरहरूको साथ सहायक कार्यहरू पनि चाहिन्छ:

-- Список соседей данной вершины.
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)

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

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

मेरो पहिलो विचार Either monad को प्रयोग गर्नु थियो, जसले हामीलाई चाहिने प्रभावहरू लागू गर्दछ। मैले लेखेको पहिलो कार्यान्वयन यो विकल्पको धेरै नजिक थियो। वास्तवमा, मसँग एक बिन्दुमा पाँचवटा फरक कार्यान्वयनहरू थिए र अन्ततः अर्कोमा बसे।

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

मैले किन यस्तो जटिल प्रकार रोजें? दुई कारण। पहिलो, कार्यान्वयन अनिवार्य रूपमा धेरै मिल्दोजुल्दो छ। दोस्रो, विचित्र लूप पुनर्स्थापना गर्न पुनरावृत्तिबाट फिर्ता गर्दा द्वन्द्वको अवस्थामा हामीले फिर्ता मूल्यलाई हेरफेर गर्न आवश्यक छ, जुन शायद मोनाडमा गर्न धेरै सजिलो छ।

यसरी हामी यो कार्यान्वयन प्राप्त गर्छौं।

{-# 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)

जहाँ ब्लक एल्गोरिदम को मूल हो। म भित्र के भइरहेको छ भनेर व्याख्या गर्ने प्रयास गर्नेछु।

• inVertex depth-first search को भाग हो जहाँ हामी पहिलो पटक भेर्टेक्समा जान्छौं। यहाँ हामी भेर्टेक्समा सेयर नम्बर तोक्छौं र सबै छिमेकीहरूमा onEdge चलाउँछौं। यो पनि हो जहाँ हामी कल स्ट्याक पुनर्स्थापित गर्छौं: यदि msum ले मान फर्काउँछ भने, हामी vertex v त्यहाँ पुश गर्छौं।
• onEdge त्यो भाग हो जहाँ हामी किनारामा जान्छौं। यसलाई प्रत्येक किनाराको लागि दुई पटक भनिन्छ। यहाँ हामी जाँच गर्छौं कि अर्को छेउको भेर्टेक्स भ्रमण गरिएको छ, र यदि छैन भने यसलाई भ्रमण गर्नुहोस्। यदि भ्रमण गरिएको छ भने, हामी किनारा विरोधाभासी छ कि छैन जाँच गर्छौं। यदि यो हो भने, हामी मान फिर्ता गर्छौं - पुनरावृत्ति स्ट्याकको एकदम शीर्ष, जहाँ अन्य सबै ठाडोहरू फिर्तामा राखिनेछ।
• processVertex ले प्रत्येक भेर्टेक्सको लागि जाँच गर्दछ कि यो भ्रमण गरिएको छ र यदि छैन भने यसमा भर्टेक्स चल्छ।
• dfs सबै ठाडोहरूमा processVertex चलाउँछ।

यति नै।

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

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

GHC कोर आउटपुट पढेर एक हप्ता बिताएपछि, मैले स्पष्ट INLINE को एक लाइनको साथ समस्या समाधान गर्न सक्षम भएँ। GHC 8.4.4 र GHC 8.6.5 को बीचमा केहि बिन्दुमा अनुकूलकले यो आफैं गर्न बन्द गर्यो।

मैले हस्केल प्रोग्रामिङमा यस्तो फोहोरको सामना गर्ने आशा गरेन। यद्यपि, आज पनि, अप्टिमाइजरहरूले कहिलेकाहीं गल्ती गर्छन्, र तिनीहरूलाई संकेत दिनु हाम्रो काम हो। उदाहरणका लागि, यहाँ हामीलाई थाहा छ कि प्रकार्य इनलाइन हुनुपर्छ किनभने यो अनिवार्य संस्करणमा इनलाइन गरिएको छ, र यो कम्पाइलरलाई संकेत दिने कारण हो।

अनि के भयो?

त्यसपछि मैले अन्य मोनाडहरूसँग Hopcroft-Karp एल्गोरिथ्म लागू गरें, र त्यो कार्यक्रमको अन्त्य थियो।

गुगल समर अफ कोडको लागि धन्यवाद, मैले कार्यात्मक प्रोग्रामिङमा व्यावहारिक अनुभव प्राप्त गरें, जसले मलाई अर्को गर्मीमा जेन स्ट्रिटमा इन्टर्नशिप प्राप्त गर्न मद्दत गर्‍यो (मलाई थाहा छैन कि यो ठाउँ हाब्रका जानकार दर्शकहरूमाझ पनि कत्तिको परिचित छ, तर यो एउटा हो। कार्यात्मक प्रोग्रामिङमा संलग्न हुनको लागि तपाईं समर गर्न सक्नुहुन्छ भन्ने केही मध्ये), तर यसले मलाई परम्परागत भाषाहरूमा मेरो अनुभव भन्दा उल्लेखनीय रूपमा फरक व्यवहारमा यो प्रतिमान लागू गर्ने अद्भुत संसारमा परिचय गराएको छ।

स्रोत: www.habr.com