Majira ya joto iliyopita nilishiriki Msimu wa Google wa Msimbo - mpango wa wanafunzi kutoka Google. Kila mwaka, waandaaji huchagua miradi kadhaa ya Open Source, pamoja na kutoka kwa mashirika yanayojulikana kama Boost.org и Msingi wa Linux. Google inawaalika wanafunzi kutoka kote ulimwenguni kufanya kazi kwenye miradi hii.

Kama mshiriki katika Majira ya joto ya Google ya Kanuni za 2019, nilifanya mradi ndani ya maktaba Mshahara na shirika Haskell.org, ambayo inakuza lugha ya Haskell - mojawapo ya lugha maarufu za programu za kazi. Alga ni maktaba ambayo inawakilisha aina salama uwakilishi wa grafu katika Haskell. Inatumika, kwa mfano, katika semantiki - maktaba ya Github ambayo huunda miti ya semantiki, kupiga simu na grafu za utegemezi kulingana na nambari na inaweza kuzilinganisha. Mradi wangu ulikuwa ni kuongeza uwakilishi salama wa aina kwa grafu na algoriti za uwakilishi huo.

Katika chapisho hili nitazungumza juu ya utekelezaji wangu wa algorithm ya kuangalia girafu kwa uwili huko Haskell. Ingawa algorithm ni moja ya msingi zaidi, kuitekeleza kwa uzuri katika mtindo wa kufanya kazi kulinichukua marudio kadhaa na kuhitaji kazi nyingi. Kama matokeo, nilikaa juu ya utekelezaji na vibadilishaji vya monad.

Kuhusu mimi mwenyewe

Jina langu ni Vasily Alferov, mimi ni mwanafunzi wa mwaka wa nne huko St. Petersburg HSE. Hapo awali kwenye blogi niliandika kuhusu mradi wangu kuhusu algorithms ya parameta и kuhusu safari ya ZuriHac. Sasa hivi niko kwenye internship Chuo Kikuu cha Bergen nchini Norway, ambapo ninafanyia kazi mbinu za kutatua tatizo hilo Orodha ya Rangi. Mambo yanayonivutia ni pamoja na kanuni za vigezo na utayarishaji wa utendaji kazi.

Kuhusu utekelezaji wa algorithm

utangulizi

Wanafunzi wanaoshiriki katika programu wanahimizwa sana kublogi. Walinipa jukwaa la blogi Majira ya joto ya Haskell. Makala hii ni tafsiri nakala, iliyoandikwa na mimi huko Julai kwa Kiingereza, na dibaji fupi.

Ombi la Kuvuta na nambari inayohusika inaweza kupatikana hapa.

Unaweza kusoma kuhusu matokeo ya kazi yangu (kwa Kiingereza) hapa.

Chapisho hili linadhania kuwa msomaji anafahamu dhana za kimsingi katika upangaji kazi, ingawa nitajaribu kukumbuka maneno yote yanayotumika wakati utakapofika.

Kuangalia grafu kwa uwili

Algorithm ya kuangalia grafu kwa uwili kwa kawaida hutolewa katika kozi ya algoriti kama mojawapo ya algorithms rahisi zaidi ya grafu. Wazo lake ni moja kwa moja: kwanza kwa namna fulani tunaweka wima katika sehemu ya kushoto au ya kulia, na wakati makali yanayopingana yanapatikana, tunasisitiza kwamba grafu sio pande mbili.

Maelezo kidogo zaidi: kwanza tunaweka vertex katika sehemu ya kushoto. Kwa wazi, majirani wote wa vertex hii wanapaswa kulala kwenye lobe sahihi. Zaidi ya hayo, majirani wote wa majirani wa vertex hii wanapaswa kulala katika lobe ya kushoto, na kadhalika. Tunaendelea kugawa hisa kwa wima mradi bado kuna wima katika sehemu iliyounganishwa ya kipeo tulichoanza nayo ambayo hatujawagawia majirani. Kisha tunarudia kitendo hiki kwa vipengele vyote vilivyounganishwa.

Ikiwa kuna makali kati ya vipeo vinavyoanguka kwenye kizigeu sawa, si vigumu kupata mzunguko usio wa kawaida kwenye grafu, ambayo inajulikana sana (na ni wazi kabisa) haiwezekani katika grafu ya pande mbili. Vinginevyo, tunayo kizigeu sahihi, ambayo inamaanisha kuwa grafu ni sehemu mbili.

Kwa kawaida, algorithm hii inatekelezwa kwa kutumia utafutaji wa kwanza au utafutaji wa kina kwanza. Katika lugha za lazima, utafutaji wa kina-kwanza kawaida hutumiwa kwa kuwa ni rahisi zaidi na hauhitaji miundo ya ziada ya data. Pia nilichagua utaftaji wa kina-kwanza kwani ni wa kitamaduni zaidi.

Kwa hivyo, tulikuja kwa mpango ufuatao. Tunapitia wima za grafu kwa utafutaji wa kina-kwanza na kuwapa hisa, kubadilisha nambari ya kushiriki tunaposonga kando. Ikiwa tutajaribu kugawa sehemu kwa vertex ambayo tayari ina sehemu iliyopewa, tunaweza kusema kwa usalama kwamba grafu sio pande mbili. Wakati wima zote zimepewa sehemu na tumeangalia kingo zote, tuna kizigeu kizuri.

Usafi wa mahesabu

Katika Haskell tunadhani kuwa mahesabu yote ni safi. Walakini, ikiwa hii ingekuwa kweli, hatungekuwa na njia ya kuchapisha chochote kwenye skrini. Hata kidogo, safi mahesabu ni ya uvivu sana kwamba hakuna hata mmoja safi sababu za kuhesabu kitu. Mahesabu yote yanayotokea kwenye programu yanalazimishwa kwa njia fulani "najisi" monad IO.

Monads ni njia ya kuwakilisha mahesabu madhara katika Haskell. Kuelezea jinsi wanavyofanya kazi ni zaidi ya upeo wa chapisho hili. Maelezo mazuri na ya wazi yanaweza kusomwa kwa Kiingereza hapa.

Hapa nataka kusema kwamba wakati monads zingine, kama vile IO, zinatekelezwa kupitia uchawi wa mkusanyaji, karibu zingine zote zinatekelezwa kwenye programu na mahesabu yote ndani yao ni safi.

Kuna athari nyingi na kila moja ina monad yake. Hii ni nadharia yenye nguvu sana na nzuri: monads zote hutekeleza kiolesura kimoja. Tutazungumza juu ya monads tatu zifuatazo:

Eidha ea ni hesabu inayorudisha thamani ya aina a au kuweka ubaguzi wa aina e. Tabia ya monad hii ni sawa na kushughulikia ubaguzi katika lugha za lazima: makosa yanaweza kupatikana au kupitishwa. Tofauti kuu ni kwamba monad inatekelezwa kimantiki katika maktaba ya kawaida huko Haskell, wakati lugha muhimu kawaida hutumia mifumo ya uendeshaji.
State sa ni hesabu ambayo inarudisha thamani ya aina a na inaweza kufikia hali inayoweza kubadilika ya aina s.
Labda a. Monad ya Labda inaelezea hesabu ambayo inaweza kuingiliwa wakati wowote kwa kurudisha Hakuna. Hata hivyo, tutazungumzia kuhusu utekelezaji wa darasa la MonadPlus kwa aina ya Labda, ambayo inaonyesha athari kinyume: ni hesabu ambayo inaweza kuingiliwa wakati wowote kwa kurejesha thamani maalum.

Utekelezaji wa algorithm

Tuna aina mbili za data, Graph a na Bigraph ab, ya kwanza ambayo inawakilisha grafu zilizo na vipeo vilivyoandikwa thamani za aina a, na ya pili inawakilisha grafu zenye pande mbili zenye vipeo vya upande wa kushoto vilivyoandikwa thamani za aina a na kulia. -wima za upande zilizo na alama za aina b.

Hizi sio aina kutoka kwa maktaba ya Alga. Mwani hauna uwakilishi wa grafu za sehemu mbili ambazo hazijaelekezwa. Nilifanya aina kama hii kwa uwazi.

Tutahitaji pia vitendaji vya msaidizi na saini zifuatazo:

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

Ni rahisi kuona kwamba ikiwa wakati wa utafutaji wa kina-kwanza tulipata ukingo unaokinzana, mzunguko usio wa kawaida upo juu ya mrundikano wa kujirudia. Kwa hivyo, ili kuirejesha, tunahitaji kukata kila kitu kutoka kwa safu ya kurudi tena hadi tukio la kwanza la vertex ya mwisho.

Tunatekeleza utafutaji wa kina wa kwanza kwa kudumisha safu shirikishi ya nambari za kushiriki kwa kila kipeo. Rafu ya urejeshaji itadumishwa kiotomatiki kupitia utekelezaji wa darasa la Kitendaji cha monad tuliyochagua: tutahitaji tu kuweka wima zote kutoka kwa njia hadi matokeo yaliyorejeshwa kutoka kwa chaguo la kukokotoa la kujirudia.

Wazo langu la kwanza lilikuwa kutumia Ama monad, ambayo inaonekana kutekeleza athari tunazohitaji. Utekelezaji wa kwanza nilioandika ulikuwa karibu sana na chaguo hili. Kwa kweli, nilikuwa na utekelezaji tano tofauti kwa wakati mmoja na mwishowe nikatulia kwenye nyingine.

Kwanza, tunahitaji kudumisha safu shirikishi ya vitambulishi vya kushiriki - hili ni jambo kuhusu Jimbo. Pili, tunahitaji kuwa na uwezo wa kuacha mzozo unapogunduliwa. Hii inaweza kuwa Monad kwa Ama, au MonadPlus kwa Labda. Tofauti kuu ni kwamba Ama inaweza kurudisha thamani ikiwa hesabu haijasimamishwa, na Labda inarudisha habari tu juu ya hii katika kesi hii. Kwa kuwa hatuhitaji thamani tofauti kwa mafanikio (tayari imehifadhiwa katika Jimbo), tunachagua Labda. Na kwa sasa tunapohitaji kuchanganya athari za monads mbili, zinatoka transfoma ya monad, ambayo inachanganya kwa usahihi athari hizi.

Kwa nini nilichagua aina ngumu kama hii? Sababu mbili. Kwanza, utekelezaji unageuka kuwa sawa na wa lazima. Pili, tunahitaji kuchezea thamani ya kurudi katika kesi ya mzozo wakati wa kurudi kutoka kwa kujirudia ili kurejesha kitanzi kisicho cha kawaida, ambacho ni rahisi zaidi kufanya katika Labda monad.

Hivyo tunapata utekelezaji huu.

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

Sehemu ya kuzuia ndio msingi wa algorithm. Nitajaribu kuelezea kile kinachotokea ndani yake.

inVertex ni sehemu ya utafutaji wa kina-kwanza ambapo tunatembelea vertex kwa mara ya kwanza. Hapa tunapeana nambari ya kushiriki kwenye vertex na kukimbia OneEdge kwa majirani wote. Hapa ndipo tunarejesha rundo la simu: ikiwa msum ilirudisha thamani, tunasukuma vertex v hapo.
OneEdge ni sehemu ambayo tunatembelea ukingo. Inaitwa mara mbili kwa kila makali. Hapa tunaangalia ikiwa vertex upande wa pili imetembelewa, na uitembelee ikiwa sio. Ikitembelewa, tunaangalia kama ukingo unakinzana. Ikiwa ndivyo, tunarudisha thamani - sehemu ya juu kabisa ya safu ya urejeshaji, ambapo wima zingine zote zitawekwa baada ya kurudi.
processVertex hukagua kila kipeo ikiwa imetembelewa na inaendesha inVertex juu yake ikiwa sivyo.
dfs huendesha processVertex kwenye wima zote.

Ni hayo tu.

Historia ya neno INLINE

Neno INLINE halikuwa katika utekelezaji wa kwanza wa algoriti; lilionekana baadaye. Nilipojaribu kupata utekelezaji bora, niligundua kuwa toleo lisilo la INLINE lilikuwa polepole sana kwenye baadhi ya grafu. Kwa kuzingatia kwamba kimantiki kazi zinapaswa kufanya kazi sawa, hii ilinishangaza sana. Hata mgeni, kwenye mashine nyingine yenye toleo tofauti la GHC hapakuwa na tofauti inayoonekana.

Baada ya kutumia wiki moja kusoma matokeo ya GHC Core, niliweza kurekebisha tatizo na mstari mmoja wa INLINE wazi. Wakati fulani kati ya GHC 8.4.4 na GHC 8.6.5 kiboreshaji kiliacha kufanya hivi peke yake.

Sikutarajia kukutana na uchafu kama huo katika programu ya Haskell. Walakini, hata leo, viboreshaji wakati mwingine hufanya makosa, na ni kazi yetu kuwapa vidokezo. Kwa mfano, hapa tunajua kwamba kipengele cha kukokotoa kinapaswa kuandikwa kwa mstari kwa sababu kimewekwa katika toleo la lazima, na hii ndiyo sababu ya kumpa mkusanyaji kidokezo.

Nini kilitokea baadaye?

Kisha nikatekeleza algorithm ya Hopcroft-Karp na monads nyingine, na huo ulikuwa mwisho wa programu.

Shukrani kwa Majira ya joto ya Google ya Kanuni, nilipata uzoefu wa vitendo katika upangaji programu, ambao haukunisaidia tu kupata taaluma katika Jane Street msimu uliofuata (sina uhakika jinsi mahali hapa panajulikana hata kati ya watazamaji wenye ujuzi wa Habr, lakini ni moja kati ya wachache ambapo unaweza majira ya joto kujihusisha na programu tendaji), lakini pia ilinitambulisha kwa ulimwengu mzuri wa kutumia dhana hii kwa vitendo, tofauti sana na uzoefu wangu katika lugha za kitamaduni.

Chanzo: mapenzi.com

GSoC 2019: Kukagua grafu kwa vibadilishi viwili vya sehemu mbili na monad