ProHoster > Të gjejmë rend në kaosin e IT-së: burimet e dobishme

Të gjejmë rend në kaosin e IT-së: burimet e dobishme

Veriun verĂ«n e kaluar mora pjesĂ« nĂ« Google Summer of Code — njĂ« program pĂ«r studentĂ«t nga kompaninĂ« Google. Çdo vit, organizatorĂ«t pĂ«rzgjidhin disa projekte Open Source, duke pĂ«rfshirĂ« nga organizata tĂ« njohura si Boost.org dhe The Linux Foundation. PĂ«r tĂ« punuar mbi kĂ«to projekte, Google fton studentĂ« nga e gjithĂ« bota. 

Si pjesĂ«marrĂ«s nĂ« Google Summer of Code 2019, unĂ« realizova njĂ« projekt brenda bibliotekĂ«s Alga nĂ« organizatĂ«n Haskell.org, e cila merret me zhvillimin e gjuhĂ«s Haskell — njĂ« nga gjuhĂ«t mĂ« tĂ« njohura tĂ« programimit funksional. Alga Ă«shtĂ« njĂ« bibliotekĂ« qĂ« ofron temĂ« tĂ« sigurt tĂ« pĂ«rfaqĂ«simit pĂ«r grafĂ«t nĂ« Haskell. Ajo pĂ«rdoret, pĂ«r shembull, nĂ« semantic — bibliotekĂ«n e kompanisĂ« Github, e cila ndĂ«rton pemĂ« semantike, grafĂ« thirrjesh dhe varĂ«sish nga kodi dhe Ă«shtĂ« nĂ« gjendje t'i krahasojĂ« ato. Projekti im pĂ«rfshinte shtimin e njĂ« pĂ«rfaqĂ«simi tĂ« sigurt pĂ«r grafĂ«t dy-pjesĂ«sh dhe algoritme pĂ«r kĂ«tĂ« pĂ«rfaqĂ«sim. 

Në këtë postim do të flas për implementimin tim të algoritmit për verifikimin e grafit për dy-pjesshmëri në Haskell. Megjithëse algoritmi është një nga më bazikët, implementimi i tij tërheqës në stilin funksional më mori disa iteracione dhe kërkoi një punë të konsiderueshme. Si rezultat, vendosa për një implementim me transformatorë monad. 

Të gjejmë rend në kaosin e IT-së: burimet e dobishme

Për vetë

Më quajnë Vasily Alfyrov, jam student i vitit të katërt në Universitetin e Peterburgut. Më parë në blog kam shkruar për projektin tim të algoritmeve të parametrizuara dhe për udhëtimin në ZuriHac. Tani po bëj një praktikë në Universitetin e Bergenit në Norvegji, ku merrem me qasjet ndaj problemit të List Coloring. Fushat e mia të interesit përfshijnë algoritmet e parametrizuara dhe programimin funksional.

Rreth implementimit të algoritmit

Parathënie

Studentët që marrin pjesë në program, këshillohen me ngulm të mbajnë një blog. Më kanë ofruar një platformë për blogun Summer of Haskell. Ky artikull është një përkthim artikulli, i shkruar prej meje për aty në korrik në anglisht, me një parathënie të vogël. 

Pull Request me kodin që po flitet, mund ta gjeni këtu.

Për rezultatet e punës sime mund të lexoni (në anglisht) këtu.

Postimi supozon njohjen e lexuesit me konceptet bazë në programimin funksional, edhe pse do të përpiqem të rikujtoj të gjitha termat e përdorura, kur të arrijë koha për to.

Verifikimi i grafëve për dy-pjeshmëri 

Algoritmi i kontrollit të grafit për ndarjen në dy pjesë zakonisht jepet në kursin e algoritmeve si një nga algoritmet më të thjeshta të grafëve. Ideja e tij është e drejtpërdrejtë: fillimisht ne në njëfarë mënyre vendosim pikat në pjesën e majtë ose të djathtë, dhe kur zbulojmë një skaj të kundërt, konfirmojmë se grafi nuk është ndarë në dy pjesë.

Më në detaje: fillimisht ne vendosim një pikë në pjesën e majtë. Sigurisht, të gjitha fqinjët e kësaj pike duhet të jenë në pjesën e djathtë. Më pas, të gjithë fqinjët e fqinjëve të kësaj pike duhet të jenë në pjesën e majtë, dhe kështu me radhë. Ne vazhdojmë të caktojmë pikave pjesët derisa në komponentin e lidhjes së pikës me të cilën filluam, të ketë ende pika të pa caktuara fqinjët. Pastaj ne e përsërisim këtë veprim për të gjitha komponentët e lidhjes.

Nëse ka një skaj midis pikave që përfundojnë në të njëjtën pjesë, nuk është e vështirë të gjejmë një cikël çifte në grafik, siç dihet gjerësisht (dhe është mjaft e qartë) e pamundur në një grafik të ndarë në dy pjesë. Përndryshe kemi një ndarje të saktë në pjesë, dhe kështu, grafi është i ndarë në dy pjesë.

Si rregull, ky algoritëm realizohet me kërkimin në gjerësi ose kërkimin në thellësi. Në gjuhët imperativë zakonisht përdoret kërkimi në thellësi, si pak më i thjeshtë dhe që nuk kërkon struktura të dhënash shtesë. Unë gjithashtu zgjodha kërkimin në thellësi si metodë më tradicionale.

Kështu, ne arritëm në skemën e mëposhtme. Ne kalojmë nëpër pikat e grafit duke përdorur kërkimin në thellësi dhe u caktojmë ato pjesë, duke ndryshuar numrin e pjesës kur kalojmë përmes një skaji. Nëse përpiqemi të ndajmë një pjesë një pikës, e cila tashmë ka një pjesë të caktuar, mund të konfirmojmë se grafi nuk është ndarë në dy pjesë. Në momentin që të gjitha pikat janë ndarë dhe ne e kemi parë të gjithë skajet, ne kemi një ndarje të mirë.

Pastrimi i llogaritjeve

Në Haskell supozojmë se të gjitha llogaritjet janë të pastra. Megjithatë, sikur kjo të ishte e vërtetë, ne nuk do të kishim mundësi të printonim asgjë në ekran. Në përgjithësi, llogaritjet të pastra janë kaq të ngadalta, saqë nuk ka asnjë arsye të pastrë për të llogaritur ndonjë gjë. Të gjitha llogaritjet që ndodhin në program, në një farë mënyre, përforcohen në "mungesën e pastërtisë" monadën IO.

Monadat janë një mënyrë për të paraqitur llogaritjet me efekte. në Haskell. Shpjegimi i mënyrës sesi ato punojnë del përtej këtij posti. Një përshkrim i mirë dhe i kuptueshëm mund të lexoni në anglisht këtu.

Këtu dua të theksoj se, ndonëse disa monada, si IO, janë të implementuara përmes magjisë së kompilatorit, pothuajse të gjitha të tjerat janë të implementuara programërisht dhe të gjitha llogaritë në to janë të pastra.

Ekzistojnë shumë efekte dhe për secilin është krijuar një monadë e vetme. Kjo është një teori shumë e fuqishme dhe e bukur: të gjitha monadat implementojnë të njëjtën ndërfaqe. Ne do të flasim për këto tri monada:

  • Either e a — njĂ« llogaritje qĂ« kthen njĂ« vlerĂ« tĂ« tipit a ose hedh njĂ« pĂ«rjashtim tĂ« tipit e. Sjellja e kĂ«saj monade Ă«shtĂ« shumĂ« e ngjashme me punĂ«n me pĂ«rjashtimet nĂ« gjuhĂ«t imperativĂ«: gabimet mund tĂ« kapen ose tĂ« kalojnĂ« mĂ« tej. Diferenca kryesore Ă«shtĂ« se monada Ă«shtĂ« e implementuar plotĂ«sisht nĂ« mĂ«nyrĂ« logjike nĂ« bibliotekĂ«n standarde nĂ« Haskell, ndĂ«rkohĂ« qĂ« nĂ« gjuhĂ«t imperativĂ« zakonisht pĂ«rdoren mekanizmat e sistemit operativ.
  • State s a — njĂ« llogaritje qĂ« kthen njĂ« vlerĂ« tĂ« tipit a dhe ka akses nĂ« njĂ« gjendje tĂ« ndryshueshme tĂ« tipit s.
  • Maybe a. Monada Maybe shpreh njĂ« llogaritje qĂ« mund tĂ« ndĂ«rpritet nĂ« çdo moment nga kthimi i Nothing. MegjithatĂ«, ne do tĂ« flasim pĂ«r implementimin e klasĂ«s MonadPlus pĂ«r tipin Maybe, qĂ« shpreh efektin e kundĂ«rt: kjo Ă«shtĂ« njĂ« llogaritje qĂ« mund tĂ« ndĂ«rpritet nĂ« çdo moment duke kthyer njĂ« vlerĂ« konkrete.

Implementimi i algoritmit

Ne kemi dy tipe të dhënash, Graph a dhe Bigraph a b, i pari nga të cilët përfaqëson grafet me pika të shënuara me vlera të tipit a, ndërsa tjetri përfaqëson grafet e dyfishta me pika të majtë të shënuara me vlera të tipit a dhe pika të djathta të shënuara me vlera të tipit b.

Këto nuk janë tipe nga biblioteka Alga. Në Alga nuk ka përfaqësim për grafet e dyfishta të paorientuara. Tipet i krijova kështu për qartësi.

Gjithashtu, do të na nevojiten funksione ndihmëse me këto nënshkrime:

-- Lista e fqinjëve të kësaj kulme.
neighbours :: Ord a => a -> Graph a -> [a]

-- Ndërtoni një graf bipartit nga grafi dhe funksioni, për secilën kulm
-- që jep aksionin e saj dhe shënimin në aksionin e ri, duke injoruar skajet konfliktuese.
toBipartiteWith :: (Ord a, Ord b, Ord c) => (a -> Either b c)
                                         -> Graph a
                                         -> Bigraph b c

-- Lista e kulmeve në graf
vertexList :: Ord a => Graph a -> [a]
Sinshtet e funksionit që do të shkruajmë duket kështu:

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

Nuk është e vështirë të vëresh se nëse gjatë procesit të kërkimit në thellësi gjejmë një skaj konfliktues, cikli çuditshëm ndodhet në krye të grimit të rekursisë. Kështu që, për ta rikuperuar atë, na duhet të prishim të gjitha në grimin e rekursisë deri në shfaqjen e parë të kulmës së fundit.

Ne do të zbatojmë kërkimin në thellësi, duke mbajtur një array asociativ të numrave të aksionit për secilën kulmë. Grimi i rekursisë do të mbahet automatikisht përmes implementimit të klasës Functor të monadës që kemi zgjedhur: thjesht do të duhet të vendosim të gjitha kulmet në rrugë në rezultatin që kthehet nga funksioni rekursiv.

Ideja ime e parë ishte të përdorja monadën Either, e cila në dukje realizon efektet që na nevojiten. Implementimi i parë që shkrova ishte shumë i afërt me këtë variant. Në të vërtetë, unë kisha pesë implementime të ndryshme në një moment, dhe përfundimisht u ndala në një tjetër.

NĂ« radhĂ« tĂ« parĂ«, na nevojitet tĂ« mbajmĂ« njĂ« array asociativ tĂ« identifikuesve tĂ« aksionit — ky Ă«shtĂ« diçka nĂ« lidhje me State. NĂ« radhĂ« tĂ« dytĂ«, na nevojitet tĂ« dimĂ« si tĂ« ndalemi nĂ« rast se zbulojmĂ« njĂ« konflikt. Kjo mund tĂ« jetĂ« ose Monad pĂ«r Either, ose MonadPlus pĂ«r Maybe. Dallimi kryesor Ă«shtĂ« se Either mund tĂ« kthejĂ« njĂ« vlerĂ« nĂ« rastin kur llogaritja nuk Ă«shtĂ« ndalur, ndĂ«rsa Maybe kthen nĂ« kĂ«tĂ« rast vetĂ«m informacion nĂ« lidhje me kĂ«tĂ«. Duke qenĂ« se nuk na nevojitet njĂ« vlerĂ« e veçantĂ« nĂ« rastin e suksesit (ajo Ă«shtĂ« tashmĂ« e ruajtur nĂ« State), ne zgjedhim Maybe. Dhe nĂ« momentin kur na nevojitet tĂ« kombinojmĂ« efektet e dy monadave, dalin transformatorĂ«t e monadave, tĂ« cilat nĂ« fakt kĂ«to efekte i kombinojnĂ«.

Pse e zgjodha një tip kaq të ndërlikuar? Dy arsye. Së pari, realizimi doli shumë i ngjashëm me të imperative. Së dyti, na nevojitet të manipulojmë me vlerën që kthehet në rast të konfliktit, kur kthehemi prapa nga rekursioni për të rikuperuar një cikël të çuditshëm, dhe kjo është shumë më e lehtë ta bëjmë në monadën Maybe.

Kështu, ne marrim një realizim të tillë.

{-# 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  a -> PartMonad a
        onEdge p v = do m  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  [a]
        oddCycle c = tail (dropWhile ((/=) last c) c)

Blloku where — Ă«shtĂ« thelbi i algoritmit. Do pĂ«rpiqem tĂ« shpjegoj se çfarĂ« ndodh brenda tij.

  • inVertex — Ă«shtĂ« pjesa e kĂ«rkimit nĂ« thellĂ«si, ku ne vizitojmĂ« njĂ« pikĂ« pĂ«r herĂ« tĂ« parĂ«. KĂ«tu i japim pikĂ«s numrin e pjesĂ«s dhe aktivizojmĂ« onEdge pĂ«r tĂ« gjithĂ« fqinjĂ«t. Gjithashtu, kjo Ă«shtĂ« vendi ku rikuperojmĂ« grumbullin e thirrjeve: nĂ«se msum ktheu njĂ« vlerĂ«, ne e lidhim atje pikĂ«n v.
  • onEdge — Ă«shtĂ« pjesa kur vizitojmĂ« skajet. Ajo thirret dy herĂ« pĂ«r çdo skaj. KĂ«tu kontrollojmĂ« nĂ«se maja nga ana tjetĂ«r Ă«shtĂ« vizituar dhe e vizitojmĂ« atĂ« nĂ«se nuk Ă«shtĂ«. NĂ«se Ă«shtĂ« vizituar, kontrollojmĂ« nĂ«se skaji Ă«shtĂ« konfliktual. NĂ«se Ă«shtĂ«, kthejmĂ« vlerĂ«n — majĂ«n e stack-ut tĂ« rekursivitetit, ku mĂ« pas do tĂ« ngjiten tĂ« gjitha majat e tjera gjatĂ« kthimit.
  • processVertex kontrollon pĂ«r çdo majĂ« nĂ«se Ă«shtĂ« vizituar dhe e nis inVertex nĂ« tĂ« nĂ«se nuk Ă«shtĂ«.
  • dfs nis processVertex nĂ« tĂ« gjitha majat.

Kjo është gjithçka.

Historia e fjalës INLINE

Fjala INLINE nuk ishte në implementimin e parë të algoritmit, ajo u shfaq më vonë. Kur përpiqesha të gjeja një implementim më të mirë, vura re se në disa grafe versioni pa INLINE funksiononte ndjeshëm më ngadalë. Duke pasur parasysh që semantikisht funksionet duhet të punojnë njësoj, kjo më befasoi shumë. Edhe më e çuditshme ishte që në një makinë tjetër me një version tjetër të GHC nuk kishte asnjë ndryshim të dukshëm.

Pas një javë të kaluar duke lexuar daljen e GHC Core, arrita të rregulloj problemin me një rresht me INLINE të qartë. Në një moment midis GHC 8.4.4 dhe GHC 8.6.5 optimizuesi ndaloi ta bëjë këtë automatikisht.

Nuk e prisja tĂ« hasja njĂ« kaos tĂ« tillĂ« nĂ« programimin me Haskell. MegjithatĂ«, optimizuesit megjithatĂ«, madje edhe nĂ« kohĂ«t tona, ndonjĂ«herĂ« bĂ«jnĂ« gabime dhe t'u japĂ«sh atyre sugjerime — Ă«shtĂ« detyra jonĂ«. PĂ«r shembull, kĂ«tu e dimĂ« qĂ« funksioni duhet tĂ« jetĂ« i inlinuar, sepse Ă«shtĂ« i inlinuar nĂ« versionin imperativ, dhe kjo Ă«shtĂ« arsyeja pĂ«r tĂ« dhĂ«nĂ« njĂ« sugjerim pĂ«r kompajlerin.

ÇfarĂ« ndodhi mĂ« pas?

Më pas realizova algoritmin e Hopcroft-Karpa me monada të tjera, dhe me këtë programi përfundoi.

Falë Google Summer of Code, fitova përvojë praktike në programimin funksional, që jo vetëm që më ndihmoi të kaloj në një praktikë në Jane Street verën tjetër (nuk jam i sigurt se sa e njohur është kjo vend për audiencën e ditur të Habra, por është një nga pak ku në verë mund të merresh me programimin funksional), por gjithashtu më prezantoi me botën e habitshme të aplikimit të kësaj paradigme në praktikë, e cila ndryshon ndjeshëm nga përvoja ime në gjuhët tradicionale.

Burimi: habr.com

Blini hosting tĂ« besueshĂ«m pĂ«r faqe interneti me mbrojtje nga DDoS, serverĂ« VPS VDS đŸ”„ Blini hosting tĂ« besueshĂ«m pĂ«r faqe interneti me mbrojtje nga DDoS, serverĂ« VPS VDS | ProHoster