تیر دوبی ما برخه واخیسته - د ګوګل څخه د زده کونکو لپاره یو برنامه. هر کال، تنظیم کونکي د خلاصې سرچینې ډیری پروژې غوره کوي، پشمول د داسې مشهور سازمانونو څخه и . ګوګل د ټولې نړۍ زده کونکو ته بلنه ورکوي چې پدې پروژو کار وکړي.
د ګوګل سمر آف کوډ 2019 کې د ګډون کونکي په توګه ، ما په کتابتون کې یوه پروژه ترسره کړه د سازمان سره ، کوم چې د هاسکل ژبه رامینځته کوي - یو له خورا مشهور فعال برنامه کولو ژبو څخه. الګا یو کتابتون دی چې استازیتوب کوي په هاسکل کې د ګرافونو استازیتوب. دا د مثال په توګه کارول کیږي - د ګیتوب کتابتون چې د کوډ پراساس سیمانټیک ونې ، زنګ او د انحصار ګرافونه رامینځته کوي او پرتله کولی شي. زما پروژه د دې نمایش لپاره د دوه اړخیز ګرافونو او الګوریتمونو لپاره د ډول خوندي نمایش اضافه کول وو.
پدې پوسټ کې به زه په هاسکل کې د دوه اړخیزې ګراف چیک کولو لپاره زما د الګوریتم پلي کولو په اړه وغږیږم. که څه هم الګوریتم یو له خورا بنسټیزو څخه دی، په فعاله بڼه کې په ښکلي ډول پلي کول ما څو تکرارونه واخیستل او ډیر کار ته اړتیا درلوده. د پایلې په توګه، ما د موناد ټرانسفارمرونو سره په پلي کولو کې میشته شوم.
زما په اړه
زما نوم واسیلي الفروف دی، زه په سینټ پیټرزبورګ HSE کې د څلورم کال محصل یم. مخکې په بلاګ کې ما لیکلي و и . همدا اوس زه په انټرنشپ کې یم په ناروې کې، چیرته چې زه د ستونزې د حل لپاره کار کوم . زما په ګټو کې پیرامیټریز شوي الګوریتمونه او فعال پروګرامونه شامل دي.
د الګوریتم پلي کولو په اړه
وړاندیز
هغه زده کونکي چې په برنامه کې برخه اخلي په کلکه هڅول کیږي چې بلاګ وکړي. دوی ما ته د بلاګ لپاره یو پلیټ فارم چمتو کړ . دا مقاله ژباړه ده ، زما لخوا د جولای په میاشت کې په انګلیسي کې لیکل شوی ، د لنډې ماخذ سره.
د پوښتنې کوډ سره د پلولو غوښتنه موندل کیدی شي .
تاسو کولی شئ زما د کار پایلو په اړه ولولئ (په انګلیسي کې) .
دا پوسټ داسې انګیرل کیږي چې لوستونکی په فعاله برنامه کې د لومړني مفاهیمو سره آشنا دی ، که څه هم زه به هڅه وکړم ټول هغه شرایط یاد کړم چې وخت راشي.
د دوه اړخیزوالي لپاره د ګرافونو چک کول
د دوه اړخیزوالي لپاره د ګراف چک کولو لپاره الګوریتم معمولا د الګوریتم په کورس کې د یو ساده ګراف الګوریتم په توګه ورکول کیږي. د هغه مفکوره مستقیمه ده: لومړی موږ په یو څه ډول په کیڼ یا ښي برخه کې عمودی کیږدو، او کله چې یو متضاد څنډه وموندل شي، موږ ادعا کوو چې ګراف دوه اړخیز نه دی.
یو څه نور توضیحات: لومړی موږ په ښي برخه کې یو څه عمودی کیښودو. په ښکاره ډول، د دې عمودی ټول ګاونډیان باید په ښي لوبی کې پروت وي. برسېره پر دې، د دې عمودی ګاونډیو ټول ګاونډیان باید په کیڼ لاس کې پروت وي، او داسې نور. موږ عمودیو ته د ونډو ټاکلو ته دوام ورکوو تر هغه چې د عمودی تړلې برخې کې اوس هم عمودی شتون لري چې موږ یې پیل کړی چې موږ ګاونډیانو ته نه دی ټاکلی. بیا موږ دا عمل د ټولو تړلو برخو لپاره تکرار کوو.
که چیرې د عمودیو په منځ کې یوه څنډه شتون ولري چې په ورته ویش کې راوتلی وي، نو دا ستونزمنه نه ده چې په ګراف کې یو عجیب دور ومومئ، کوم چې په پراخه توګه پیژندل شوی (او په ښکاره ډول) په دوه اړخیز ګراف کې ناممکن دی. که نه نو، موږ سمه برخه لرو، پدې معنی چې ګراف دوه اړخیز دی.
عموما، دا الګوریتم په کارولو سره پلي کیږي او یا . په اړینو ژبو کې، د ژورې لومړنۍ لټون معمولا کارول کیږي ځکه چې دا یو څه ساده دی او د معلوماتو اضافي جوړښتونو ته اړتیا نلري. ما هم د ژورې لومړنۍ لټون غوره کړ ځکه چې دا ډیر دودیز دی.
په دې توګه، موږ لاندې سکیم ته راغلو. موږ د ژورې لومړۍ پلټني په کارولو سره د ګراف عمودی وګرځوو او دوی ته ونډې ټاکو، د ونډې شمیره بدلوي کله چې موږ د څنډې په اوږدو کې حرکت کوو. که موږ هڅه وکړو چې یوې برخې ته یوه برخه وټاکو چې دمخه یې برخه ټاکل شوې وي، موږ کولی شو په خوندي ډول ووایو چې ګراف دوه اړخیز نه دی. هغه شیبه چې ټول عمودی برخه ټاکل شوې وي او موږ ټولو څنډو ته ګورو، موږ ښه ویش لرو.
د محاسبې پاکوالی
په هاسکل کې موږ فرض کوو چې ټول حسابونه دي پاک په هرصورت، که دا واقعیا قضیه وي، موږ به په سکرین کې د هیڅ شی چاپولو لپاره هیڅ لاره ونه لرو. هیڅکله، پاک محاسبه دومره سسته ده چې یو هم نشته پاک د یو څه محاسبه کولو دلایل. ټول حسابونه چې په برنامه کې پیښیږي په یو ډول جبري کیږي "ناپاک" monad IO.
مونډز د محاسبې نمایندګۍ یوه لاره ده اغیزې په هاسکل کې تشریح کول چې دوی څنګه کار کوي د دې پوسټ له دائرې بهر دی. یو ښه او روښانه توضیحات په انګلیسي کې لوستل کیدی شي .
دلته زه غواړم په ګوته کړم چې پداسې حال کې چې ځینې مونډونه ، لکه IO ، د کمپیلر جادو له لارې پلي کیږي ، نږدې ټول نور په سافټویر کې پلي کیږي او په دوی کې ټول حسابونه خالص دي.
ډیری اغیزې شتون لري او هر یو یې خپل موناد لري. دا خورا قوي او ښکلې تیوري ده: ټول مونډونه ورته انٹرفیس پلي کوي. موږ به د لاندې دریو مانادونو په اړه وغږیږو:
- یا هم ea یوه محاسبه ده چې د ډول a ارزښت بیرته راګرځوي یا د e ډول استثنا غورځوي. د دې ماناد چلند په لازمي ژبو کې د استثنایی مدیریت سره ورته دی: تېروتنې نیول کیدی شي یا تیریږي. اصلي توپیر دا دی چې مونډ په بشپړ ډول په منطقي ډول په هاسکل کې په معیاري کتابتون کې پلي کیږي ، پداسې حال کې چې لازمي ژبې معمولا د عملیاتي سیسټم میکانیزمونه کاروي.
- State sa یوه محاسبه ده چې د ډول a ارزښت بیرته راګرځوي او د s ډول بدلیدونکي حالت ته لاسرسی لري.
- شاید یو. شاید مونډ یو داسې محاسبه څرګندوي چې په هر وخت کې د هیڅ شی په راستنولو سره مداخله کیدی شي. په هرصورت، موږ به د ممکن ډول لپاره د MonadPlus ټولګي پلي کولو په اړه وغږیږو، کوم چې مخالف اغیزه څرګندوي: دا یو حساب دی چې په هر وخت کې د یو ځانګړي ارزښت بیرته راستنیدو سره مداخله کیدی شي.
د الګوریتم پلي کول
موږ د ډیټا دوه ډولونه لرو، ګراف a او Bigraph ab، چې لومړی یې د ګرافونو نمایندګي کوي د عمودی ډولونو سره چې د ډول A ارزښتونو سره لیبل شوي، او دوهم یې د دوه اړخیز ګرافونو استازیتوب کوي د کیڼ اړخ عمودی سره چې د ډول a او ښي ارزښتونو سره لیبل شوي. -د اړخ عمودی د ډول بی ارزښتونو سره لیبل شوی.
دا د الګا کتابتون ډولونه ندي. الګا د غیر مستقیم دوه اړخیز ګرافونو لپاره نمایش نه لري. ما د وضاحت لپاره دا ډول ډولونه جوړ کړل.
موږ به د لاندې لاسلیکونو سره مرستندویه کارونو ته هم اړتیا ولرو:
-- Список соседей данной вершины.
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)دا په اسانۍ سره لیدل کیږي چې که موږ د ژورې لومړنۍ لټون په جریان کې یو متضاد څنډه وموندله، عجیب دوره د تکرار سټیک په سر کې پروت دی. په دې توګه، د دې د بیا رغولو لپاره، موږ اړتیا لرو چې د تکرار سټیک څخه د وروستي عمودی لومړي پیښې پورې هرڅه پرې کړو.
موږ د هر عمودی لپاره د شریک شمیرو د شریک شمیرو په ساتلو سره ژور - لومړی لټون پلي کوو. د تکرار سټیک به په اوتومات ډول د مونډ د فنکټور ټولګي پلي کولو له لارې ساتل کیږي چې موږ غوره کړی دی: موږ به یوازې د لارې څخه ټول عمودي برخې ته د تکراري فنکشن څخه راستنیدونکي پایلې ته اړتیا ولرو.
زما لومړی نظر د 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 د ژورې لومړنۍ لټون برخه ده چیرې چې موږ د لومړي ځل لپاره ورټیکس څخه لیدنه کوو. دلته موږ عمودی ته د ونډې شمیره ورکوو او په ټولو ګاونډیو کې onEdge چلوو. دا هم هغه ځای دی چې موږ د کال سټیک بحال کوو: که msum یو ارزښت بیرته راوباسي، نو موږ vertex v هلته فشار ورکوو.
- onEdge هغه برخه ده چیرې چې موږ څنډې ته ګورو. دا د هرې څنډې لپاره دوه ځله ویل کیږي. دلته موږ وګورو چې آیا د بل اړخ عمودی لیدل شوی، او لیدنه یې وکړه که نه. که لیدنه وشي، موږ ګورو چې ایا څنډه متضاد ده. که دا وي، موږ ارزښت بیرته راګرځوو - د تکرار سټیک خورا پورتنۍ برخه، چیرې چې نور ټول عمودي به بیا د بیرته راستنیدو پرمهال ځای په ځای شي.
- processVertex د هر عمودی لپاره چک کوي چې ایا دا لیدل شوي او په هغې باندې ورټیکس چلوي که نه.
- dfs په ټولو عمودیو کې پروسس ویرټیکس چلوي.
بس نور څه نه.
د انلاین کلمې تاریخ
د انلاین کلمه د الګوریتم په لومړي پلي کولو کې نه وه؛ دا وروسته ښکاره شوه. کله چې ما د ښه تطبیق موندلو هڅه وکړه، ما وموندله چې غیر انلاین نسخه په ځینو ګرافونو کې د پام وړ ورو وه. د دې په پام کې نیولو سره چې په معنی ډول دندې باید ورته کار وکړي ، دا ما خورا حیران کړ. حتی اجنبی ، په بل ماشین کې د GHC مختلف نسخه سره هیڅ د پام وړ توپیر نه و.
د GHC کور محصول لوستلو یوه اونۍ تیرولو وروسته ، زه وکولی شوم ستونزه د واضح انلاین یوې کرښې سره حل کړم. په ځینو وختونو کې د GHC 8.4.4 او GHC 8.6.5 ترمنځ اصلاح کونکي په خپله دا کار بند کړ.
ما تمه نه درلوده چې د هاسکل برنامه کې د داسې کثافاتو سره مخ شم. په هرصورت، حتی نن ورځ، اصلاح کونکي کله ناکله غلطي کوي، او دا زموږ دنده ده چې دوی ته اشاره وکړو. د مثال په توګه، دلته موږ پوهیږو چې فنکشن باید په لیکه کې وي ځکه چې دا په لازمي نسخه کې دننه شوی، او دا یو دلیل دی چې کمپیلر ته اشاره ورکوي.
بیا څه وشول؟
بیا ما د نورو مونډونو سره د Hopcroft-Karp الګوریتم پلي کړ، او دا د برنامه پای وه.
د ګوګل سمر کوډ څخه مننه، ما په فعال پروګرام کولو کې عملي تجربه ترلاسه کړه، کوم چې نه یوازې ما سره په راتلونکي دوبي کې په جین سټریټ کې د انټرنشپ ترلاسه کولو کې مرسته وکړه (زه ډاډه نه یم چې دا ځای حتی د حبر د پوهو لیدونکو ترمنځ څومره پیژندل شوی، مګر دا یو دی. د یو څو څخه چیرې چې تاسو کولی شئ په فعاله برنامو کې دخیل کیدو لپاره اوړي) ، مګر ما په عمل کې د دې تمثیل پلي کولو عالي نړۍ ته هم معرفي کړ ، په دودیزو ژبو کې زما له تجربې څخه د پام وړ توپیر لري.
سرچینه: www.habr.com