Lokacin rani na baya na shiga ciki - shirin ga dalibai daga Google. Kowace shekara, masu shirya suna zaɓar ayyukan Buɗewa da yawa, gami da daga sanannun ƙungiyoyi kamar и . Google yana gayyatar ɗalibai daga ko'ina cikin duniya don yin aiki akan waɗannan ayyukan.
A matsayina na ɗan takara a Google Summer of Code 2019, Na yi wani aiki a cikin ɗakin karatu tare da kungiyar , wanda ke haɓaka harshen Haskell - ɗaya daga cikin shahararrun harsunan shirye-shiryen aiki. Alga ɗakin karatu ne wanda ke wakiltar wakilci ga jadawali a Haskell. Ana amfani da shi, alal misali, a cikin - Laburaren Github wanda ke gina bishiyar tatsuniyoyi, kira da zane-zanen dogaro bisa lambobi kuma yana iya kwatanta su. Aikina shine ƙara nau'in amintaccen wakilci don jadawali biyu da algorithms don wakilcin.
A cikin wannan sakon zan yi magana game da aiwatar da algorithm na duba jadawali don rabuwa a Haskell. Ko da yake algorithm yana ɗaya daga cikin mafi mahimmanci, aiwatar da shi da kyau a cikin salon aiki ya ɗauki ni matakai da yawa kuma yana buƙatar aiki mai yawa. A sakamakon haka, na zauna a kan aiwatarwa tare da monad transformers.
Game da ni
Sunana Vasily Alferov, Ni ɗalibi ne mai shekara huɗu a St. Petersburg HSE. Tun da farko a cikin blog na rubuta и . A yanzu haka ina kan aikin horarwa a a Norway, inda nake aiki kan hanyoyin magance matsalar . Abubuwan da nake da sha'awa sun haɗa da madaidaitan algorithms da shirye-shirye masu aiki.
Game da aiwatar da algorithm
Magana
Daliban da ke shiga cikin shirin suna ƙarfafawa sosai don yin rubutun ra'ayin kanka a yanar gizo. Sun ba ni dandali don blog . Wannan labarin fassarar ce , wanda na rubuta a can a watan Yuli da Turanci, tare da gajeren gabatarwa.
Ana iya samun buƙatun ja tare da lambar da ake tambaya .
Kuna iya karanta game da sakamakon aikina (a Turanci) .
An yi niyya ne don fahimtar da mai karatu tare da mahimman ra'ayoyi a cikin shirye-shiryen aiki, kodayake zan yi ƙoƙarin tunawa da duk kalmomin da aka yi amfani da su idan lokaci ya yi.
Duba jadawalai don haɗin kai
Algorithm don duba jadawali don nuna bambancin ra'ayi yawanci ana ba da shi a cikin kwas akan algorithms azaman ɗayan mafi sauƙin jadawali algorithms. Ra'ayinsa mai sauƙi ne: da farko za mu sanya maƙasudi a hannun hagu ko dama, kuma idan aka sami gefen da ya saba wa juna, sai mu tabbatar da cewa jadawali ba ya bambanta.
Dalla-dalla kadan: da farko mun sanya wasu juzu'i a cikin hannun hagu. Babu shakka, duk maƙwabta na wannan vertex dole ne su kwanta a cikin lobe mai kyau. Bugu da ari, duk maƙwabta na maƙwabta na wannan vertex dole ne su kwanta a cikin hagu na hagu, da sauransu. Muna ci gaba da sanya hannun jari zuwa gaɓoɓi muddin har yanzu akwai ɗimbin ɗimbin ɗimbin ɗimbin ɗimbin ɗigon da muka fara da wanda ba mu sanya maƙwabta ba. Sa'an nan kuma mu maimaita wannan aikin don duk abubuwan da aka haɗa.
Idan akwai gefe tsakanin madaidaitan da suka fada cikin bangare guda, ba shi da wahala a sami wani yanayi mara kyau a cikin jadawali, wanda sananne ne (kuma a fili) ba zai yiwu ba a cikin jadawali bipartite. In ba haka ba, muna da daidaitaccen bangare, wanda ke nufin jadawali bipartite ne.
Yawanci, ana aiwatar da wannan algorithm ta amfani da shi ko . A cikin yaruka masu mahimmanci, bincike-zurfin farko yawanci ana amfani da shi saboda yana da ɗan sauƙi kuma baya buƙatar ƙarin tsarin bayanai. Na kuma zaɓi bincike na farko mai zurfi kamar yadda ya fi al'ada.
Don haka, mun zo ga makirci mai zuwa. Muna ratsa madaidaicin jadawali ta amfani da bincike-zurfin farko da kuma sanya hannun jari zuwa gare su, muna canza adadin rabon yayin da muke motsawa tare da gefen. Idan muka yi ƙoƙari mu sanya rabon ga wani juzu'in da aka riga aka ba da rabo, za mu iya aminta da cewa jadawali baya ɓangarori biyu. Lokacin da aka ba da rabon duka gabaɗaya kuma mun kalli dukkan gefuna, muna da rabo mai kyau.
Tsaftar lissafi
A cikin Haskell muna ɗauka cewa duk lissafin su ne mai tsabta. Koyaya, idan da gaske haka lamarin yake, da bamu da hanyar buga komai akan allo. Ko kadan, mai tsabta lissafi yayi kasala da babu daya mai tsabta dalilai na lissafin wani abu. Duk lissafin da ke faruwa a cikin shirin an tilasta su ko ta yaya "mara tsarki" ina IO.
Monads wata hanya ce ta wakiltar lissafi tare da tasiri in Haskell. Bayyana yadda suke aiki ya wuce iyakar wannan sakon. Za a iya karanta kwatanci mai kyau kuma bayyananne cikin Turanci .
Anan ina so in nuna cewa yayin da ake aiwatar da wasu monads, irin su IO, ta hanyar sihirin compiler, kusan sauran ana aiwatar da su a cikin software kuma duk lissafin da ke cikin su tsarkakakku ne.
Akwai tasiri da yawa kuma kowanne yana da nasa mond. Wannan ka'ida ce mai ƙarfi kuma kyakkyawa: duk monads suna aiwatar da ƙa'idar iri ɗaya. Za mu yi magana game da monads guda uku masu zuwa:
- Ko dai ea lissafi ne da ke mayar da kimar nau'in a ko kuma ya jefa ban da nau'in e. Halin wannan monad yayi kama da keɓantacce a cikin yaruka masu mahimmanci: ana iya kama ko wuce kurakurai. Babban bambanci shi ne cewa an aiwatar da monad gaba ɗaya cikin ma'ana a cikin daidaitaccen ɗakin karatu a Haskell, yayin da yaruka masu mahimmanci galibi suna amfani da hanyoyin tsarin aiki.
- State sa lissafi ne da ke dawo da ƙimar nau'in a kuma yana da damar zuwa yanayin nau'in s mai canzawa.
- Wataƙila a. The Maybe monad yana bayyana lissafin lissafi wanda za'a iya katse shi a kowane lokaci ta hanyar dawo da Komai. Duk da haka, za mu yi magana game da aiwatar da kundin MonadPlus don nau'in Maybe, wanda ke nuna kishiyar sakamako: ƙididdigewa ne wanda za'a iya katsewa a kowane lokaci ta hanyar mayar da takamaiman ƙima.
Aiwatar da algorithm
Muna da nau'ikan bayanai guda biyu, Graph a da Bigraph ab, na farko wanda ke wakiltar jadawalai tare da lakabi da ƙimar nau'in a, na biyu kuma yana wakiltar zane-zane bipartite tare da gefen hagu masu lakabi da ƙimar nau'in a da dama. - gefen gefen da aka lakafta tare da ƙimar nau'in b.
Waɗannan ba nau'ikan ba ne daga ɗakin karatu na Alga. Alga bashi da wakilci don jadawali biyu marasa jagora. Na yi nau'ikan irin wannan don tsabta.
Hakanan za mu buƙaci ayyukan mataimaka tare da sa hannu masu zuwa:
-- Список соседей данной вершины.
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)Yana da sauƙi a ga cewa idan a cikin zurfin-bincike na farko mun sami gefe mai cin karo da juna, zagayowar da ba ta dace ba ta ta'allaka ne a saman tarin maimaitawa. Don haka, don mayar da shi, muna buƙatar yanke duk abin da ke tattare da maimaitawa har zuwa farkon abin da ya faru na ƙarshen ƙarshen.
Muna aiwatar da bincike-bincike na farko ta hanyar kiyaye ɗimbin lambobi masu alaƙa ga kowane juzu'i. Za a kiyaye tari mai maimaitawa ta atomatik ta hanyar aiwatar da ajin Functor na monad da muka zaɓa: za mu buƙaci kawai sanya duk ƙarshen hanya zuwa sakamakon da aka dawo daga aikin maimaitawa.
Tunanina na farko shine in yi amfani da ko dai monad, wanda da alama yana aiwatar da ainihin tasirin da muke buƙata. Farkon aiwatarwa da na rubuta ya kasance kusa da wannan zaɓi. A gaskiya ma, ina da aiwatarwa daban-daban guda biyar a lokaci guda kuma a ƙarshe na daidaita akan wani.
Na farko, muna bukatar mu kula da ɗimbin abubuwan haɗin haɗin gwiwa - wannan wani abu ne game da Jiha. Na biyu, muna bukatar mu iya dakatarwa lokacin da aka gano rikici. Wannan na iya zama ko dai Monad don Ko dai, ko MonadPlus don Watakila. Babban bambanci shine ko dai zai iya dawo da ƙima idan ba a dakatar da lissafin ba, kuma wataƙila ya dawo da bayanai kawai game da wannan a cikin wannan yanayin. Tun da ba mu buƙatar ƙima daban don nasara (an riga an adana shi a Jiha), mun zaɓi Wataƙila. Kuma a lokacin da muke buƙatar haɗa tasirin monadi biyu, suna fitowa , wanda daidai hada waɗannan tasirin.
Me yasa na zabi irin wannan hadadden nau'in? Dalilai biyu. Na farko, aiwatarwa ya zama kama da na wajibi. Na biyu, muna buƙatar yin amfani da ƙimar dawowa idan akwai rikici lokacin dawowa daga sake dawowa don dawo da madaidaicin madauki, wanda ya fi sauƙi a yi a cikin Ƙila monad.
Ta haka muke samun wannan aiwatarwa.
{-# 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)
Inda toshe shine ginshiƙi na algorithm. Zan yi ƙoƙari in bayyana abin da ke faruwa a ciki.
- inVertex shine ɓangaren bincike na farko-zurfin inda muka ziyarci ƙarshen a karon farko. Anan muna sanya lambar rabo zuwa ga bayanta kuma muna gudanar da onEdge akan duk maƙwabta. Wannan kuma shine inda muke mayar da tarin kira: idan msum ya dawo da ƙima, muna tura vertex v can.
- onEdge shine bangaren da muke ziyartar gefen. Ana kiran shi sau biyu don kowane gefe. Anan zamu duba idan an ziyarci gefen gefen gefe, kuma mu ziyarce shi idan ba haka ba. Idan an ziyarta, muna duba ko gefen yana cin karo da juna. Idan haka ne, za mu mayar da darajar - ainihin saman tari mai maimaitawa, inda za a sanya duk sauran madaidaicin bayan dawowa.
- ProcessVertex yana bincika kowane juzu'in ko an ziyartan shi kuma yana aiki cikinVertex akan sa idan ba haka ba.
- dfs yana gudanar da tsariVertex akan kowane lungu.
Shi ke nan.
Tarihin kalmar INLINE
Kalmar INLINE ba ta kasance a farkon aiwatar da algorithm ba; ta bayyana daga baya. Lokacin da na yi ƙoƙarin samun ingantaccen aiwatarwa, na gano cewa sigar da ba ta INLINE ba ta yi hankali a hankali akan wasu jadawali. Ganin cewa a zahiri ayyukan yakamata suyi aiki iri ɗaya, wannan ya bani mamaki sosai. Ko da baƙo, akan wata na'ura mai nau'in GHC daban-daban babu wani bambanci mai ban mamaki.
Bayan shafe mako guda ina karanta fitowar GHC Core, na sami damar gyara matsalar tare da layi ɗaya na fayyace INLINE. A wani lokaci tsakanin GHC 8.4.4 da GHC 8.6.5 mai ingantawa ya daina yin wannan da kansa.
Ban yi tsammanin haduwa da irin wannan datti a cikin shirye-shiryen Haskell ba. Duk da haka, har ma a yau, masu ingantawa wasu lokuta suna yin kuskure, kuma aikinmu ne mu ba su alamu. Misali, a nan mun san cewa aikin ya kamata a sanya shi cikin layi saboda an sanya shi cikin sigar dole, kuma wannan dalili ne na ba wa mai tarawa alama.
Me ya faru kuma?
Sannan na aiwatar da Hopcroft-Karp algorithm tare da sauran monads, kuma wannan shine ƙarshen shirin.
Godiya ga Google Summer of Code, na sami gogewa mai amfani a cikin shirye-shirye masu aiki, wanda ba wai kawai ya taimaka mini samun horon horo a titin Jane ba a lokacin rani mai zuwa (Ban tabbata yadda sanannen wannan wurin yake ba har ma tsakanin masu sauraron Habr, amma ɗaya ne. daga cikin 'yan kaɗan inda za ku iya lokacin rani don shiga cikin shirye-shirye na aiki), amma kuma sun gabatar da ni ga duniyar ban mamaki na yin amfani da wannan tsari a aikace, wanda ya bambanta da kwarewata a cikin harsunan gargajiya.
source: www.habr.com