கடந்த கோடையில் நான் பங்கேற்றேன்
Google Summer of Code 2019 இல் ஒரு பங்கேற்பாளராக, நூலகத்தில் ஒரு திட்டத்தைச் செய்தேன்
இந்த இடுகையில் ஹாஸ்கெல்லில் இருதரப்புக்கான வரைபடத்தை சரிபார்க்கும் வழிமுறையை நான் செயல்படுத்துவது பற்றி பேசுவேன். அல்காரிதம் மிகவும் அடிப்படையான ஒன்றாகும் என்றாலும், அதை ஒரு செயல்பாட்டு பாணியில் அழகாக செயல்படுத்த எனக்கு பல மறு செய்கைகளை எடுத்தது மற்றும் நிறைய வேலை தேவைப்பட்டது. இதன் விளைவாக, நான் மோனாட் மின்மாற்றிகளுடன் செயல்படுத்துவதில் குடியேறினேன்.
என்னைப் பற்றி
என் பெயர் வாசிலி அல்பெரோவ், நான் செயின்ட் பீட்டர்ஸ்பர்க் HSE இல் நான்காம் ஆண்டு மாணவன். முன்பு நான் எழுதிய வலைப்பதிவில்
அல்காரிதம் செயல்படுத்துவது பற்றி
முன்னுரையில்
திட்டத்தில் பங்கேற்கும் மாணவர்கள் வலைப்பதிவு செய்ய வலுவாக ஊக்குவிக்கப்படுகிறார்கள். அவர்கள் எனக்கு வலைப்பதிவுக்கான தளத்தை வழங்கினர்
கேள்விக்குரிய குறியீட்டுடன் இழுக்கும் கோரிக்கையைக் காணலாம்
எனது பணியின் முடிவுகளைப் பற்றி நீங்கள் படிக்கலாம் (ஆங்கிலத்தில்)
இந்த இடுகையானது செயல்பாட்டு நிரலாக்கத்தின் அடிப்படைக் கருத்துகளை வாசகருக்கு அறிமுகப்படுத்தும் நோக்கம் கொண்டது, இருப்பினும் நேரம் வரும்போது பயன்படுத்தப்படும் அனைத்து சொற்களையும் நினைவுபடுத்த முயற்சிக்கிறேன்.
இருதரப்புக்கான வரைபடங்களைச் சரிபார்க்கிறது
இருதரப்புக்கான வரைபடத்தைச் சரிபார்ப்பதற்கான ஒரு அல்காரிதம் பொதுவாக எளிய வரைபட அல்காரிதம்களில் ஒன்றாக அல்காரிதம்கள் குறித்த பாடத்திட்டத்தில் கொடுக்கப்படுகிறது. அவரது யோசனை நேரடியானது: முதலில் நாம் எப்படியாவது இடது அல்லது வலது பங்குகளில் செங்குத்துகளை வைக்கிறோம், மேலும் முரண்பட்ட விளிம்பைக் கண்டறிந்தால், வரைபடம் இருதரப்பு அல்ல என்று நாங்கள் வலியுறுத்துகிறோம்.
இன்னும் கொஞ்சம் விவரம்: முதலில் இடது பங்கில் சில உச்சியை வைக்கிறோம். வெளிப்படையாக, இந்த உச்சியின் அனைத்து அண்டை நாடுகளும் வலது மடலில் இருக்க வேண்டும். மேலும், இந்த உச்சியின் அண்டை நாடுகளின் அனைத்து அண்டை நாடுகளும் இடது மடலில் இருக்க வேண்டும், மற்றும் பல. நாம் தொடங்கிய உச்சியின் இணைக்கப்பட்ட கூறுகளில் அண்டை நாடுகளுக்கு ஒதுக்கப்படாத செங்குத்துகள் இருக்கும் வரை, செங்குத்துகளுக்குப் பங்குகளை ஒதுக்குவதைத் தொடர்கிறோம். இணைக்கப்பட்ட அனைத்து கூறுகளுக்கும் இந்த செயலை மீண்டும் செய்கிறோம்.
ஒரே பகிர்வில் விழும் செங்குத்துகளுக்கு இடையில் ஒரு விளிம்பு இருந்தால், வரைபடத்தில் ஒற்றைப்படை சுழற்சியைக் கண்டறிவது கடினம் அல்ல, இது இருதரப்பு வரைபடத்தில் பரவலாக அறியப்பட்ட (மற்றும் மிகவும் வெளிப்படையாக) சாத்தியமற்றது. இல்லையெனில், எங்களிடம் சரியான பகிர்வு உள்ளது, அதாவது வரைபடம் இருபக்கமாக உள்ளது.
பொதுவாக, இந்த அல்காரிதம் பயன்படுத்தி செயல்படுத்தப்படுகிறது
எனவே, நாங்கள் பின்வரும் திட்டத்திற்கு வந்தோம். ஆழம்-முதல் தேடலைப் பயன்படுத்தி வரைபடத்தின் உச்சிகளைக் கடந்து, அவற்றிற்குப் பங்குகளை ஒதுக்குவோம், விளிம்பில் நகரும்போது பங்கின் எண்ணிக்கையை மாற்றுவோம். ஏற்கனவே ஒதுக்கப்பட்ட ஒரு பங்கைக் கொண்ட ஒரு உச்சியில் ஒரு பங்கை ஒதுக்க முயற்சித்தால், வரைபடம் இருதரப்பு இல்லை என்று பாதுகாப்பாகக் கூறலாம். எல்லா முனைகளுக்கும் ஒரு பங்கு ஒதுக்கப்பட்டு, எல்லா விளிம்புகளையும் பார்த்த தருணத்தில், எங்களிடம் ஒரு நல்ல பகிர்வு உள்ளது.
கணக்கீடுகளின் தூய்மை
Haskell இல் அனைத்து கணக்கீடுகளும் உள்ளன என்று கருதுகிறோம் சுத்தமான. இருப்பினும், இது உண்மையாக இருந்தால், திரையில் எதையும் அச்சிட எங்களுக்கு வழி இருக்காது. அனைத்தும், சுத்தமான கணக்கீடுகள் மிகவும் சோம்பேறித்தனமானவை, ஒன்று இல்லை சுத்தமான எதையாவது கணக்கிடுவதற்கான காரணங்கள். நிரலில் நிகழும் அனைத்து கணக்கீடுகளும் எப்படியாவது கட்டாயப்படுத்தப்படுகின்றன "அசுத்தமான" மோனாட் ஐஓ.
Monads என்பது கணக்கீடுகளைக் குறிக்கும் ஒரு வழியாகும் விளைவுகள் ஹாஸ்கெல்லில். அவை எவ்வாறு செயல்படுகின்றன என்பதை விளக்குவது இந்த இடுகையின் எல்லைக்கு அப்பாற்பட்டது. ஒரு நல்ல தெளிவான விளக்கத்தை ஆங்கிலத்தில் படிக்கலாம்
IO போன்ற சில மொனாட்கள் கம்பைலர் மேஜிக் மூலம் செயல்படுத்தப்பட்டாலும், மற்ற அனைத்தும் மென்பொருளில் செயல்படுத்தப்படுகின்றன மற்றும் அவற்றில் உள்ள அனைத்து கணக்கீடுகளும் தூய்மையானவை என்பதை இங்கே நான் சுட்டிக்காட்ட விரும்புகிறேன்.
பல விளைவுகள் உள்ளன, ஒவ்வொன்றும் அதன் சொந்த மோனாட் உள்ளது. இது மிகவும் வலுவான மற்றும் அழகான கோட்பாடு: அனைத்து மொனாட்களும் ஒரே இடைமுகத்தை செயல்படுத்துகின்றன. பின்வரும் மூன்று மொனாட்களைப் பற்றி பேசுவோம்:
- ea என்பது வகை a இன் மதிப்பை வழங்கும் அல்லது e வகையின் விதிவிலக்கைக் கொடுக்கும் கணக்கீடு ஆகும். இந்த மோனாட்டின் நடத்தை கட்டாய மொழிகளில் விதிவிலக்கு கையாளுதலுடன் மிகவும் ஒத்திருக்கிறது: பிழைகள் பிடிக்கப்படலாம் அல்லது கடந்து செல்லலாம். முக்கிய வேறுபாடு என்னவென்றால், ஹாஸ்கலில் உள்ள நிலையான நூலகத்தில் மோனாட் முற்றிலும் தர்க்கரீதியாக செயல்படுத்தப்படுகிறது, அதே நேரத்தில் கட்டாய மொழிகள் பொதுவாக இயக்க முறைமை வழிமுறைகளைப் பயன்படுத்துகின்றன.
- மாநில sa என்பது வகை a இன் மதிப்பை வழங்கும் மற்றும் வகை s இன் மாறக்கூடிய நிலைக்கு அணுகக்கூடிய ஒரு கணக்கீடு ஆகும்.
- ஒருவேளை ஏ. நத்திங் என்று திருப்பி அனுப்புவதன் மூலம் எந்த நேரத்திலும் குறுக்கிடக்கூடிய ஒரு கணக்கீட்டை மேப் மோனாட் வெளிப்படுத்துகிறது. இருப்பினும், மோனாட்பிளஸ் வகுப்பை மேப் வகைக்கு செயல்படுத்துவது பற்றி பேசுவோம், இது எதிர் விளைவை வெளிப்படுத்துகிறது: இது ஒரு குறிப்பிட்ட மதிப்பை வழங்குவதன் மூலம் எந்த நேரத்திலும் குறுக்கிடக்கூடிய ஒரு கணக்கீடு ஆகும்.
அல்காரிதம் செயல்படுத்துதல்
எங்களிடம் இரண்டு தரவு வகைகள் உள்ளன, வரைபடம் a மற்றும் Bigraph ab, அவற்றில் முதலாவது வகை a இன் மதிப்புகளுடன் லேபிளிடப்பட்ட செங்குத்துகளைக் கொண்ட வரைபடங்களைக் குறிக்கிறது, இரண்டாவது வகை a மற்றும் வலது மதிப்புகளுடன் பெயரிடப்பட்ட இடது பக்க செங்குத்துகளைக் கொண்ட இருதரப்பு வரைபடங்களைக் குறிக்கிறது. -பி வகையின் மதிப்புகளுடன் பெயரிடப்பட்ட பக்க முனைகள்.
இவை அல்கா நூலகத்தின் வகைகள் அல்ல. ஆல்காவில் திசைதிருப்பப்படாத இருதரப்பு வரைபடங்களுக்கான பிரதிநிதித்துவம் இல்லை. தெளிவுக்காக இது போன்ற வகைகளை செய்தேன்.
பின்வரும் கையொப்பங்களுடன் எங்களுக்கு உதவியாளர் செயல்பாடுகளும் தேவைப்படும்:
-- Список соседей данной вершины.
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)
ஆழம்-முதல் தேடலின் போது நாம் முரண்பட்ட விளிம்பைக் கண்டறிந்தால், ஒற்றைப்படை சுழற்சியானது மறுநிகழ்வு அடுக்கின் மேல் இருப்பதைப் பார்ப்பது எளிது. எனவே, அதை மீட்டெடுக்க, ரிகர்ஷன் ஸ்டாக் முதல் கடைசி உச்சியின் முதல் நிகழ்வு வரை அனைத்தையும் துண்டிக்க வேண்டும்.
ஒவ்வொரு உச்சிக்கும் பங்கு எண்களின் துணை வரிசையை பராமரிப்பதன் மூலம் ஆழமான முதல் தேடலை நாங்கள் செயல்படுத்துகிறோம். நாம் தேர்ந்தெடுத்த மோனாட்டின் ஃபங்க்டர் வகுப்பை செயல்படுத்துவதன் மூலம் ரிகர்ஷன் ஸ்டேக் தானாகவே பராமரிக்கப்படும்: சுழல்நிலை செயல்பாட்டிலிருந்து திரும்பிய முடிவில் பாதையிலிருந்து அனைத்து முனைகளையும் மட்டுமே வைக்க வேண்டும்.
எனது முதல் யோசனை, எதர் மோனாட்டைப் பயன்படுத்துவதாகும், இது நமக்குத் தேவையான விளைவுகளைச் சரியாகச் செயல்படுத்துவதாகத் தெரிகிறது. நான் எழுதிய முதல் செயலாக்கம் இந்த விருப்பத்திற்கு மிக நெருக்கமாக இருந்தது. உண்மையில், நான் ஒரு கட்டத்தில் ஐந்து வெவ்வேறு செயலாக்கங்களைக் கொண்டிருந்தேன், இறுதியில் மற்றொன்றில் குடியேறினேன்.
முதலில், பங்கு அடையாளங்காட்டிகளின் துணை வரிசையை நாம் பராமரிக்க வேண்டும் - இது மாநிலத்தைப் பற்றியது. இரண்டாவதாக, ஒரு மோதல் கண்டறியப்பட்டால் நாம் நிறுத்த முடியும். இது ஒன்றுக்கான மொனாட் அல்லது ஒருவேளை மோனாட்பிளஸ் ஆக இருக்கலாம். முக்கிய வேறுபாடு என்னவென்றால், கணக்கீடு நிறுத்தப்படாவிட்டால், மதிப்பை வழங்கலாம், மேலும் இந்த விஷயத்தில் இதைப் பற்றிய தகவலை மட்டுமே வழங்கலாம். வெற்றிக்கு தனி மதிப்பு தேவையில்லை என்பதால் (இது ஏற்கனவே மாநிலத்தில் சேமிக்கப்பட்டுள்ளது), ஒருவேளை என்பதை தேர்வு செய்கிறோம். இரண்டு மொனாட்களின் விளைவுகளை நாம் இணைக்க வேண்டிய தருணத்தில், அவை வெளியே வருகின்றன
அத்தகைய சிக்கலான வகையை நான் ஏன் தேர்வு செய்தேன்? இரண்டு காரணங்கள். முதலாவதாக, செயல்படுத்தல் கட்டாயத்திற்கு மிகவும் ஒத்ததாக மாறும். இரண்டாவதாக, ஒற்றைப்படை வளையத்தை மீட்டெடுக்க, மறுநிகழ்வில் இருந்து திரும்பும் போது, மோதலின் போது திரும்பும் மதிப்பை நாம் கையாள வேண்டும், இது ஒருவேளை மோனாடில் செய்ய மிகவும் எளிதானது.
எனவே இந்த நடைமுறையை நாங்கள் பெறுகிறோம்.
{-# 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 மதிப்பை வழங்கினால், வெர்டெக்ஸ் v ஐ அங்கு தள்ளுவோம்.
- ஒன்எட்ஜ் என்பது நாம் விளிம்பைப் பார்வையிடும் பகுதி. இது ஒவ்வொரு விளிம்பிற்கும் இரண்டு முறை அழைக்கப்படுகிறது. மறுபக்கத்தில் உள்ள உச்சியைப் பார்வையிட்டதா என்பதை இங்கே சரிபார்ப்போம், இல்லையெனில் அதைப் பார்வையிடுவோம். பார்வையிட்டால், விளிம்பு முரண்படுகிறதா என்பதை நாங்கள் சரிபார்க்கிறோம். அது இருந்தால், மதிப்பை நாங்கள் திரும்பப் பெறுகிறோம் - மறுநிகழ்வு அடுக்கின் மிக மேலே, மற்ற எல்லா முனைகளும் திரும்பியவுடன் வைக்கப்படும்.
- processVertex ஒவ்வொரு உச்சியையும் அது பார்வையிட்டதா என்பதைச் சரிபார்த்து, இல்லாவிட்டாலும் அதில் இன்வெர்டெக்ஸை இயக்குகிறது.
- dfs அனைத்து முனைகளிலும் processVertex ஐ இயக்குகிறது.
அவ்வளவுதான்.
INLINE என்ற வார்த்தையின் வரலாறு
INLINE என்ற சொல் அல்காரிதத்தின் முதல் செயலாக்கத்தில் இல்லை; அது பின்னர் தோன்றியது. ஒரு சிறந்த செயலாக்கத்தைக் கண்டறிய முயற்சித்தபோது, இன்லைன் அல்லாத பதிப்பு சில வரைபடங்களில் குறிப்பிடத்தக்க அளவில் மெதுவாக இருப்பதைக் கண்டேன். சொற்பொருள் செயல்பாடுகள் ஒரே மாதிரியாக செயல்பட வேண்டும் என்பதைக் கருத்தில் கொண்டு, இது என்னை மிகவும் ஆச்சரியப்படுத்தியது. கூட அந்நியமாக, GHC இன் வேறுபட்ட பதிப்பைக் கொண்ட மற்றொரு கணினியில் குறிப்பிடத்தக்க வேறுபாடு எதுவும் இல்லை.
GHC கோர் வெளியீட்டைப் படித்து ஒரு வாரம் கழித்து, வெளிப்படையான INLINE இன் ஒரு வரியில் சிக்கலைச் சரிசெய்ய முடிந்தது. GHC 8.4.4 மற்றும் GHC 8.6.5 க்கு இடையில் சில புள்ளியில், ஆப்டிமைசர் இதைத் தானே செய்வதை நிறுத்தியது.
ஹாஸ்கெல் புரோகிராமிங்கில் இதுபோன்ற அழுக்குகளை சந்திப்பேன் என்று நான் எதிர்பார்க்கவில்லை. இருப்பினும், இன்றும் கூட, மேம்படுத்துபவர்கள் சில நேரங்களில் தவறு செய்கிறார்கள், மேலும் அவர்களுக்கு குறிப்புகளை வழங்குவது எங்கள் வேலை. எடுத்துக்காட்டாக, செயல்பாடு இன்லைன் செய்யப்பட வேண்டும் என்பதை நாம் அறிவோம், ஏனெனில் அது கட்டாய பதிப்பில் உள்ளிடப்பட்டுள்ளது, மேலும் இது கம்பைலருக்கு ஒரு குறிப்பைக் கொடுக்க ஒரு காரணம்.
அடுத்து என்ன நடந்தது?
பின்னர் நான் ஹாப்கிராஃப்ட்-கார்ப் அல்காரிதத்தை மற்ற மொனாட்களுடன் செயல்படுத்தினேன், அது நிரலின் முடிவாகும்.
Google Summer of Codeக்கு நன்றி, நான் செயல்பாட்டு நிரலாக்கத்தில் நடைமுறை அனுபவத்தைப் பெற்றேன், இது அடுத்த கோடையில் ஜேன் ஸ்ட்ரீட்டில் இன்டர்ன்ஷிப்பைப் பெற எனக்கு உதவியது (Habr இன் அறிவார்ந்த பார்வையாளர்களிடையே கூட இந்த இடம் எவ்வளவு நன்கு அறியப்பட்டது என்பது எனக்குத் தெரியவில்லை, ஆனால் இது ஒன்றாகும். கோடையில் நீங்கள் செயல்பாட்டு நிரலாக்கத்தில் ஈடுபடக்கூடிய சிலவற்றில்), ஆனால் இந்த முன்னுதாரணத்தை நடைமுறையில் பயன்படுத்துவதற்கான அற்புதமான உலகத்திற்கு என்னை அறிமுகப்படுத்தியது, பாரம்பரிய மொழிகளில் எனது அனுபவத்திலிருந்து கணிசமாக வேறுபட்டது.
ஆதாரம்: www.habr.com