An samhradh seo caite ghlac mé páirt ann - clár do mhic léinn ó Google. Gach bliain, roghnaíonn na heagraithe roinnt tionscadal Foinse Oscailte, lena n-áirítear ó eagraíochtaí aitheanta mar и . Tugann Google cuireadh do mhic léinn ó gach cearn den domhan oibriú ar na tionscadail seo.
Mar rannpháirtí i Google Summer of Code 2019, rinne mé tionscadal laistigh den leabharlann leis an eagraíocht , atá ag forbairt na teanga Haskell - ceann de na teangacha ríomhchlárúcháin feidhme is cáiliúla. Is leabharlann é Alga a dhéanann ionadaíocht léiriú do ghraif i Haskell. Úsáidtear é, mar shampla, i — leabharlann Github a thógann crainn shéimeantacha, graif ghlaonna agus spleáchais bunaithe ar chód agus is féidir iad a chur i gcomparáid. Ba é an tionscadal a bhí agam ná léiriú cineál-sábháilte a chur leis do ghraif dhépháirteacha agus halgartaim don léiriú sin.
Sa phost seo beidh mé ag caint faoi mo chur i bhfeidhm algartam chun graf a sheiceáil le haghaidh départiteness i Haskell. Cé go bhfuil an t-algartam ar cheann de na cinn is bunúsaí, thóg sé roinnt atriallta orm é a chur i bhfeidhm go hálainn i stíl fheidhmiúil agus bhí go leor oibre ag teastáil. Mar thoradh air sin, shocraigh mé ar chur i bhfeidhm le trasfhoirmeoirí monad.
Ráiteas
Vasily Alferov is ainm dom, is mac léinn ceathrú bliana mé ag FSS St. Petersburg. Níos luaithe sa bhlag scríobh mé и . Faoi láthair tá mé ar intéirneacht ag san Iorua, áit a bhfuilim ag obair ar chur chuige i leith na faidhbe . I measc mo chuid spéise tá algartaim pharaiméadairithe agus ríomhchlárú feidhmiúil.
Maidir le cur i bhfeidhm an algartam
Réamhrá
Moltar go láidir do dhaltaí a ghlacann páirt sa chlár blagáil. Chuir siad ardán ar fáil dom don bhlag . Is aistriúchán é an t-alt seo , a scríobh mé ansin i mí Iúil i mBéarla, le réamhrá gairid.
Is féidir Iarratas Tarraingthe leis an gcód atá i gceist a fháil .
Is féidir léamh faoi thorthaí mo shaothair (i mBéarla) .
Glacann an post seo leis go bhfuil an léitheoir eolach ar na coincheapa bunúsacha i ríomhchlárú feidhme, cé go ndéanfaidh mé iarracht na téarmaí go léir a úsáidtear nuair a thagann an t-am a thabhairt chun cuimhne.
Ag seiceáil graif le haghaidh dépháirteachas
Is gnách go dtugtar algartam chun graf a sheiceáil le haghaidh déthaobhachta i gcúrsa ar halgartaim mar cheann de na halgartaim graf is simplí. Tá a smaoineamh simplí: ar dtús cuirimid rinn ar bhealach éigin sa sciar clé nó ar dheis, agus nuair a aimsítear imeall contrártha, dearbhaímid nach graf dépháirteach é an graf.
Beagán níos mó sonraí: ar dtús cuirimid roinnt rinn sa sciar clé. Ar ndóigh, caithfidh comharsana uile an rinn seo a bheith ina luí sa lobe ceart. Thairis sin, ní mór go mbeadh comharsana uile chomharsana an rinn seo ina luí sa lobe clé, agus mar sin de. Leanaimid de scaireanna a shannadh do rinn chomh fada agus atá rinn fós sa chomhpháirt nasctha den rinn ar thosaigh muid leis nach bhfuil comharsana sannta againn dóibh. Déanaimid an gníomh seo arís ansin maidir le gach comhpháirt nasctha.
Má tá imeall idir rinn a thiteann isteach sa dheighilt chéanna, níl sé deacair timthriall corr a fháil sa ghraf, rud a bhfuil eolas forleathan air (agus is léir go bhfuil sé dodhéanta) i ngraf dépháirteach. Seachas sin, tá deighilt cheart againn, rud a chiallaíonn go bhfuil an graf dépháirteach.
De ghnáth, cuirtear an algartam seo i bhfeidhm ag baint úsáide as nó . I dteangacha riachtanacha, is gnách go n-úsáidtear cuardach domhain-an chéad toisc go bhfuil sé beagán níos simplí agus nach dteastaíonn struchtúir sonraí breise uaidh. Roghnaigh mé freisin doimhneacht-an chéad cuardach mar go bhfuil sé níos traidisiúnta.
Mar sin, thángamar ar an scéim seo a leanas. Trasnaíonn muid rinn an ghraif trí úsáid a bhaint as cuardach doimhneacht-an chéad uair agus sannaimid scaireanna dóibh, ag athrú uimhir na scaire agus muid ag bogadh feadh an chiumhais. Má dhéanaimid iarracht sciar a shannadh do rinn a bhfuil sciar sannta cheana féin, is féidir linn a rá go sábháilte nach bhfuil an graf dépháirteach. Nuair a shanntar sciar do gach rinn agus d’fhéachamar ar na himill go léir, tá críochdheighilt mhaith againn.
Íonacht na n-áireamh
I Haskell glacaimid leis go bhfuil gach ríomh glan. Mar sin féin, dá mbeadh sé seo fíor, ní bheadh aon bhealach againn rud ar bith a phriontáil ar an scáileán. Ar chor ar bith, glan ríomhaireachtaí atá chomh leisciúil nach bhfuil ceann glan cúiseanna rud éigin a ríomh. Gach ríomhaireachtaí a tharlaíonn sa chlár tá iachall ar bhealach isteach "neamhghlan" monad IO.
Is bealach iad monaí chun ríomhaireachtaí a léiriú le éifeachtaí i Haskell. Tá míniú a thabhairt ar an gcaoi a n-oibríonn siad lasmuigh de scóip an phoist seo. Is féidir cur síos maith soiléir a léamh i mBéarla .
Anseo ba mhaith liom a chur in iúl, cé go gcuirtear roinnt monads, mar shampla IO, i bhfeidhm trí dhraíocht tiomsaitheora, go gcuirtear beagnach gach ceann eile i bhfeidhm i mbogearraí agus go bhfuil gach ríomh iontu íon.
Tá go leor éifeachtaí ann agus tá a monad féin ag gach ceann acu. Is teoiric an-láidir agus álainn í seo: cuireann gach monad an comhéadan céanna i bhfeidhm. Labhróimid faoi na trí monaidí seo a leanas:
- Is ríomh é ea a thugann luach chineál a ar ais nó a chaitheann eisceacht de chineál e. Tá iompar an monad seo an-chosúil le láimhseáil eisceachta i dteangacha ríthábhachtacha: is féidir earráidí a ghabháil nó a chur ar aghaidh. Is é an príomhdhifríocht ná go gcuirtear an monad i bhfeidhm go hiomlán go loighciúil sa leabharlann chaighdeánach i Haskell, agus is gnách go n-úsáideann teangacha éigeantacha meicníochtaí córais oibriúcháin.
- Is ríomh é State sa a thugann luach chineál a ar ais agus a bhfuil rochtain aige ar staid sho-shóite chineál s.
- B’fhéidir a. Cuireann an monad May in iúl ríomh ar féidir cur isteach air ag am ar bith trí Ní dhéanfaidh aon ní a thabhairt ar ais. Mar sin féin, beimid ag caint faoi chur i bhfeidhm rang MonadPlus don chineál B'fhéidir, a léiríonn an éifeacht os coinne: is ríomh é is féidir cur isteach ag am ar bith trí luach ar leith a thabhairt ar ais.
Cur i bhfeidhm an algartam
Tá dhá chineál sonraí againn, Graf a agus Bigraph ab, agus seasann an chéad cheann acu graif le rinn atá lipéadaithe le luachanna de chineál a, agus seasann an dara ceann le graif dépháirteacha le rinn ar thaobh na láimhe clé lipéadaithe le luachanna de chineál a agus ar dheis. -taobh rinn lipéadaithe le luachanna de chineál b.
Ní cineálacha iad seo ó leabharlann Alga. Níl aon léiriú ag Alga ar ghraif dépháirteacha neamhdhírithe. Rinne mé na cineálacha mar seo ar mhaithe le soiléireacht.
Beidh feidhmeanna cúntóra de dhíth orainn freisin leis na sínithe seo a leanas:
-- Список соседей данной вершины.
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)Is furasta a fheiceáil más rud é go bhfuaireamar imeall contrártha le linn an chéad chuardaigh doimhneachta, go luíonn an timthriall corr ar bharr an stoic athchúrsála. Mar sin, chun é a athbhunú, ní mór dúinn gach rud a ghearradh amach ón gcruach athfhillteach go dtí an chéad rud a tharla den rinn deiridh.
Cuirimid cuardach domhain-an-tosaigh i bhfeidhm trí raon comhthiomsaitheach d'uimhreacha scaireanna a choinneáil do gach rinn. Déanfar an stack athfhillteach a chothabháil go huathoibríoch trí rang Functor den monad atá roghnaithe againn a chur i bhfeidhm: ní bheidh orainn ach na rinn go léir a chur ón gcosán isteach sa toradh a chuirtear ar ais ón bhfeidhm athfhillteach.
Ba é an chéad smaoineamh a bhí agam ná an ceachtar monad a úsáid, rud is cosúil go gcuireann sé i bhfeidhm go díreach na héifeachtaí atá ag teastáil uainn. Bhí an chéad chur i bhfeidhm a scríobh mé an-ghar don rogha seo. Go deimhin, bhí cúig fheidhmiúchán éagsúla agam ag pointe amháin agus shocraigh mé ar cheann eile ar deireadh.
Gcéad dul síos, ní mór dúinn a choimeád ar bun le sraith comhthiomsaitheach d'aitheantóirí scaireanna - tá sé seo rud éigin faoi Stáit. Ar an dara dul síos, ní mór dúinn a bheith in ann stop a chur nuair a bhraitear coinbhleacht. Is féidir é seo a bheith Monad do Ceachtar, nó MonadPlus do B'fhéidir. Is é an príomh-difríocht ná gur féidir le Ceachtar luach a thabhairt ar ais mura bhfuil an ríomh stoptha, agus b'fhéidir nach dtugann ach faisnéis faoi seo sa chás seo. Ós rud é nach bhfuil luach ar leith ag teastáil uainn le haghaidh rathúlachta (tá sé stóráilte cheana féin sa Stát), roghnaíonn muid B'fhéidir. Agus i láthair na huaire nuair is gá dúinn a chur le chéile éifeachtaí dhá monads, a thagann siad amach , a chomhcheanglaíonn na héifeachtaí seo go beacht.
Cén fáth ar roghnaigh mé cineál den sórt sin casta? Dhá chúis. Ar an gcéad dul síos, is cosúil go bhfuil an cur i bhfeidhm an-chosúil leis an riachtanas. Ar an dara dul síos, ní mór dúinn an luach tuairisceáin a ionramháil i gcás coinbhleachta agus muid ag filleadh ar ais ó athchúrsáil chun an lúb corr a athbhunú, rud atá i bhfad níos éasca a dhéanamh sa B'fhéidir monad.
Mar sin faigheann muid an cur i bhfeidhm seo.
{-# 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)
An áit a bhfuil bloc mar chroílár an algartam. Déanfaidh mé iarracht a mhíniú cad atá ag tarlú taobh istigh de.
- Is é inVertex an chuid den chéad chuardach doimhneachta ina dtugaimid cuairt ar an rinn den chéad uair. Anseo sannaimid scairuimhir don rinn agus rithimid onEdge ar na comharsana go léir. Seo freisin an áit a ndéanaimid an chairn glaonna a athbhunú: má thug msum luach ar ais, brúimid rinn v ann.
- Is é onEdge an chuid ina dtugaimid cuairt ar an imeall. Tugtar faoi dhó ar gach imeall. Déanaimid seiceáil anseo an bhfuil cuairt tugtha ar an rinn ar an taobh eile, agus tabhair cuairt air mura bhfuil. Má thugtar cuairt air, déanaimid seiceáil an bhfuil an imeall ag teacht salach ar a chéile. Más ea, tugaimid an luach ar ais - barr an chruach athchúrsála, áit a gcuirfear gach rinn eile ar ais.
- Seiceálann processVertex do gach rinn cibé acu ar tugadh cuairt air agus ritheann sé inVertex air murar tugadh.
- ritheann dfs processVertex ar gach rinn.
Sin uile.
Stair an fhocail INLINE
Ní raibh an focal INLINE i gcéad chur i bhfeidhm an algartam; bhí sé le feiceáil níos déanaí. Nuair a rinne mé iarracht cur i bhfeidhm níos fearr a fháil, fuair mé amach go raibh an leagan neamh-INLÍNE go suntasach níos moille ar roinnt graif. Ag cur san áireamh gur cheart go n-oibreodh na feidhmeanna mar an gcéanna go semantach, chuir sé seo ionadh mór orm. Fiú strainséir, ar mheaisín eile le leagan difriúil de GHC ní raibh aon difríocht suntasach.
Tar éis seachtain a chaitheamh ag léamh aschur GHC Core, bhí mé in ann an fhadhb a réiteach le líne amháin INLINE follasach. Ag am éigin idir GHC 8.4.4 agus GHC 8.6.5 stop an optimizer é seo a dhéanamh leis féin.
Ní raibh mé ag súil go dtarlódh a leithéid de shalachar i gcláir Haskell. Mar sin féin, fiú sa lá atá inniu ann, uaireanta déanann optimizers botúin, agus is é an post atá againn leideanna a thabhairt dóibh. Mar shampla, tá a fhios againn anseo gur cheart an fheidhm a inlíneáil toisc go bhfuil sé inlíneáilte sa leagan riachtanach, agus is cúis é seo le leid a thabhairt don tiomsaitheoir.
Cad a tharla ina dhiaidh sin?
Ansin chuir mé algartam Hopcroft-Karp i bhfeidhm le monads eile, agus b'shin deireadh an chláir.
A bhuíochas le Google Summer of Code, fuair mé taithí phraiticiúil ar ríomhchlárú feidhmiúil, rud a chabhraigh liom ní hamháin intéirneacht a fháil ag Jane Street an samhradh dár gcionn (níl mé cinnte cé chomh maith is atá an áit seo fiú i measc lucht féachana eolach Habr, ach tá sé ar cheann den bheagán áit ar féidir leat an samhradh le bheith páirteach i gcláir fheidhmiúla), ach chuir sé isteach mé freisin ar an saol iontach a bhaineann leis an bparaidím seo a chur i bhfeidhm go praiticiúil, rud atá difriúil go mór le mo thaithí ar theangacha traidisiúnta.
Foinse: will.com