Lub caij ntuj sov dhau los kuv tau koom nrog - ib qho program rau cov tub ntxhais kawm los ntawm Google. Txhua xyoo, cov koom haum xaiv ntau qhov Open Source project, suav nrog los ntawm cov koom haum zoo li no и . Google caw cov tub ntxhais kawm thoob plaws ntiaj teb los ua haujlwm ntawm cov haujlwm no.
Raws li ib tus neeg koom nrog Google Lub Caij Ntuj Sov ntawm Code 2019, kuv tau ua ib qhov project hauv lub tsev qiv ntawv nrog lub koom haum , uas yog tsim cov lus Haskell - ib qho ntawm cov npe nrov tshaj plaws hauv kev ua haujlwm. Alga yog lub tsev qiv ntawv uas sawv cev sawv cev rau cov duab hauv Haskell. Nws yog siv, piv txwv li, hauv - ib lub tsev qiv ntawv Github uas tsim cov ntoo semantic, hu xov tooj thiab cov duab kos raws li cov cai thiab tuaj yeem sib piv lawv. Kuv qhov project yog ntxiv ib hom kev nyab xeeb sawv cev rau bipartite graphs thiab algorithms rau qhov sawv cev.
Hauv tsab xov xwm no kuv yuav tham txog kuv qhov kev siv ntawm ib qho algorithm rau kev tshuaj xyuas daim duab rau kev sib koom tes hauv Haskell. Txawm hais tias lub algorithm yog ib qho tseem ceeb tshaj plaws, kev siv nws zoo nkauj hauv kev ua haujlwm tau coj kuv ntau qhov kev hloov pauv thiab yuav tsum tau ua haujlwm ntau heev. Raws li qhov tshwm sim, kuv tau txiav txim siab rau kev siv nrog monad transformers.
Txog kuv tus kheej
Kuv lub npe yog Vasily Alferov, Kuv yog ib tug menyuam kawm ntawv plaub xyoos ntawm St. Petersburg HSE. Ua ntej hauv blog kuv tau sau и . Tam sim no kuv nyob rau hauv internship ntawm nyob rau hauv Norway, qhov chaw uas kuv tab tom ua haujlwm rau txoj hauv kev rau qhov teeb meem . Kuv qhov kev txaus siab suav nrog parameterized algorithms thiab kev ua haujlwm ua haujlwm.
Hais txog kev siv cov algorithm
Lus Qhia Tshab
Cov tub ntxhais kawm koom nrog hauv qhov kev zov me nyuam tau txhawb siab rau blog. Lawv muab kuv lub platform rau blog . Kab lus no yog kev txhais lus , sau los ntawm kuv nyob rau lub Xya hli ntuj ua lus Askiv, nrog ib tug luv luv preface.
Rub Thov nrog tus lej hauv nqe lus nug tuaj yeem pom .
Koj tuaj yeem nyeem txog cov txiaj ntsig ntawm kuv txoj haujlwm (ua lus Askiv) .
Cov ntawv tshaj tawm no yog tsim los ua kom paub cov neeg nyeem nrog cov ntsiab lus tseem ceeb hauv kev ua haujlwm ua haujlwm, txawm hais tias kuv yuav sim rov qab txhua cov lus siv thaum lub sijhawm los txog.
Tshawb xyuas graphs rau bipartiteness
Ib qho algorithm rau kev kuaj ib daim duab rau bipartiteness feem ntau yog muab nyob rau hauv ib chav kawm ntawm algorithms raws li ib qho ntawm qhov yooj yim tshaj plaws graph algorithms. Nws lub tswv yim yog ncaj nraim: ua ntej peb muab cov vertices nyob rau sab laug lossis sab xis, thiab thaum pom qhov tsis sib haum xeeb, peb lees tias daim duab tsis yog bipartite.
Ib qho ntxiv me ntsis: ua ntej peb muab qee qhov vertex nyob rau sab laug qhia. Obviously, tag nrho cov neeg nyob ze ntawm no vertex yuav tsum pw nyob rau hauv txoj cai lobe. Tsis tas li ntawd, tag nrho cov neeg nyob ze ntawm cov neeg nyob ze ntawm lub vertex no yuav tsum pw nyob rau sab laug lobe, thiab lwm yam. Peb txuas ntxiv muab faib rau vertices tsuav yog tseem muaj cov vertices nyob rau hauv qhov txuas txuas ntawm lub vertex peb pib nrog qhov peb tsis tau muab cov neeg nyob ze rau. Peb mam li rov ua qhov kev txiav txim no rau txhua qhov txuas txuas.
Yog hais tias muaj ib qho ntug ntawm vertices uas poob rau hauv tib qhov kev faib tawm, nws tsis yog qhov nyuaj los nrhiav lub voj voog khib hauv daim duab, uas paub dav dav (thiab pom tseeb) tsis yooj yim sua hauv daim duab bipartite. Txwv tsis pub, peb muaj qhov muab faib kom raug, uas txhais tau hais tias daim duab yog bipartite.
Feem ntau, qhov algorithm no yog siv los siv los yog . Hauv cov lus tseem ceeb, kev tshawb nrhiav qhov tob yog feem ntau yog siv vim nws yooj yim me ntsis thiab tsis xav tau cov ntaub ntawv ntxiv. Kuv kuj tau xaiv qhov tob-thawj kev tshawb fawb raws li nws yog ib txwm muaj.
Yog li, peb tuaj rau cov txheej txheem hauv qab no. Peb hla lub vertices ntawm daim duab siv qhov tob-thawj tshawb nrhiav thiab muab faib rau lawv, hloov tus naj npawb ntawm qhov sib koom thaum peb txav mus raws ntug. Yog hais tias peb sim muab ib qho kev qhia rau ib qho vertex uas twb muaj ib qho kev qhia, peb tuaj yeem hais tau tias daim duab tsis yog bipartite. Lub sijhawm tag nrho cov vertices raug muab faib thiab peb tau saib tag nrho cov npoo, peb muaj kev faib zoo.
Purity ntawm kev suav
Hauv Haskell peb xav tias txhua qhov kev suav yog huv si. Txawm li cas los xij, yog tias qhov no yog qhov tseeb tiag, peb yuav tsis muaj txoj hauv kev los luam tawm dab tsi rau qhov screen. Txhua yam, huv si xam lazy ces tsis muaj ib tug huv si yog vim li cas rau xam ib yam dab tsi. Txhua qhov kev suav uas tshwm sim hauv qhov kev zov me nyuam yog qee qhov yuam kev "tsis huv" mav IO.
Monads yog ib txoj hauv kev los sawv cev rau kev suav nrog teebmeem hauv Haskell. Piav seb lawv ua haujlwm li cas dhau ntawm qhov kev tshaj tawm no. Cov lus piav qhia zoo thiab meej tuaj yeem nyeem ua lus Askiv .
Ntawm no kuv xav taw qhia tias thaum qee qhov monads, xws li IO, tau siv los ntawm kev sau cov khawv koob, yuav luag tag nrho lwm tus yog siv hauv software thiab txhua qhov kev suav hauv lawv yog cov ntshiab.
Muaj ntau qhov teebmeem thiab txhua tus muaj nws tus kheej monad. Qhov no yog qhov kev xav zoo heev thiab zoo nkauj: txhua tus monads siv tib lub interface. Peb yuav tham txog peb monads hauv qab no:
- Ob qho e a yog ib qho kev suav uas xa rov qab tus nqi ntawm hom a lossis cuam tshuam qhov kev zam ntawm hom e. Tus cwj pwm ntawm no monad yog heev zoo ib yam li tshwj xeeb tuav nyob rau hauv cov lus tseem ceeb: yuam kev yuav ntes tau los yog dhau mus. Qhov sib txawv tseem ceeb yog tias monad tau ua tiav tag nrho hauv cov tsev qiv ntawv tus qauv hauv Haskell, thaum cov lus tseem ceeb feem ntau siv cov txheej txheem kev ua haujlwm.
- Lub xeev s yog ib qho kev suav uas xa rov qab tus nqi ntawm hom a thiab muaj kev nkag mus rau lub xeev ntawm hom s.
- Tej zaum ib. Tej zaum monad qhia txog kev suav uas tuaj yeem cuam tshuam txhua lub sijhawm los ntawm kev xa rov qab Tsis muaj dab tsi. Txawm li cas los xij, peb yuav tham txog qhov kev siv ntawm MonadPlus chav kawm rau yam Tej zaum, uas qhia txog qhov cuam tshuam ntawm qhov sib txawv: nws yog kev suav uas tuaj yeem cuam tshuam txhua lub sijhawm los ntawm kev xa rov qab tus nqi tshwj xeeb.
Kev siv cov algorithm
Peb muaj ob hom ntaub ntawv, Graph a thiab Bigraph a b, thawj qhov uas sawv cev rau cov duab nrog vertices sau nrog qhov tseem ceeb ntawm hom a, thiab qhov thib ob yog sawv cev rau cov duab bipartite nrog rau sab laug-sab vertices sau nrog qhov tseem ceeb ntawm hom a thiab sab xis. -side vertices sau nrog qhov tseem ceeb ntawm hom b.
Cov no tsis yog hom los ntawm lub tsev qiv ntawv Alga. Alga tsis muaj tus sawv cev rau cov duab bipartite uas tsis muaj kev taw qhia. Kuv ua cov hom zoo li no kom pom tseeb.
Peb tseem yuav xav tau kev pab cuam nrog cov npe hauv qab no:
-- Список соседей данной вершины.
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)Nws yog ib qho yooj yim kom pom tias yog thaum lub sij hawm qhov tob-thawj kev tshawb fawb peb pom ib tug tsis sib haum xeeb ntug, lub khib lub voj voog nyob rau sab saum toj ntawm cov recursion pawg. Yog li, txhawm rau kho nws, peb yuav tsum tau txiav tawm txhua yam los ntawm pawg recursion mus rau thawj qhov tshwm sim ntawm qhov kawg vertex.
Peb siv qhov tob-thawj kev tshawb fawb los ntawm kev tswj hwm kev sib koom ua ke ntawm cov lej sib koom rau txhua qhov vertex. Cov pawg recursion yuav cia li khaws cia los ntawm kev siv ntawm Functor chav kawm ntawm lub monad peb tau xaiv: peb tsuas yog yuav tsum tau muab tag nrho cov vertices los ntawm txoj kev mus rau hauv cov txiaj ntsig rov qab los ntawm kev ua haujlwm recursive.
Kuv thawj lub tswv yim yog siv lub monad, uas zoo li siv raws nraim cov teebmeem uas peb xav tau. Thawj qhov kev siv kuv tau sau yog ze rau qhov kev xaiv no. Qhov tseeb, kuv muaj tsib qhov kev siv sib txawv ntawm ib qho thiab nws thiaj li txiav txim siab rau lwm qhov.
Ua ntej, peb yuav tsum tuav ib qho kev sib koom ua ke ntawm kev qhia cov cim - qhov no yog ib yam dab tsi txog Lub Xeev. Qhov thib ob, peb yuav tsum muaj peev xwm nres thaum muaj kev tsis sib haum xeeb. Qhov no tuaj yeem yog Monad rau Ib Leeg, lossis MonadPlus rau Tej zaum. Qhov sib txawv tseem ceeb yog tias Ob leeg tuaj yeem xa rov qab tus nqi yog tias kev suav tsis tau raug tso tseg, thiab Tej zaum yuav rov qab tsuas yog cov ntaub ntawv hais txog qhov no hauv qhov no. Txij li thaum peb tsis xav tau tus nqi sib cais rau kev ua tiav (nws twb tau khaws cia hauv Xeev), peb xaiv Tej zaum. Thiab lub sijhawm thaum peb xav tau los ua ke cov teebmeem ntawm ob lub monads, lawv tawm tuaj , uas precisely muab cov teebmeem no.
Vim li cas kuv thiaj xaiv hom complex? Ob qho laj thawj. Firstly, qhov kev siv tau zoo ib yam li qhov tseem ceeb. Qhov thib ob, peb yuav tsum tswj hwm tus nqi xa rov qab thaum muaj kev tsis sib haum xeeb thaum rov qab los ntawm recursion los kho qhov khib khib, uas yooj yim dua ua nyob rau hauv Tej zaum monad.
Yog li peb tau txais qhov kev siv no.
{-# 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)
Qhov twg thaiv yog lub hauv paus ntawm lub algorithm. Kuv yuav sim piav qhia txog dab tsi tshwm sim hauv nws.
- inVertex yog ib feem ntawm qhov tob-thawj tshawb nrhiav qhov twg peb mus ntsib vertex thawj zaug. Ntawm no peb muab tus lej sib faib rau lub vertex thiab khiav onEdge ntawm txhua tus neeg nyob ze. Qhov no kuj yog qhov uas peb rov qab hu cov pawg: yog tias msum xa rov qab tus nqi, peb thawb vertex v muaj.
- onEdge yog ib feem peb mus saib ntug. Nws yog hu ua ob zaug rau txhua ntug. Ntawm no peb xyuas seb lub vertex ntawm sab nraud tau mus xyuas, thiab mus saib yog tias tsis yog. Yog tias tau mus xyuas, peb xyuas seb lub ntug tsis sib haum. Yog tias nws yog, peb xa rov qab tus nqi - qhov saum toj kawg nkaus ntawm pawg recursion, qhov twg tag nrho lwm cov vertices yuav muab tso rau thaum rov qab los.
- processVertex kuaj xyuas txhua qhov vertex seb nws puas tau mus xyuas thiab khiav hauv Vertex rau nws yog tias tsis yog.
- dfs khiav processVertex ntawm txhua qhov vertices.
Yog tag nrho.
Keeb kwm ntawm lo lus INLINE
Lo lus INLINE tsis yog thawj qhov kev siv ntawm algorithm; nws tshwm sim tom qab. Thaum kuv sim nrhiav kev ua kom zoo dua, kuv pom tias qhov tsis yog INLINE version tau pom qeeb qeeb ntawm qee cov duab. Xav tias semantically cov haujlwm yuav tsum ua haujlwm zoo ib yam, qhov no ua rau kuv xav tsis thoob. Txawm tias tus neeg txawv, ntawm lwm lub tshuab nrog ib qho txawv version ntawm GHC tsis muaj qhov txawv txav.
Tom qab siv sijhawm ib lub lim tiam nyeem GHC Core tso tawm, Kuv tuaj yeem kho qhov teeb meem nrog ib kab ntawm INLINE qhia meej. Ntawm qee qhov taw tes ntawm GHC 8.4.4 thiab GHC 8.6.5 lub optimizer nres ua qhov no ntawm nws tus kheej.
Kuv tsis xav tias yuav ntsib cov av hauv Haskell programming. Txawm li cas los xij, txawm tias niaj hnub no, cov neeg ua haujlwm zoo qee zaum ua yuam kev, thiab nws yog peb txoj haujlwm los muab cov lus qhia rau lawv. Piv txwv li, ntawm no peb paub tias qhov kev ua haujlwm yuav tsum tau nyob rau hauv vim tias nws yog inlined nyob rau hauv qhov tseem ceeb version, thiab qhov no yog ib qho laj thawj los muab cov lus qhia rau compiler.
Tom ntej no yog dab tsi?
Tom qab ntawd kuv tau siv Hopcroft-Karp algorithm nrog rau lwm cov monads, thiab qhov ntawd yog qhov kawg ntawm qhov kev pab cuam.
Ua tsaug rau Google Lub Caij Ntuj Sov ntawm Code, kuv tau txais kev paub txog kev ua haujlwm hauv kev ua haujlwm, uas tsis yog pab kuv tau txais kev xyaum ua haujlwm ntawm Jane Street lub caij ntuj sov tom ntej (Kuv tsis paub tseeb tias qhov chaw no paub zoo npaum li cas txawm yog Habr cov neeg tuaj saib, tab sis nws yog ib qho. ntawm ob peb qhov uas koj tuaj yeem ua rau lub caij ntuj sov los koom nrog kev ua haujlwm ua haujlwm), tab sis kuj tau qhia kuv txog lub ntiaj teb zoo ntawm kev siv lub tswv yim no hauv kev xyaum, txawv txawv ntawm kuv qhov kev paub hauv cov lus ib txwm muaj.
Tau qhov twg los: www.hab.com