ባለፈው ክረምት ተሳትፌ ነበር። ኮድ የ Google በጋ - ከ Google ለተማሪዎች የሚሆን ፕሮግራም. በየዓመቱ አዘጋጆቹ ብዙ የክፍት ምንጭ ፕሮጀክቶችን ይመርጣሉ, ከእንደዚህ ያሉ ታዋቂ ድርጅቶችን ጨምሮ Boost.org и ሊኑክስ ፋውንዴሽን. Google በእነዚህ ፕሮጀክቶች ላይ እንዲሰሩ ከመላው አለም የመጡ ተማሪዎችን ይጋብዛል። 

በGoogle Summer of Code 2019 ተሳታፊ እንደመሆኔ፣ በቤተ-መጽሐፍት ውስጥ ፕሮጀክት ሰርቻለሁ አልጋ ከድርጅቱ ጋር Haskell.orgየ Haskell ቋንቋን እያዳበረ ነው - በጣም ታዋቂ ከሆኑ ተግባራዊ የፕሮግራም ቋንቋዎች አንዱ። አልጋ የሚወክል ቤተ መጻሕፍት ነው። ደህንነቱን ይተይቡ በ Haskell ውስጥ ለግራፎች ውክልና። ጥቅም ላይ ይውላል, ለምሳሌ, በ ሥነ-ጽሑፍ - የትርጓሜ ዛፎችን፣ የጥሪ እና የጥገኝነት ግራፎችን በኮድ ላይ በመመስረት የሚገነባ እና እነሱን ማወዳደር የሚችል የ Github ቤተ-መጽሐፍት። የእኔ ፕሮጀክት ለሁለቱም ሁለት ግራፎች እና ስልተ ቀመሮች አይነት-አስተማማኝ ውክልና ማከል ነበር። 

በዚህ ልኡክ ጽሁፍ በሃስኬል ውስጥ ለሁለትዮሽነት ግራፍ ለመፈተሽ ስለ አልጎሪዝም አተገባበር አወራለሁ። ምንም እንኳን አልጎሪዝም በጣም መሠረታዊ ከሆኑት ውስጥ አንዱ ቢሆንም፣ በሚያምር ሁኔታ በተግባራዊ ዘይቤ መተግበሩ ብዙ ድግግሞሾችን ወስዶብኛል እና ብዙ ስራ አስፈልጎኛል። በዚህ ምክንያት ከሞናድ ትራንስፎርመሮች ጋር ወደ ትግበራ ገባሁ። 

ስለ እኔ

ስሜ ቫሲሊ አልፌሮቭ እባላለሁ፣ በሴንት ፒተርስበርግ ኤችኤስኢ የአራተኛ ዓመት ተማሪ ነኝ። ቀደም ብዬ በጻፍኩት ብሎግ ውስጥ ስለ ፐሮጀክቴ ስለ ፓራሜትሪ ስልተ ቀመሮች и ስለ ZuriHac ጉዞ. አሁን እኔ በ internship ላይ ነኝ የበርገን ዩኒቨርሲቲ በኖርዌይ ለችግሩ አቀራረቦችን እየሰራሁ ነው። የዝርዝር ማቅለም. የእኔ ፍላጎቶች የተካኑ ስልተ ቀመሮችን እና ተግባራዊ ፕሮግራሞችን ያካትታሉ።

ስለ አልጎሪዝም አተገባበር

መቅድም

በፕሮግራሙ ውስጥ የሚሳተፉ ተማሪዎች በብሎግ እንዲያደርጉ በጥብቅ ይበረታታሉ። ለብሎግ መድረክ አዘጋጅተውልኛል። የ Haskell ክረምት. ይህ ጽሑፍ ትርጉም ነው። መጣጥፎች፣ እኔ እዚያ በሐምሌ ወር በእንግሊዝኛ የተጻፈ ፣ ከትንሽ መቅድም ጋር። 

የመጎተት ጥያቄ በጥያቄ ውስጥ ካለው ኮድ ጋር ሊገኝ ይችላል። እዚህ.

ስለ ሥራዬ ውጤት (በእንግሊዝኛ) ማንበብ ትችላላችሁ እዚህ.

ይህ ጽሑፍ አንባቢውን በተግባራዊ ፕሮግራሚንግ ውስጥ ከመሠረታዊ ፅንሰ-ሀሳቦች ጋር ለመተዋወቅ የታሰበ ነው ፣ ምንም እንኳን ጊዜው ሲደርስ ጥቅም ላይ የዋሉትን ሁሉንም ቃላት ለማስታወስ እሞክራለሁ ።

ለሁለት ፓርቲነት ግራፎችን መፈተሽ 

ለሁለትዮሽነት ግራፍ ለመፈተሽ ስልተ ቀመር ብዙውን ጊዜ በአልጎሪዝም ላይ በሚሰጥ ኮርስ ውስጥ በጣም ቀላሉ የግራፍ ስልተ ቀመሮች አንዱ ነው። ሃሳቡ ቀጥተኛ ነው፡ መጀመሪያ እንደምንም ወደ ግራ ወይም ቀኝ ድርሻ ላይ ጫፎችን እናስቀምጣለን እና የሚጋጭ ጠርዝ ሲገኝ ግራፉ የሁለትዮሽ እንዳልሆነ እናረጋግጣለን።

ትንሽ ተጨማሪ ዝርዝር፡ በመጀመሪያ በግራ ድርሻው ላይ የተወሰነ ወርድ እናስቀምጣለን። በግልጽ ለማየት እንደሚቻለው, ሁሉም የዚህ ጫፍ ጎረቤቶች በትክክለኛው ሎብ ውስጥ መዋሸት አለባቸው. በተጨማሪም, ሁሉም የዚህ ጫፍ ጎረቤቶች ጎረቤቶች በግራ ሎብ ውስጥ መተኛት አለባቸው, ወዘተ. እኛ ጎረቤቶች ያልመደብንበት የጀመርንበት የ vertex ክፍል የተገናኘ አካል ላይ አሁንም ጫፎች እስካሉ ድረስ አክሲዮኖችን ወደ ጫፎች መመደብን እንቀጥላለን። ከዚያ ይህን እርምጃ ለሁሉም የተገናኙ አካላት እንደግመዋለን.

በተመሳሳዩ ክፍልፍል ውስጥ በሚወድቁ ጫፎች መካከል ጠርዝ ካለ በግራፍ ውስጥ ያልተለመደ ዑደት ማግኘት አስቸጋሪ አይደለም ፣ ይህም በሰፊው የሚታወቅ (እና በግልፅ) በሁለትዮሽ ግራፍ ውስጥ የማይቻል ነው። አለበለዚያ, እኛ ትክክለኛ ክፍልፍል አለን, ይህም ማለት ግራፉ የሁለትዮሽ ነው.

በተለምዶ ይህ ስልተ ቀመር በመጠቀም ይተገበራል ስፋት የመጀመሪያ ፍለጋ ወይም ጥልቀት የመጀመሪያ ፍለጋ. በአስፈላጊ ቋንቋዎች ጥልቀት-የመጀመሪያ ፍለጋ ብዙውን ጊዜ ጥቅም ላይ የሚውለው ትንሽ ቀላል ስለሆነ እና ተጨማሪ የውሂብ አወቃቀሮችን ስለማያስፈልገው ነው። እኔ ደግሞ ጥልቅ-የመጀመሪያ ፍለጋን የመረጥኩት ባህላዊ ስለሆነ ነው።

ስለዚህ, ወደሚከተለው እቅድ ደርሰናል. ጥልቀት-የመጀመሪያ ፍለጋን በመጠቀም የግራፉን ጫፎች እናቋርጣለን እና አክሲዮኖችን እንመድባቸዋለን, በጠርዙ ላይ ስንንቀሳቀስ የቁጥሩን ቁጥር እንለውጣለን. ቀድሞውንም ድርሻ ያለው ድርሻ ላለው ወርድ ለመመደብ ከሞከርን ግራፉ የሁለትዮሽ አይደለም ማለት እንችላለን። ሁሉም ጫፎች አንድ ድርሻ በተመደቡበት ጊዜ እና ሁሉንም ጫፎች በተመለከትንበት ጊዜ ጥሩ ክፍፍል አለን።

የስሌቶች ንፅህና

በ Haskell ውስጥ ሁሉም ስሌቶች እንደሆኑ እንገምታለን። ንፁህ ። ነገር ግን፣ ይህ እውነት ከሆነ፣ ምንም ነገር በስክሪኑ ላይ ለማተም ምንም አይነት መንገድ አይኖረንም ነበር። ፈጽሞ, ንፁህ ስሌቶች በጣም ሰነፍ ስለሆኑ አንድም የለም። ንፁህ አንድ ነገር ለማስላት ምክንያቶች. በፕሮግራሙ ውስጥ የሚከሰቱ ሁሉም ስሌቶች በሆነ መንገድ እንዲገቡ ይገደዳሉ "ርኩስ" ሞናድ አይ.ኦ.

ሞናዶች ስሌቶችን የሚወክሉበት መንገድ ናቸው። ተፅዕኖዎች በ Haskell ውስጥ. እንዴት እንደሚሠሩ ማብራራት ከዚህ ጽሑፍ ወሰን በላይ ነው። ጥሩ እና ግልጽ መግለጫ በእንግሊዝኛ ሊነበብ ይችላል እዚህ.

እዚህ ላይ እንደ አይኦ ያሉ አንዳንድ ሞናዶች በአቀነባባሪ አስማት ሲተገበሩ ሌሎች ሁሉም ማለት ይቻላል በሶፍትዌር ውስጥ እንደሚተገበሩ እና በውስጣቸው ያሉት ሁሉም ስሌቶች ንጹህ መሆናቸውን መግለፅ እፈልጋለሁ።

ብዙ ተፅዕኖዎች አሉ እና እያንዳንዱ የራሱ ሞንዳ አለው. ይህ በጣም ጠንካራ እና የሚያምር ፅንሰ-ሀሳብ ነው-ሁሉም ሞናዶች አንድ አይነት በይነገጽ ይተገብራሉ። ስለሚከተሉት ሶስት ሞኖዶች እንነጋገራለን-

• ወይ ኢ የአይነት እሴትን የሚመልስ ወይም ከአይነት ኢ በስተቀር የሚጥል ስሌት ነው። የዚህ ሞናድ ባህሪ በአስገዳጅ ቋንቋዎች ልዩ አያያዝ ጋር በጣም ተመሳሳይ ነው፡ ስህተቶች ሊያዙ ወይም ሊተላለፉ ይችላሉ። ዋናው ልዩነቱ ሞንዳው ሙሉ በሙሉ በሐክሄል ውስጥ ባለው መደበኛ ቤተ-መጽሐፍት ውስጥ ሙሉ በሙሉ ምክንያታዊ በሆነ መንገድ መተግበሩ ነው ፣ አስፈላጊ ቋንቋዎች ግን ብዙውን ጊዜ የስርዓተ ክወና ዘዴዎችን ይጠቀማሉ።
• State sa የአይነት ሀ እሴትን የሚመልስ እና የሚለዋወጠውን አይነት s የሚይዝ ስሌት ነው።
• ምናልባት ሀ. The Maybe monad ምንም ነገር በመመለስ በማንኛውም ጊዜ ሊቋረጥ የሚችል ስሌት ይገልጻል። ሆኖም ግን, ስለ MonadPlus ክፍል ለሜይቤ ዓይነት አተገባበር እንነጋገራለን, እሱም ተቃራኒውን ውጤት የሚገልጽ ነው: አንድ የተወሰነ እሴት በመመለስ በማንኛውም ጊዜ ሊቋረጥ የሚችል ስሌት ነው.

የአልጎሪዝም አተገባበር

ሁለት የዳታ ዓይነቶች አሉን ፣ግራፍ ሀ እና ቢግራፍ ab ፣የመጀመሪያው በአይነት ሀ ላይ የተለጠፈ ጫፎች ያላቸው ግራፎችን ይወክላል ፣ሁለተኛው ደግሞ የሁለትዮሽ ግራፎችን የሚወክለው የግራ ጎን ቁመቶች አይነት ሀ እና ቀኝ ናቸው። - የጎን ጫፎች በዓይነት እሴቶች ምልክት የተደረገባቸው ለ.

እነዚህ ከአልጋ ቤተ-መጽሐፍት የመጡ ዓይነቶች አይደሉም. አልጋ ላልተመሩ የሁለትዮሽ ግራፎች ውክልና የለውም። ግልጽ ለማድረግ እንደዚህ አይነት ዓይነቶችን አዘጋጅቻለሁ.

እንዲሁም ከሚከተሉት ፊርማዎች ጋር የረዳት ተግባራትን እንፈልጋለን።

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

በጥልቅ-የመጀመሪያ ፍለጋ ወቅት እርስ በርሱ የሚጋጭ ጠርዝ ካገኘን ፣ ያልተለመደው ዑደት በድግግሞሽ ቁልል አናት ላይ እንደሚገኝ ለማየት ቀላል ነው። ስለዚህ, ወደነበረበት ለመመለስ, ከተደጋገሙ ቁልል ጀምሮ እስከ የመጨረሻው ጫፍ የመጀመሪያ ክስተት ድረስ ሁሉንም ነገር መቁረጥ አለብን.

የጥልቀት-የመጀመሪያ ፍለጋን እንተገብራለን ለእያንዳንዱ ቬቴክስ አሶሺዬቲቭ የአክሲዮን ቁጥሮችን በመጠበቅ። የድጋሚ ቁልል በመረጥነው የፈንጠዝያ ክፍል ትግበራ አማካኝነት በራስ-ሰር ይጠበቃል፡ ከመንገዱ ወደ ተደጋጋሚ ተግባር ወደ ተመለሰው ውጤት ሁሉንም ጫፎች ብቻ ማስቀመጥ አለብን።

የእኔ የመጀመሪያ ሀሳብ እኛ የምንፈልገውን ተፅእኖ በትክክል የሚተገበር የሚመስለውን ወይ ሞናድን መጠቀም ነበር። የጻፍኩት የመጀመሪያ አተገባበር ለዚህ አማራጭ በጣም ቅርብ ነበር። እንደውም በአንድ ወቅት አምስት የተለያዩ አተገባበርዎች ነበሩኝ እና በመጨረሻ በሌላኛው ላይ ተቀመጥኩ።

በመጀመሪያ፣ የአጋርነት መለያዎችን ድርድር ማቆየት አለብን - ይህ ስለ ግዛት የሆነ ነገር ነው። በሁለተኛ ደረጃ, ግጭት ሲታወቅ ማቆም መቻል አለብን. ይህ Monad ለ ወይ ወይም MonadPlus ለ ምናልባት ሊሆን ይችላል። ዋናው ልዩነት ስሌቱ ካልተቋረጠ ዋጋውን መመለስ ይችላል, እና ምናልባት በዚህ ጉዳይ ላይ ስለዚህ ጉዳይ መረጃን ብቻ ይመልሳል. ለስኬት የተለየ ዋጋ ስለማንፈልግ (ቀድሞውኑ በግዛት ውስጥ ተከማችቷል)፣ ምናልባት እንመርጣለን። እና የሁለት ሞናዶችን ተፅእኖዎች ማዋሃድ በሚያስፈልገን ጊዜ, እነሱ ይወጣሉ ሞንዳድ ትራንስፎርመሮች, በትክክል እነዚህን ተፅዕኖዎች የሚያጣምረው.

ለምን እንደዚህ አይነት ውስብስብ አይነት መረጥኩ? ሁለት ምክንያቶች. በመጀመሪያ ደረጃ, አተገባበሩ ከአስፈላጊው ጋር በጣም ተመሳሳይ ነው. ሁለተኛ፣ ከድግግሞሽ ወደ ኋላ ስንመለስ ግጭት በሚፈጠርበት ጊዜ የመመለሻ እሴቱን ማስተካከል አለብን፣ ይህም ያልተለመደውን ዑደት ወደነበረበት ለመመለስ በ Maybe monad ውስጥ በጣም ቀላል ነው።

ስለዚህ ይህንን ትግበራ እናገኛለን.

{-# 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 የጥልቀት-የመጀመሪያው ፍለጋ አካል ነው ለመጀመሪያ ጊዜ አከርካሪውን የምንጎበኝበት። እዚህ የማጋራት ቁጥርን ወደ ቬርቴክስ እንመድባለን እና onEdge በሁሉም ጎረቤቶች ላይ እናስኬዳለን። ይህ ደግሞ የጥሪ ቁልል ወደነበረበት የምንመለስበት ነው፡ msum እሴት ከመለሰ፣ እኛ እዚያ ቁልል እንገፋለን።
• onEdge ጠርዙን የምንጎበኝበት ክፍል ነው። ለእያንዳንዱ ጠርዝ ሁለት ጊዜ ይባላል. እዚህ በሌላኛው በኩል ያለው ጫፍ የተጎበኘ መሆኑን እናረጋግጣለን, እና ካልሆነ ይጎብኙት. ከተጎበኘ, ጠርዙ እርስ በርስ የሚጋጭ መሆኑን እናረጋግጣለን. ከሆነ ፣ እሴቱን እንመልሳለን - የመድገሚያ ቁልል የላይኛው ክፍል ፣ ከዚያ ሁሉም ሌሎች ጫፎች ሲመለሱ ይቀመጣሉ።
• ፕሮሰስ ቬርቴክስ እያንዳንዱን ቋጥኝ የተጎበኘ መሆኑን ያረጋግጣል እና ካልሆነ በላዩ ላይ በቬርቴክስ ይሰራል።
• dfs በሁሉም ጫፎች ላይ ቨርቴክስን ያካሂዳል።

ይኼው ነው.

INLINE የሚለው ቃል ታሪክ

INLINE የሚለው ቃል በአልጎሪዝም የመጀመሪያ አተገባበር ውስጥ አልነበረም፤ በኋላ ላይ ታየ። የተሻለ አተገባበር ለማግኘት ስሞክር INLINE ያልሆነው እትም በአንዳንድ ግራፎች ላይ በሚያስደንቅ ሁኔታ ቀርፋፋ ሆኖ አግኝቼዋለሁ። በትርጉም ደረጃ ተግባራቶቹ አንድ አይነት መስራት እንዳለባቸው ግምት ውስጥ በማስገባት ይህ በጣም አስገረመኝ። እንግዳ እንኳን፣ ሌላ የጂኤችሲ ስሪት ባለው ሌላ ማሽን ላይ ምንም የሚታይ ልዩነት አልነበረም።

የGHC Core ውፅዓትን አንድ ሳምንት ካነበብኩ በኋላ፣ ችግሩን በአንድ መስመር ግልጽ በሆነ INLINE ማስተካከል ችያለሁ። በተወሰነ ጊዜ በGHC 8.4.4 እና GHC 8.6.5 መካከል አመቻች በራሱ ይህን ማድረግ አቆመ።

በ Haskell ፕሮግራሚንግ ላይ እንደዚህ ያለ ቆሻሻ ያጋጥመኛል ብዬ አልጠበኩም ነበር። ይሁን እንጂ ዛሬም ቢሆን አመቻቾች አንዳንድ ጊዜ ስህተት ይሠራሉ, እና ለእነሱ ፍንጭ መስጠት የእኛ ስራ ነው. ለምሳሌ, እዚህ ውስጥ ተግባሩ የግድ መሆን እንዳለበት እናውቃለን, ምክንያቱም በአስፈላጊው ስሪት ውስጥ ነው, እና ይህ ለአቀነባባሪው ፍንጭ ለመስጠት ምክንያት ነው.

ከዚያስ ምን ሆነ?

ከዚያም ሆፕክሮፍት-ካርፕ አልጎሪዝምን ከሌሎች ሞናዶች ጋር ተግባራዊ አድርጌያለሁ፣ እና ያ የፕሮግራሙ መጨረሻ ነበር።

ለጎግል የበጋ ኮድ ምስጋና ይግባውና በተግባራዊ ፕሮግራሚንግ ላይ ተግባራዊ ልምድ አግኝቻለሁ፣ ይህም በሚቀጥለው የበጋ ወቅት በጄን ጎዳና ላይ ልምምድ እንዳገኝ ረድቶኛል (ይህ ቦታ ምን ያህል በሀብር እውቀት ባላቸው ታዳሚዎች መካከል እንኳን እንደሚታወቅ እርግጠኛ አይደለሁም ፣ ግን አንዱ ነው) በተግባራዊ ፕሮግራሚንግ ላይ ለመሳተፍ በበጋ ከምትችሉት ጥቂቶች) ነገር ግን በባህላዊ ቋንቋዎች ካለኝ ልምድ በተለየ መልኩ ይህንን ምሳሌ በተግባር የማዋልን አስደናቂውን ዓለም አስተዋወቀኝ።

ምንጭ: hab.com