පසුගිය ගිම්හානයේදී මම සහභාගී විය - Google වෙතින් සිසුන් සඳහා වැඩසටහනක්. සෑම වසරකම, සංවිධායකයින් විවෘත මූලාශ්‍ර ව්‍යාපෘති කිහිපයක් තෝරා ගනී, එවැනි ප්‍රසිද්ධ ආයතන වලින් и . Google ලොව පුරා සිටින සිසුන්ට මෙම ව්‍යාපෘතිවල වැඩ කිරීමට ආරාධනා කරයි.
Google Summer of Code 2019 හි සහභාගිවන්නෙකු ලෙස, මම පුස්තකාලය තුළ ව්‍යාපෘතියක් කළෙමි සංවිධානය සමඟ , Haskell භාෂාව සංවර්ධනය කරන - වඩාත් ප්‍රසිද්ධ ක්‍රියාකාරී ක්‍රමලේඛන භාෂාවකි. ඇල්ගා යනු නියෝජනය කරන පුස්තකාලයකි Haskell හි ප්‍රස්තාර සඳහා නිරූපණය. එය භාවිතා වේ, උදාහරණයක් ලෙස, in — සංකේතාත්මක ගස්, ඇමතුම් සහ යැපුම් ප්‍රස්ථාර කේතය මත පදනම්ව ගොඩනඟන සහ ඒවා සංසන්දනය කළ හැකි Github පුස්තකාලයකි. මගේ ව්‍යාපෘතිය වූයේ ද්විපාර්ශ්වික ප්‍රස්ථාර සහ එම නිරූපණය සඳහා ඇල්ගොරිතම සඳහා ටයිප්-ආරක්ෂිත නිරූපණයක් එක් කිරීමයි.
මෙම ලිපියෙන් මම Haskell හි ද්විපාර්ශ්විකත්වය සඳහා ප්‍රස්ථාරයක් පරීක්ෂා කිරීම සඳහා ඇල්ගොරිතමයක් ක්රියාත්මක කිරීම ගැන කතා කරමි. ඇල්ගොරිතම වඩාත් මූලික එකක් වුවද, එය ක්‍රියාකාරී ශෛලියකින් අලංකාර ලෙස ක්රියාත්මක කිරීම මට පුනරාවර්තන කිහිපයක් ගෙන ගිය අතර විශාල වැඩ ප්‍රමාණයක් අවශ්‍ය විය. එහි ප්රතිඵලයක් වශයෙන්, මම මොනාඩ් ට්රාන්ස්ෆෝමර් සමඟ ක්රියාත්මක කිරීම මත පදිංචි විය.
මම ගැන
මගේ නම Vasily Alferov, මම ශාන්ත පීටර්ස්බර්ග් HSE හි සිව්වන වසරේ ශිෂ්‍යයෙක්මි. කලින් බ්ලොග් එකේ ලිව්වා и . දැනට මම සීමාවාසික පුහුණුවක යෙදී සිටිමි නෝර්වේ හි, මම ගැටලුවට ප්‍රවේශයන් මත වැඩ කරමින් සිටිමි . මගේ රුචිකත්වයට පරාමිතික ඇල්ගොරිතම සහ ක්‍රියාකාරී වැඩසටහන් ඇතුළත් වේ.
ඇල්ගොරිතම ක්රියාත්මක කිරීම ගැන
පෙරවදන
වැඩසටහනට සහභාගී වන සිසුන් බ්ලොග් කිරීමට දැඩි ලෙස දිරිමත් කරනු ලැබේ. ඔවුන් මට බ්ලොග් අඩවියට වේදිකාවක් ලබා දුන්නා . මෙම ලිපිය පරිවර්තනයකි , මා විසින් එහි ජූලි මාසයේදී ඉංග්‍රීසියෙන්, කෙටි පෙරවදනක් සමඟ ලියා ඇත.
ප්‍රශ්නගත කේතය සමඟ ඇදීමේ ඉල්ලීම සොයාගත හැක .
මගේ කාර්යයේ ප්‍රතිඵල ගැන ඔබට කියවිය හැකිය (ඉංග්‍රීසියෙන්) .
මෙම සටහන ක්‍රියාකාරී ක්‍රමලේඛනයේ මූලික සංකල්ප පාඨකයාට හුරු කිරීමට අදහස් කරන නමුත්, මම කාලය පැමිණි විට භාවිතා කරන සියලුම යෙදුම් සිහිපත් කිරීමට උත්සාහ කරමි.
ද්විපාර්ශ්විකත්වය සඳහා ප්‍රස්ථාර පරීක්ෂා කිරීම
ද්විපාර්ශ්විකත්වය සඳහා ප්‍රස්ථාරයක් පරීක්ෂා කිරීම සඳහා ඇල්ගොරිතමයක් සාමාන්යයෙන් ඇල්ගොරිතම පිළිබඳ පාඨමාලාවකදී සරලම ප්‍රස්ථාර ඇල්ගොරිතම වලින් එකක් ලෙස ලබා දේ. ඔහුගේ අදහස සරල ය: පළමුව අපි කෙසේ හෝ වම් හෝ දකුණු කොටසෙහි සිරස් තබමු, ගැටුම්කාරී දාරයක් සොයාගත් විට, ප්‍රස්ථාරය ද්විපාර්ශ්වික නොවන බව අපි ප්‍රකාශ කරමු.
තව ටිකක් විස්තර: පළමුව අපි වම් කොටසෙහි සිරස් කිහිපයක් තබමු. නිසැකවම, මෙම ශීර්ෂයේ සියලුම අසල්වැසියන් දකුණු පසෙහි වැතිර සිටිය යුතුය. තවද, මෙම ශීර්ෂයේ අසල්වාසීන්ගේ සියලුම අසල්වැසියන් වම් පසෙහි වැතිර සිටිය යුතුය, සහ එසේ ය. අප විසින් ආරම්භ කරන ලද ශීර්ෂයේ සම්බන්ධිත සංඝටකයේ අපි අසල්වැසියන් වෙත පවරා නොමැති සිරස් තවමත් පවතින තාක් අපි සිරස් වෙත කොටස් පැවරීම දිගටම කරගෙන යන්නෙමු. ඉන්පසුව අපි සියලුම සම්බන්ධිත සංරචක සඳහා මෙම ක්‍රියාව නැවත කරන්නෙමු.
එකම කොටසට වැටෙන සිරස් අතර දාරයක් තිබේ නම්, ද්විපාර්ශ්වික ප්‍රස්ථාරයක පුළුල් ලෙස දන්නා (හා පැහැදිලිවම) කළ නොහැකි ඔත්තේ චක්‍රයක් ප්‍රස්ථාරයේ සොයා ගැනීම අපහසු නැත. එසේ නොමැතිනම්, අපට නිවැරදි කොටසක් ඇත, එනම් ප්‍රස්ථාරය ද්විපාර්ශ්වික වේ.
සාමාන්යයෙන්, මෙම ඇල්ගොරිතම භාවිතා කර ක්රියාත්මක වේ හෝ . අත්‍යවශ්‍ය භාෂාවලින්, ගැඹුර-පළමු සෙවීම සාමාන්යයෙන් භාවිතා කරනුයේ එය තරමක් සරල වන අතර අමතර දත්ත ව්‍යුහයන් අවශ්‍ය නොවන බැවිනි. එය වඩාත් සාම්ප්‍රදායික බැවින් මම ගැඹුර-පළමු සෙවුම ද තෝරා ගත්තෙමි.
මේ අනුව, අපි පහත යෝජනා ක්රමයට පැමිණියෙමු. අපි ගැඹුර-පළමු සෙවුම භාවිතයෙන් ප්‍රස්ථාරයේ සිරස් හරහා ගමන් කර ඒවාට කොටස් පවරමු, අපි දාරය දිගේ ගමන් කරන විට කොටසේ අංකය වෙනස් කරමු. අපි දැනටමත් කොටසක් පවරා ඇති ශීර්ෂයකට කොටසක් පැවරීමට උත්සාහ කරන්නේ නම්, ප්‍රස්ථාරය ද්විපාර්ශ්වික නොවන බව අපට ආරක්ෂිතව පැවසිය හැකිය. සියලුම සිරස් වලට කොටස ලබා දී අපි සියලු දාර දෙස බැලූ මොහොතේ අපට හොඳ කොටසක් තිබේ.
ගණනය කිරීම් වල සංශුද්ධතාවය
Haskell හි අපි සියලු ගණනය කිරීම් බව උපකල්පනය කරමු පිරිසිදු. කෙසේ වෙතත්, මෙය සැබවින්ම එසේ නම්, අපට තිරයට කිසිවක් මුද්රණය කිරීමට ක්රමයක් නැත. කිසිසේත්, පිරිසිදුයි ගණනය කිරීම් කොතරම් කම්මැලිද යත් එකක් නැත පිරිසිදු යමක් ගණනය කිරීමට හේතු. වැඩසටහනේ සිදුවන සියලුම ගණනය කිරීම් කෙසේ හෝ බලහත්කාරයෙන් සිදු කෙරේ "අපිරිසිදු" මොනාඩ් IO.
මොනාඩ් යනු ගණනය කිරීම් නියෝජනය කරන ක්‍රමයකි බලපෑම් Haskell හි. ඔවුන් ක්‍රියා කරන ආකාරය පැහැදිලි කිරීම මෙම සටහනේ විෂය පථයෙන් ඔබ්බට ය. හොඳ සහ පැහැදිලි විස්තරයක් ඉංග්‍රීසියෙන් කියවිය හැකිය .
මෙහිදී මට පෙන්වා දීමට අවශ්‍ය වන්නේ IO වැනි සමහර monads compiler magic හරහා ක්රියාත්මක වන අතර අනෙක් සියල්ලම පාහේ මෘදුකාංග වල ක්රියාත්මක වන අතර ඒවායේ සියලුම ගණනය කිරීම් පිරිසිදු බවයි.
බොහෝ බලපෑම් ඇති අතර ඒ සෑම එකක්ම තමන්ගේම මොනාඩ් ඇත. මෙය ඉතා ශක්තිමත් හා ලස්සන න්‍යායකි: සියලුම මොනාඩ් එකම අතුරු මුහුණතක් ක්රියාත්මක කරයි. අපි පහත මොනාඩ් තුන ගැන කතා කරමු:
- එක්කෝ ea යනු a වර්ගයේ අගයක් ලබා දෙන හෝ e වර්ගයේ ව්‍යතිරේකයක් ලබා දෙන ගණනය කිරීමකි. මෙම මොනාඩ්ගේ හැසිරීම අත්‍යවශ්‍ය භාෂාවලින් ව්‍යතිරේක හැසිරවීමට බෙහෙවින් සමාන ය: දෝෂ හසු කර ගැනීමට හෝ සම්මත කිරීමට හැකිය. ප්රධාන වෙනස නම් මොනාඩ් සම්පූර්ණයෙන්ම තාර්කිකව Haskell හි සම්මත පුස්තකාලයේ ක්රියාත්මක කර ඇති අතර අනිවාර්ය භාෂා සාමාන්යයෙන් මෙහෙයුම් පද්ධති යාන්ත්‍රණ භාවිතා කරයි.
- රාජ්‍ය sa යනු a වර්ගයේ අගයක් ලබා දෙන සහ s වර්ගයේ විකෘති තත්ත්වයට ප්‍රවේශය ඇති ගණනය කිරීමකි.
- සමහර විට අ. Maybe monad කිසිවක් ආපසු ලබා දීමෙන් ඕනෑම වේලාවක බාධා කළ හැකි ගණනය කිරීමක් ප්‍රකාශ කරයි. කෙසේ වෙතත්, ප්‍රතිවිරුද්ධ බලපෑම ප්‍රකාශ කරන Maybe වර්ගය සඳහා MonadPlus පන්තිය ක්රියාත්මක කිරීම ගැන අපි කතා කරමු: එය නිශ්චිත අගයක් ආපසු ලබා දීමෙන් ඕනෑම වේලාවක බාධා කළ හැකි ගණනය කිරීමකි.
ඇල්ගොරිතම ක්රියාත්මක කිරීම
අපට දත්ත වර්ග දෙකක් ඇත, ප්‍රස්තාරය a සහ Bigraph ab, ඉන් පළමුවැන්න a වර්ගයේ අගයන් සමඟ ලේබල් කර ඇති සිරස් සහිත ප්‍රස්ථාර නියෝජනය කරන අතර දෙවැන්න a සහ දකුණේ අගයන් සමඟ ලේබල් කර ඇති වම් පැත්තේ සිරස් සහිත ද්විපාර්ශ්වික ප්‍රස්ථාර නියෝජනය කරයි. b වර්ගයේ අගයන් සමඟ ලේබල් කර ඇති පැති සිරස්.
මේවා ඇල්ගා පුස්තකාලයේ වර්ග නොවේ. යොමු නොකළ ද්විපාර්ශ්වික ප්‍රස්ථාර සඳහා ඇල්ගාට නියෝජනයක් නොමැත. මම මේ වගේ වර්ග හැදුවේ පැහැදිලිකමට.
අපට පහත අත්සන් සහිත උපකාරක කාර්යයන් ද අවශ්‍ය වනු ඇත:
-- Список соседей данной вершины.
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)ගැඹුර-පළමු සෙවුමේදී අපට ගැටුම්කාරී මායිමක් හමු වූයේ නම්, ඔත්තේ චක්‍රය ප්‍රත්‍යාවර්තක අට්ටිය මත පිහිටා ඇති බව දැකීම පහසුය. මේ අනුව, එය යථා තත්ත්වයට පත් කිරීම සඳහා, අපි පුනරාවර්තන තොගයේ සිට අවසාන ශීර්ෂයේ පළමු සිදුවීම දක්වා සියල්ල කපා දැමිය යුතුය.
අපි එක් එක් ශීර්ෂය සඳහා කොටස් අංක ආශ්‍රිත අරාවක් පවත්වා ගනිමින් ගැඹුර-පළමු සෙවුම ක්රියාත්මක කරන්නෙමු. අප විසින් තෝරා ගන්නා ලද මොනාඩ්හි Functor class එක ක්රියාත්මක කිරීම හරහා ප්‍රත්‍යාවර්තක අට්ටිය ස්වයංක්‍රීයව පවත්වා ගෙන යනු ඇත: අපට අවශ්‍ය වන්නේ ප්‍රත්‍යාවර්තී ශ්‍රිතයෙන් ආපසු ලැබෙන ප්‍රතිඵලයට මාර්ගයෙන් සියලුම සිරස් දැමීම පමණි.
මගේ පළමු අදහස වූයේ අපට අවශ්‍ය ප්‍රයෝග හරියටම ක්රියාත්මක කරන බව පෙනෙන Either monad භාවිතා කිරීමයි. මා විසින් ලියන ලද පළමු ක්රියාත්මක කිරීම මෙම විකල්පයට ඉතා සමීප විය. ඇත්ත වශයෙන්ම, මට එක් අවස්ථාවක විවිධ ක්රියාත්මක කිරීම් පහක් තිබූ අතර අවසානයේ තවත් එකක පදිංචි විය.
පළමුව, අපි කොටස් හඳුනාගැනීම් වල ආශ්‍රිත මාලාවක් පවත්වා ගත යුතුය - මෙය රාජ්‍යය පිළිබඳ යමක් වේ. දෙවනුව, ගැටුමක් අනාවරණය වූ විට නතර කිරීමට අපට හැකි විය යුතුය. මෙය එක්කෝ සඳහා Monad විය හැකිය, නැතහොත් සමහරවිට සඳහා MonadPlus විය හැක. ප්රධාන වෙනස නම්, ගණනය කිරීම නතර කර නොමැති නම්, එක්කෝ අගයක් ආපසු ලබා දිය හැකි අතර, සමහර විට මෙම අවස්ථාවෙහිදී මේ පිළිබඳ තොරතුරු පමණක් ලබා දෙයි. සාර්ථකත්වය සඳහා අපට වෙනම අගයක් අවශ්‍ය නොවන බැවින් (එය දැනටමත් රාජ්‍යයේ ගබඩා කර ඇත), අපි සමහරවිට තෝරා ගනිමු. මොනාඩ් දෙකක බලපෑම් ඒකාබද්ධ කිරීමට අවශ්‍ය මොහොතේදී, ඒවා පිටතට පැමිණේ , මෙම බලපෑම් නිශ්චිතවම ඒකාබද්ධ කරයි.
මම එවැනි සංකීර්ණ වර්ගයක් තෝරා ගත්තේ ඇයි? හේතු දෙකක්. පළමුව, ක්රියාත්මක කිරීම අත්‍යවශ්‍ය දෙයට බෙහෙවින් සමාන ය. දෙවනුව, සමහර විට මොනාඩ් හි කිරීමට වඩා පහසු ඔත්තේ ලූපය ප්‍රතිසාධනය කිරීම සඳහා පුනරාවර්තනයෙන් ආපසු එන විට ගැටුමකදී ප්‍රතිලාභ අගය හැසිරවිය යුතුය.
මේ අනුව අපි මෙම ක්රියාත්මක කිරීම ලබා ගනිමු.
{-# 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)
එහිදී බ්ලොක් යනු ඇල්ගොරිතමයේ හරයයි. ඒක ඇතුලේ වෙන්නේ මොකක්ද කියලා මම පැහැදිලි කරන්න උත්සාහ කරන්නම්.
- inVertex යනු ගැඹුර-පළමු සෙවුමේ කොටස වන අතර එහිදී අපි පළමු වරට ශීර්ෂයට පිවිසෙමු. මෙහිදී අපි ශීර්ෂයට කොටස් අංකයක් ලබා දී සියලු අසල්වැසියන් මත onEdge ධාවනය කරන්නෙමු. අපි ඇමතුම් තොගය ප්‍රතිසාධනය කරන්නේද මෙහිදීය: msum අගයක් ආපසු ලබා දෙන්නේ නම්, අපි එහි vertex v තල්ලු කරමු.
- onEdge යනු අපි කෙළවරට පිවිසෙන කොටසයි. එය එක් එක් දාරය සඳහා දෙවරක් කැඳවනු ලැබේ. මෙහිදී අපි අනෙක් පැත්තේ ඇති ශීර්ෂය සංචාරය කර ඇත්දැයි පරීක්ෂා කර, එසේ නොමැති නම් එය බලන්න. සංචාරය කළහොත්, දාරය පරස්පර විරෝධී දැයි අපි පරීක්ෂා කරමු. එය එසේ නම්, අපි අගය ආපසු ලබා දෙන්නෙමු - ප්‍රත්‍යාවර්තක තොගයේ ඉහළම කොටස, අනෙක් සියලුම සිරස් ආපසු පැමිණීමේදී ස්ථානගත වේ.
- processVertex විසින් එක් එක් ශීර්ෂය වෙත ගොස් තිබේද යන්න පරීක්ෂා කර නොඑසේ නම් එය මත inVertex ධාවනය කරයි.
- dfs සියළුම vertices මත processVertex ධාවනය කරයි.
එච්චරයි.
INLINE යන වචනයේ ඉතිහාසය
INLINE යන වචනය ඇල්ගොරිතමයේ පළමු ක්රියාත්මක කිරීමේදී නොතිබුණි; එය පසුව දර්ශනය විය. මම වඩා හොඳ ක්රියාත්මක කිරීමක් සොයා ගැනීමට උත්සාහ කළ විට, සමහර ප්‍රස්ථාරවල INLINE නොවන අනුවාදය සැලකිය යුතු ලෙස මන්දගාමී බව මට පෙනී ගියේය. අර්ථාන්විතව කාර්යයන් එකම ලෙස ක්‍රියා කළ යුතු බව සලකන විට, මෙය මා පුදුමයට පත් කළේය. ආගන්තුක වුවත්, GHC හි වෙනස් අනුවාදයක් සහිත වෙනත් යන්ත්‍රයක සැලකිය යුතු වෙනසක් නොතිබුණි.
GHC Core ප්‍රතිදානය කියවීමෙන් සතියක් ගත කිරීමෙන් පසු, මට පැහැදිලි INLINE එක පේළියකින් ගැටලුව විසඳා ගැනීමට හැකි විය. GHC 8.4.4 සහ GHC 8.6.5 අතර යම් අවස්ථාවක දී ප්‍රශස්තකාරකය මෙය තනිවම කිරීම නතර කළේය.
Haskell ක්‍රමලේඛනයේදී මේ වගේ කුණුහරුප මුණගැහෙයි කියලා මම හිතුවේ නැහැ. කෙසේ වෙතත්, අද පවා, ප්‍රශස්තකරණය කරන්නන් සමහර විට වැරදි කරන අතර, ඔවුන්ට ඉඟි ලබා දීම අපගේ කාර්යයකි. උදාහරණයක් ලෙස, මෙහි අපි ශ්‍රිතය inlined කළ යුතු බව දනිමු, එය අනිවාර්ය අනුවාදයේ ඇතුළත් කර ඇති බැවින්, මෙය සම්පාදකයට ඉඟියක් ලබා දීමට හේතුවක් වේ.
ඊළඟට මොකද වුණේ?
ඉන්පසුව මම වෙනත් මොනාඩ් සමඟ Hopcroft-Karp ඇල්ගොරිතම ක්රියාත්මක කළ අතර එය වැඩසටහනේ අවසානය විය.
Google Summer of Code වලට ස්තූතියි, මම ක්‍රියාකාරී වැඩසටහන්කරණයේ ප්‍රායෝගික අත්දැකීමක් ලබා ගත්තෙමි, එය මට ඊළඟ ගිම්හානයේදී Jane Street හි සීමාවාසික පුහුණුවක් ලබා ගැනීමට උපකාර කළා පමණක් නොව (මෙම ස්ථානය Habr ගේ දැනුවත් ප්‍රේක්ෂකයින් අතර පවා කෙතරම් ප්‍රසිද්ධ දැයි මට විශ්වාස නැත, නමුත් එය එකකි. ක්‍රියාකාරී ක්‍රමලේඛනයේ නිරත වීමට ඔබට ගිම්හානයේදී හැකි කිහිප දෙනෙකුගෙන්), නමුත් සාම්ප්‍රදායික භාෂාවල මගේ අත්දැකීම්වලට වඩා සැලකිය යුතු ලෙස වෙනස් වූ මෙම ආදර්ශය ප්‍රායෝගිකව ක්රියාත්මක කිරීමේ අපූරු ලෝකයට මා හඳුන්වා දුන්නේය.
මූලාශ්රය: www.habr.com