گذريل اونهاري ۾ مون حصو ورتو - گوگل جي شاگردن لاءِ هڪ پروگرام. هر سال، منتظمين ڪيترن ئي اوپن سورس پروجيڪٽ کي چونڊيندا آهن، جن ۾ اهڙين معروف تنظيمن مان شامل آهن и . گوگل سڄي دنيا جي شاگردن کي انهن منصوبن تي ڪم ڪرڻ جي دعوت ڏئي ٿو.
گوگل سمر آف ڪوڊ 2019 ۾ هڪ شرڪت جي طور تي، مون لائبريري اندر هڪ پروجيڪٽ ڪيو تنظيم سان گڏ ، جيڪا ترقي ڪري رهي آهي هاسڪيل ٻولي - هڪ مشهور فنڪشنل پروگرامنگ ٻولين مان. Alga هڪ لائبريري آهي جيڪا نمائندگي ڪري ٿي Haskell ۾ گراف جي نمائندگي. اهو استعمال ڪيو ويندو آهي، مثال طور، ۾ - هڪ Github لائبريري جيڪا ڪوڊ جي بنياد تي سيمينٽڪ وڻ، ڪال ۽ انحصار گراف ٺاهي ٿي ۽ انهن جو مقابلو ڪري سگهي ٿي. منهنجو منصوبو شامل ڪرڻ هو هڪ قسم جي محفوظ نمائندگي لاءِ ٻه طرفي گرافس ۽ ان نمائندگي لاءِ الگورتھم.
هن تحرير ۾ مان ڳالهائيندس هڪ الگورٿم تي عمل ڪرڻ لاءِ هڪ گراف چيڪ ڪرڻ لاءِ هاسڪل ۾ ٻه طرفي لاءِ. جيتوڻيڪ الورورٿم سڀ کان وڌيڪ بنيادي مان هڪ آهي، ان کي سهڻي انداز ۾ لاڳو ڪرڻ هڪ فنڪشنل انداز ۾ مون کي ڪيترائي ورجائي ورتو ۽ ڪافي ڪم جي ضرورت آهي. نتيجي طور، مون مونڊ ٽرانسفارمرز سان عمل درآمد تي آباد ڪيو.
پاڻ بابت
منهنجو نالو Vasily Alferov آهي، مان سينٽ پيٽرسبرگ HSE ۾ چوٿين سال جو شاگرد آهيان. بلاگ ۾ اڳ ۾ مون لکيو هو и . هن وقت مان هڪ انٽرنيشنل شپ تي آهيان ناروي ۾، جتي آئون ڪم ڪري رهيو آهيان مسئلن جي طريقن تي . منهنجي دلچسپين ۾ شامل آهن parameterized algorithms ۽ فنڪشنل پروگرامنگ.
الورورٿم جي عمل جي باري ۾
اڳوڻي
پروگرام ۾ حصو وٺندڙ شاگردن کي بلاگ ڪرڻ لاءِ زور ڀريو وڃي ٿو. انهن مون کي بلاگ لاءِ پليٽ فارم فراهم ڪيو . هي مضمون ترجمو آهي ، مون پاران جولاءِ ۾ انگريزيءَ ۾ لکيو ويو، مختصر پيشڪش سان.
سوال ۾ ڪوڊ سان پل درخواست ڳولي سگھجي ٿو .
توهان منهنجي ڪم جي نتيجن بابت پڙهي سگهو ٿا (انگريزي ۾) .
هن پوسٽ جو مقصد پڙهندڙن کي فنڪشنل پروگرامنگ جي بنيادي مفهومن سان واقف ڪرڻ آهي، جيتوڻيڪ مان ڪوشش ڪندس ته وقت اچڻ تي استعمال ڪيل سڀني اصطلاحن کي ياد ڪرڻ جي.
ٻه طرفي لاء گراف جي جانچ ڪندي
ٻه طرفي لاءِ گراف کي جانچڻ لاءِ هڪ الگورٿم عام طور تي الورورٿمس تي هڪ ڪورس ۾ ڏنو ويندو آهي هڪ آسان گراف الگورٿم مان. هن جو خيال بلڪل سادو آهي: پهرين اسين ڪنهن نه ڪنهن طرح کاٻي يا ساڄي حصي ۾ ڪنڌ وجهي، ۽ جڏهن متضاد ڪنڊ ملي ٿي، اسان اهو سمجهون ٿا ته گراف ٻه طرفي نه آهي.
ٿورڙو وڌيڪ تفصيل: پهرين اسان کاٻي حصي ۾ ڪجهه عمودي رکون ٿا. ظاهر آهي، هن عمودي جا سڀئي پاڙيسري ساڄي لوب ۾ ڪوڙ هجڻ گهرجن. ان کان سواء، هن عمدي جي پاڙيسري جي سڀني پاڙيسرين کي کاٻي لوب ۾ ڪوڙ هجڻ گهرجي، وغيره. اسان ويڙهاڪن کي شيئرز تفويض ڪرڻ جاري رکون ٿا جيستائين اڃا تائين ڪنيڪشن جي جڙيل حصي ۾ عمودي موجود آهن جن سان اسان شروع ڪيو آهي ته اسان پاڙيسرين کي تفويض نه ڪيو آهي. اسان وري هن عمل کي سڀني ڳنڍيل اجزاء لاء ورجائيندا آهيون.
جيڪڏهن هڪ ئي ورهاڱي ۾ ڦاٿل چوڪن جي وچ ۾ هڪ ڪنڊ آهي، ته گراف ۾ هڪ عجيب چڪر ڳولڻ ڏکيو ناهي، جيڪو وڏي پيماني تي ڄاڻايل آهي (۽ بلڪل واضح طور تي) هڪ بائيپارٽ گراف ۾ ناممڪن آهي. ٻي صورت ۾، اسان وٽ صحيح ورهاڱي آهي، جنهن جو مطلب آهي گراف ٻه طرفي آهي.
عام طور تي، هي الگورتھم استعمال ڪندي لاڳو ڪيو ويندو آهي يا . لازمي ٻولين ۾، گہرائي-پهريون ڳولها عام طور تي استعمال ڪئي ويندي آهي جيئن ته اهو ٿورو آسان آهي ۽ اضافي ڊيٽا جي جوڙجڪ جي ضرورت ناهي. مون پڻ گہرائي-پهريون ڳولها چونڊيو آهي جيئن اها وڌيڪ روايتي آهي.
اهڙيء طرح، اسان هيٺ ڏنل اسڪيم تي آيا آهيون. اسان گراف جي چوٽيءَ کي ڊيپٿ فرسٽ سرچ استعمال ڪندي پار ڪريون ٿا ۽ انهن کي شيئر تفويض ڪريون ٿا، شيئر جي تعداد کي تبديل ڪندي جيئن اسين ڪنارن سان گڏ هلون ٿا. جيڪڏهن اسان ڪوشش ڪريون ٿا ته هڪ شيئر کي هڪ ورڪس تي تفويض ڪيو وڃي جنهن ۾ اڳ ۾ ئي هڪ شيئر لڳايو ويو آهي، اسان محفوظ طور تي چئي سگهون ٿا ته گراف ٻه طرفي نه آهي. جنهن وقت سڀني عمودين کي هڪ شيئر لڳايو ويو آهي ۽ اسان سڀني ڪنارن کي ڏٺو آهي، اسان وٽ سٺو ورهاڱو آهي.
حساب جي صفائي
هاسڪيل ۾ اسان فرض ڪريون ٿا ته سڀئي حساب ڪتاب آهن صاف. بهرحال، جيڪڏهن اهو واقعي ڪيس هو، اسان وٽ اسڪرين تي ڪا به شيء پرنٽ ڪرڻ جو ڪو طريقو نه هوندو. بلڪل، صاف حساب ايترو سست آهي جو هڪ به ناهي صاف ڪجهه حساب ڪرڻ جا سبب. پروگرام ۾ ٿيندڙ سڀ حساب ڪتاب ڪنهن نه ڪنهن طرح تي مجبور آهن "ناپاڪ" مونڊ IO.
Monads حساب سان نمائندگي ڪرڻ جو هڪ طريقو آهي اثرات Haskell ۾. وضاحت ڪرڻ ته اهي ڪيئن ڪم ڪن ٿا هن پوسٽ جي دائري کان ٻاهر. سٺي ۽ صاف وضاحت انگريزيءَ ۾ پڙهي سگهجي ٿي .
هتي مان اهو ٻڌائڻ چاهيان ٿو ته جڏهن ڪجهه مونڊس، جهڙوڪ IO، ڪمپيلر جادو ذريعي لاڳو ڪيا ويا آهن، تقريبن سڀئي ٻيا سافٽ ويئر ۾ لاڳو ڪيا ويا آهن ۽ انهن ۾ سڀ حساب خالص آهن.
اتي تمام گھڻا اثر آھن ۽ ھر ھڪ جو پنھنجو منڊ آھي. هي هڪ تمام مضبوط ۽ خوبصورت نظريو آهي: سڀئي مونڊس هڪ ئي انٽرفيس تي عمل ڪندا آهن. اسان هيٺ ڏنل ٽن مانڊس بابت ڳالهائينداسين:
- يا ته ea ھڪڙو حساب آھي جيڪو ھڪڙي قسم جي قيمت کي واپس ڪري ٿو يا قسم اي جي استثنا کي اڇلائي ٿو. هن منڊ جو رويو لازمي ٻولين ۾ استثنا جي سنڀال سان تمام گهڻو ملندو آهي: غلطيون پڪڙي سگهجن ٿيون يا منظور ٿي سگهن ٿيون. بنيادي فرق اهو آهي ته مونڊ مڪمل طور تي منطقي طور تي هاسڪيل ۾ معياري لائبريري ۾ لاڳو ڪيو ويو آهي، جڏهن ته لازمي ٻوليون عام طور تي آپريٽنگ سسٽم ميڪانيزم استعمال ڪندا آهن.
- اسٽيٽ sa هڪ حساب ڪتاب آهي جيڪو موٽائي ٿو هڪ قسم جي قيمت ۽ ان کي رسائي آهي تبديل ٿيندڙ حالت جي قسم s تائين.
- شايد اي. شايد مونڊ هڪ حساب جو اظهار ڪري ٿو جيڪو ڪنهن به وقت ڪجهه به نه موٽڻ سان مداخلت ڪري سگهجي ٿو. تنهن هوندي، اسان ممڪن قسم جي لاء MonadPlus ڪلاس جي عمل جي باري ۾ ڳالهائينداسين، جيڪو مخالف اثر کي ظاهر ڪري ٿو: اهو هڪ حساب آهي جيڪو ڪنهن به وقت ڪنهن مخصوص قيمت کي واپس ڪندي مداخلت ڪري سگهجي ٿو.
الگورتھم جو نفاذ
اسان وٽ ڊيٽا جا ٻه قسم آهن، گراف a ۽ Bigraph ab، جن مان پهريون گراف ڏيکاري ٿو عمودي خطن سان ليبل ٿيل قسم a جي قدرن سان، ۽ ٻيو ڏيکاري ٿو bipartite گرافس جن کي کاٻي پاسي واري عمودي سان ليبل ٿيل آهي قسم a ۽ ساڄي جي قدرن سان. -ب- قسم جي قدرن سان ليبل ٿيل پاسي واري چوٽي.
اهي قسم نه آهن Alga لائبريري مان. Alga ۾ اڻ سڌي طرح بائيپارٽي گرافس جي نمائندگي نه آھي. مون وضاحت لاءِ هن قسم جا قسم ٺاهيا آهن.
اسان کي هيٺين دستخطن سان مددگار ڪمن جي ضرورت پوندي.
-- Список соседей данной вершины.
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)
جتي بلاڪ الورورٿم جو بنيادي حصو آهي. ان جي اندر ڇا ٿي رهيو آهي ان کي بيان ڪرڻ جي ڪوشش ڪندس.
- inVertex depth-first search جو حصو آهي جتي اسان پهريون ڀيرو ويرٽيڪس جو دورو ڪيو. ھتي اسان ھڪڙي شيئر نمبر کي عمودي ڏانھن تفويض ڪريون ٿا ۽ سڀني پاڙيسرين تي ايج کي هلائيندا آھيون. اهو پڻ آهي جتي اسان ڪال اسٽيڪ کي بحال ڪريون ٿا: جيڪڏهن msum هڪ قيمت واپس ڪئي، اسان اتي ويٽڪس وي کي دٻايو.
- onEdge اهو حصو آهي جتي اسان کنڊ جو دورو ڪندا آهيون. اهو هر ڪنڊ لاء ٻه ڀيرا سڏيو ويندو آهي. هتي اسان چيڪ ڪريون ٿا ته ڇا ٻئي پاسي واري عمدي جو دورو ڪيو ويو آهي، ۽ ان جو دورو ڪريو جيڪڏهن نه. جيڪڏهن دورو ڪيو ويو، اسان چيڪ ڪريون ٿا ته ڇا کنڊ متضاد آهي. جيڪڏهن اهو آهي، اسان قيمت واپس ڪريون ٿا - ريٽرننگ اسٽيڪ جي بلڪل مٿئين حصي، جتي ٻيا سڀئي عمودي وري واپسي تي رکيا ويندا.
- processVertex چيڪ ڪري ٿو هر vertex لاءِ ته ڇا اهو دورو ڪيو ويو آهي ۽ ان تي Vertex هلندو آهي جيڪڏهن نه.
- dfs هلائي ٿو پروسيس ويرٽيڪس سڀني چوڪن تي.
اهو ئي سڀ ڪجهه آهي.
لفظ INLINE جي تاريخ
لفظ INLINE الورورٿم جي پهرين عمل ۾ نه هو؛ اهو بعد ۾ ظاهر ٿيو. جڏهن مون هڪ بهتر عمل درآمد ڳولڻ جي ڪوشش ڪئي، مون ڏٺو ته غير ان لائن ورزن ڪجهه گرافس تي خاص طور تي سست هو. انهي ڳالهه تي غور ڪندي ته لفظي طور تي افعال ساڳيو ڪم ڪرڻ گهرجي، اهو مون کي تمام گهڻو حيران ڪيو. جيتوڻيڪ اجنبي، هڪ ٻي مشين تي GHC جي مختلف ورزن سان ڪو به قابل ذڪر فرق نه هو.
GHC ڪور آئوٽ پڙهڻ ۾ هڪ هفتو گذارڻ کان پوءِ، مان ان مسئلي کي حل ڪرڻ جي قابل ٿيس ان لائن جي هڪ قطار سان. ڪجهه نقطي تي GHC 8.4.4 ۽ GHC 8.6.5 جي وچ ۾ اصلاح ڪندڙ پنهنجو پاڻ تي اهو ڪرڻ بند ڪيو.
مون کي اميد نه هئي ته هاسڪيل پروگرامنگ ۾ اهڙي گندگي سان منهن ڏيڻ. بهرحال، اڄ به، اصلاح ڪندڙ ڪڏهن ڪڏهن غلطيون ڪندا آهن، ۽ اهو اسان جو ڪم آهي انهن کي اشارو ڏيڻ. مثال طور، هتي اسان ڄاڻون ٿا ته فنڪشن کي اندر اندر هجڻ گهرجي ڇو ته اهو لازمي نسخي ۾ اندر اندر آهي، ۽ اهو هڪ سبب آهي ته مرتب ڪندڙ کي اشارو ڏيو.
اڳتي ڇا ٿيو؟
ان کان پوء مون ٻين منڊس سان Hopcroft-Karp الگورتھم کي لاڳو ڪيو، ۽ اھو پروگرام جي پڄاڻي ھئي.
گوگل سمر آف ڪوڊ جي مهرباني، مون فنڪشنل پروگرامنگ ۾ عملي تجربو حاصل ڪيو، جنهن نه صرف مون کي ايندڙ اونهاري ۾ جين اسٽريٽ تي انٽرنشپ حاصل ڪرڻ ۾ مدد ڪئي (مون کي پڪ ناهي ته هي جڳهه ڪيتري مشهور آهي حبر جي ڄاڻ رکندڙ سامعين ۾، پر اهو هڪ آهي. ڪجھ مان جتي توھان اونهاري ڪري سگھوٿا فنڪشنل پروگرامنگ ۾ مشغول ٿيڻ لاءِ)، پر مون کي ھن مثالي نموني کي عملي طور تي لاڳو ڪرڻ جي شاندار دنيا سان پڻ متعارف ڪرايو، روايتي ٻولين ۾ منھنجي تجربي کان بلڪل مختلف.
جو ذريعو: www.habr.com