Xagaagii hore ayaan ka qayb qaatay - barnaamij loogu talagalay ardayda Google. Sannad kasta, qabanqaabiyayaashu waxay doortaan dhowr mashruuc oo Isha Furan, oo ay ku jiraan ururada caanka ah sida и . Google wuxuu ku martiqaadaa ardayda adduunka oo dhan inay ka shaqeeyaan mashaariicdan.
Ka qaybgale ahaan Google Summer Code 2019, waxaan ku sameeyay mashruuc gudaha maktabadda la ururka , kaas oo horumarinaya luqadda Haskell - mid ka mid ah luqadaha barnaamijka ugu caansan ee shaqeeya. Alga waa maktabad matalaysa matalaad garaafyada Haskell. Waxa loo isticmaalaa, tusaale ahaan, in - maktabad Github ah oo dhista geedo macno leh, wac iyo garaafyada ku tiirsanaanta ee ku salaysan koodka oo isbarbar dhigi kara. Mashruucaygu wuxuu ahaa inaan ku daro matalaad nooca-ammaan ah ee garaafyada laba geesoodka ah iyo algorithms ee matalaaddaas.
Maqaalkan waxaan kaga hadli doonaa hirgalinta algorithm ee hubinta garaafka labada dhinac ee Haskell. Inkasta oo algorithm-ka uu yahay mid ka mid ah kuwa aasaasiga ah, hirgelinta si qurux badan oo qaab shaqeyn ah ayaa igu qaadatay dhowr jeer oo u baahan shaqo aad u badan. Natiijo ahaan, waxaan degey hirgalinta transformers monad.
Naftayda ku saabsan
Magacaygu waa Vasily Alferov, waxaan ahay arday sannadka afraad wax ka barta St. Petersburg HSE. Horaantii blog-ka ayaan ku qoray и . Hadda waxaan ku jiraa internship Norway, halkaas oo aan ka shaqeynayo hababka loo wajahayo dhibaatada . Waxa aan danaynayo waxa ka mid ah algorithms-ka la jaan-qaadaya iyo barnaamij-samaynta.
Ku saabsan hirgelinta algorithm
Horudhac
Ardeyda ka qeybqaadaneysa barnaamijka waxaa si adag loogu dhiirigelinayaa in ay blog-ga ku qoraan. Waxay i siiyeen madal loogu talagalay blog-ga . Maqaalkani waa tarjumaad , oo aan halkaas ku qoray bishii Luulyo oo ku qornayd Ingiriis, oo leh hordhac gaaban.
Codsiga Jiid oo leh koodka su'aasha waa la heli karaa .
Waxaad ka akhrisan kartaa natiijada shaqadayda (Ingiriisi) .
Boostada waxaa loogu talagalay in lagu baro akhristaha fikradaha aasaasiga ah ee barnaamijyada shaqeynta, inkastoo aan isku dayi doono inaan dib u soo celiyo dhammaan ereyada la isticmaalo marka wakhtigu yimaado.
Hubinta garaafyada labada dhinac
Algorithm-ka lagu hubinayo garaafka labada dhinac waxaa inta badan lagu bixiyaa koorsada algorithms-yada sida mid ka mid ah algorithms garaafyada ugu fudud. Fikirkiisu waa toosan yahay: marka hore waxaynu si uun u dhignaa dacallada bidix ama midigta, marka la helo gees is khilaafaya, waxaanu caddaynaynaa in garaafku aanu ahayn laba dhinac.
Faahfaahin yar oo dheeraad ah: marka hore waxaan ku dhejineynaa qayb ka mid ah qaybta bidix. Sida iska cad, dhammaan derisyada vertex-kan waa in ay ku seexdaan laabka saxda ah. Dheeraad ah, dhammaan deriska deriska ah ee vertex this waa in ay seexdaan lafaha bidix, iyo wixii la mid ah. Waxaan sii wadeynaa ku wareejinta saamiyada geesaha ilaa iyo inta ay jiraan geeso ka mid ah qeybta isku xiran ee vertex-ka aan ku bilownay ee aanaan deris u dhiibin. Waxaan markaa ku celineynaa ficilkan dhammaan qaybaha ku xiran.
Haddii uu jiro cidhif u dhexeeya darafyada isla qayb ahaan ku dhaca, ma adka in garaafka laga helo wareeg aan caadi ahayn, kaas oo si weyn loo yaqaan (oo si cad) aan macquul ahayn garaafka laba-geesoodka ah. Haddii kale, waxaan leenahay qayb sax ah, taas oo macnaheedu yahay garaafku waa laba geesood.
Caadi ahaan, algorithm-kan waxaa lagu fuliyaa iyadoo la adeegsanayo ama . Luuqadaha lama huraanka ah, raadinta qoto-dheer ee koowaad waxaa badanaa loo adeegsadaa maadaama ay ka yara fududdahay oo uma baahna qaabab xog dheeraad ah. Waxaan sidoo kale doortay qoto-dheer raadinta koowaad maadaama ay tahay mid dhaqameed badan.
Markaa, waxaanu ku nimid qorshahan soo socda. Waxaan ka gudubnay geesaha garaafyada annaga oo adeegsanayna raadinta qoto-dheer ee koowaad waxaana ku wareejineynaa saamiyo iyaga, annaga oo beddeleynaa tirada saamiga marka aan u soconno cidhifka. Haddii aan isku dayno in aan ku meeleyno qayb ka mid ah jaangooyooyinka horeyba loo qoondeeyey, waxaan si ammaan ah u dhihi karnaa garaafku maaha mid laba geesood ah. Marka dhammaan cidhifyada loo qoondeeyo saami oo aan eegnay geesaha oo dhan, waxaan leenahay qayb wanaagsan.
Daahirnimada xisaabinta
Haskell waxaan u qaadaneynaa in dhammaan xisaabaadka ay yihiin nadiif ah. Si kastaba ha ahaatee, haddii ay tani run ahaan tahay kiiska, ma haysan lahayn si aan wax ugu daabacno shaashadda. Dhammaan, nadiif ah xisaabtu aad bay caajis u tahay oo midna ma jiro nadiif ah sababaha wax loo xisaabiyo. Dhammaan xisaabaadka ka dhacaya barnaamijka si uun baa lagu qasbay "aan nadiif ahayn" IO.
Monads waa hab lagu matalo xisaabinta saamaynta in Haskell. Sharaxaada sida ay u shaqeeyaan waa ka baxsan xadka qoraalkan. Sharaxaad wanaagsan oo cad ayaa lagu akhriyi karaa Ingiriis .
Halkan waxaan rabaa in aan tilmaamo in qaar ka mid ah monads, sida IO, lagu fuliyo iyada oo loo marayo sixirka compiler, ku dhawaad dhammaan kuwa kale waxaa lagu hirgeliyaa software iyo dhammaan xisaabinta iyaga ku jira waa saafi.
Waxaa jira saameyn badan oo mid kastaa wuxuu leeyahay monad u gaar ah. Tani waa aragti aad u xoog badan oo qurux badan: dhammaan monads waxay hirgeliyaan isla interface isku mid ah. Waxaan ka hadli doonaa seddexda monad ee soo socda:
- Ea ama ea waa xisaab celin soo celisa qiimaha nooca a ama tuurta marka laga reebo nooca e. Dhaqanka monad-kaani wuxuu aad ula mid yahay ka-reebista wax ka qabashada luqadaha muhiimka ah: khaladaadka waa la qabsan karaa ama waa la gudbin karaa. Farqiga ugu weyni waa in monad si buuxda loogu hirgeliyay maktabadda caadiga ah ee Haskell, halka luqadaha muhiimka ah ay inta badan isticmaalaan hababka nidaamka hawlgalka.
- State sa waa xisaab celin soo celisa qiimihii nooca a oo heli kara xaalad la bedeli karo ee nooca s.
- Malaha a. Malaha monad-ku wuxuu muujiyaa xisaabinta la joojin karo wakhti kasta isagoo soo celinaya waxba. Si kastaba ha ahaatee, waxaan ka hadli doonaa hirgelinta fasalka MonadPlus ee nooca Maybe, kaas oo muujinaya saameynta ka soo horjeeda: waa xisaabin la joojin karo wakhti kasta iyadoo la soo celinayo qiimo gaar ah.
Hirgelinta algorithm
Waxaan haynaa laba nooc oo xog ah, Graph a iyo Bigraph ab, kan ugu horreeya oo matalaya garaafyo leh geeso ay ku calaamadsan yihiin qiyamka nooca a, kan labaadna wuxuu matalaa garaafyo laba geesood ah oo leh geeso dhanka bidix ah oo lagu calaamadeeyay qiyamka nooca a iyo midig. - geesaha geesaha leh ee lagu calaamadeeyay qiyamka nooca b.
Kuwani maaha noocyada maktabadda Alga. Alga ma laha matalaad garaafyada laba geesoodka ah ee aan toosnayn. Waxaan u sameeyay noocyadan oo kale si aan u caddeeyo.
Waxaan sidoo kale u baahan doonaa hawlaha caawiye ee leh saxiixyada soo socda:
-- Список соседей данной вершины.
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)Way fududahay in la arko in haddii baadhitaankii ugu horreeyay ee qoto dheer aan helnay gees iska soo horjeeda, meertadu qallafsan tahay waxay dul saaran tahay xirmooyinka soo noqnoqda. Sidaa darteed, si loo soo celiyo, waxaan u baahannahay inaan ka jarno wax kasta oo ka soo baxa xirmooyinka soo noqnoqda ilaa dhacdada ugu horreysa ee cirifka ugu dambeeya.
Waxaan hirgelineynaa raadinta-koowaad annagoo ilaalineyna isku xirnaanta nambarada wadaagga ee vertex kasta. Xirmooyinka soo noqnoqda ayaa si toos ah loo ilaalin doonaa iyada oo loo marayo hirgelinta fasalka Functor ee monad aan dooranay: waxaan u baahan doonaa oo kaliya inaan dhigno dhammaan dariiqyada ka soo baxa waddada natiijada laga soo celiyay shaqada dib u soo celinta.
Fikradayda koowaad waxay ahayd inaan isticmaalo Monad Midkood, kaas oo u muuqda inuu si sax ah u hirgeliyo saameynta aan u baahanahay. Hirgelinta koowaad ee aan qoray ayaa aad ugu dhawaa doorashadan. Dhab ahaantii, waxaan lahaa shan fulin oo kala duwan hal mar oo ugu dambeyntii ku degay mid kale.
Marka hore, waxaan u baahannahay inaan ilaalino isku xirnaanta wadaagga aqoonsiga - tani waa wax ku saabsan Gobolka. Marka labaad, waxaan u baahanahay inaan awoodno inaan joojino marka khilaaf la ogaado. Tani waxay noqon kartaa Monad midkood, ama MonadPlus laga yaabee. Farqiga ugu weyni waa in midkood uu soo celin karo qiimaha haddii xisaabinta aan la joojin, lagana yaabo inay soo celiso macluumaadka arrintan ku saabsan oo keliya. Maadaama aanaan u baahnayn qiimo gooni ah oo guusha ah (horey ayaa loogu keydiyay Gobolka), waxaan dooraneynaa Malaha. Oo wakhtigan marka aan u baahan nahay in la isku daro saamaynta laba monads, ay soo baxaan , kuwaas oo si sax ah isugu dara saamayntan.
Maxaan u doortay nooc kakan? Laba sababood. Marka hore, hirgelintu waxay noqotaa mid la mid ah lama huraanka. Marka labaad, waxaan u baahanahay inaan wax ka bedelno qiimaha soo laabashada haddii ay dhacdo isku dhac markaan ka soo laabano soo noqnoqoshada si aan u soo celinno loop-kii aan fiicneyn, taas oo aad u sahlan in lagu sameeyo monad-ka Maybe.
Sidaa darteed waxaan ku helnaa hirgelintan.
{-# 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)
Meesha block waa xudunta algorithm. Waxaan isku dayi doonaa inaan sharaxo waxa ka dhacaya gudaha.
- inVertex waa qayb ka mid ah raadinta qoto-dheer ee ugu horreysa halkaas oo aan booqanno vertex markii ugu horeysay. Halkan waxa aanu ku meelayna nambar wadaag xaga dambe oo aanu wadno onEdge dhamaan deriska. Tani sidoo kale waa halka aan ku soo celineyno xirmada wicitaanka: haddii msum soo celiyo qiime, waxaan riixeynaa vertex v halkaas.
- onEdge waa qaybta aan booqano cidhifka. Waxaa loo yaqaan laba jeer gees kasta. Halkan waxaan ku hubineynaa in cirifka dhinaca kale la booqday, oo booqo haddii kale. Haddii nala soo booqdo, waxaanu hubinaa in cidhifku is khilaafayo iyo in kale. Haddii ay sidaas tahay, waxaan soo celineynaa qiimaha - meesha ugu sareysa ee xirmooyinka soo noqnoqda, halkaas oo dhammaan geesaha kale la dhigi doono marka la soo celiyo.
- ProcessVertex wuxuu eegayaa dulle kasta in la booqday iyo in kale.
- dfs waxay ku socodsiisaa nidaamkaVertex dhammaan darafyada.
Waa intaas.
Taariikhda erayga INLINE
Erayga INLINE kuma jirin dhaqan gelinta ugu horraysa ee algorithmamka; mar dambe ayay soo muuqatay. Markii aan isku dayay inaan helo hirgalin ka wanaagsan, waxaan ogaaday in nooca aan INLINE-ka ahayn uu si muuqata uga gaabiyay garaafyada qaar. Iyadoo la tixgelinayo in macno ahaan hawluhu ay si isku mid ah u shaqeeyaan, tani aad ayay iiga yaabisay. Xitaa qariib, mishiin kale oo leh nooc ka duwan GHC ma jirin farqi muuqda oo muuqda.
Ka dib markaan qaatay usbuuc akhrinta wax soo saarka GHC Core, waxaan awooday inaan dhibaatada ku hagaajiyo hal xariiq oo INLINE ah oo cad. Mar ka mid ah inta u dhaxaysa GHC 8.4.4 iyo GHC 8.6.5 optimizer-ka ayaa joojiyay inuu kan iskii u sameeyo.
Maan fileyn inaan la kulmo wasakhdaas oo kale barnaamijka Haskell. Si kastaba ha noqotee, xitaa maanta, wanaajiyayaashu waxay mararka qaarkood sameeyaan khaladaad, waana shaqadeena inaan siino tilmaamo. Tusaale ahaan, halkan waxaan ku ognahay in shaqada ay tahay in lagu dhejiyo sababtoo ah waxay ku dhex jirtaa nooca lama huraanka ah, tani waa sababta loo siinayo soo-sameeyaha.
Maxaa dhacay kadib?
Kadibna waxaan hirgeliyay Hopcroft-Karp algorithm oo leh monads kale, taasina waxay ahayd dhamaadka barnaamijka.
Thanks to Google Summer Code of Code, waxaan kasbaday waayo-aragnimo wax ku ool ah oo ku saabsan barnaamijyada shaqeynta, taas oo aan kaliya ka caawinin in aan tababar ku qaato Jane Street xagaaga soo socda (Ma hubo sida loo yaqaan meeshan xitaa ka mid ah dhagaystayaasha aqoonta Habr, laakiin waa mid. oo ka mid ah kuwa yar oo aad kuleyli karto si aad uga qaybgasho barnaamij-samaynta), laakiin sidoo kale waxay ii soo bandhigtay adduunka cajiibka ah ee ku-dhaqanka hab-dhaqankan, oo aad uga duwan waayo-aragnimadayda luqadaha dhaqanka.
Source: www.habr.com