சில நாட்களுக்கு முன் நடந்தது ஹைட்ரா மாநாடு. JUG.ru குழுவைச் சேர்ந்த தோழர்கள் கனவுப் பேச்சாளர்களை (லெஸ்லி லாம்போர்ட்! கிளிஃப் கிளிக்! மார்ட்டின் க்ளெப்மேன்!) அழைத்தனர் மற்றும் விநியோகிக்கப்பட்ட அமைப்புகள் மற்றும் கம்ப்யூட்டிங்கிற்கு இரண்டு நாட்கள் ஒதுக்கினர். மாநாட்டின் மூன்று பங்காளிகளில் கோண்டூர் ஒருவர். நாங்கள் சாவடியில் பேசினோம், எங்கள் விநியோகிக்கப்பட்ட சேமிப்பிடத்தைப் பற்றி பேசினோம், பிங்கோ விளையாடினோம், புதிர்களைத் தீர்த்தோம்.

இது அவர்களின் உரையின் ஆசிரியரிடமிருந்து கோண்டூர் ஸ்டாண்டில் உள்ள பணிகளின் பகுப்பாய்வுடன் கூடிய இடுகை. ஹைட்ராவில் யார் இருந்தார்கள் - உங்கள் மூளையை நீட்டிக்க ஒரு வாய்ப்பு - இனிமையான அனுபவத்தை நினைவில் கொள்ள இதுவே உங்கள் காரணம். பெரிய ஓ-குறிப்பு.

பங்கேற்பாளர்கள் தங்கள் முடிவை எழுதுவதற்காக ஃபிளிப்சார்ட்டை ஸ்லைடுகளாக அகற்றினர். நான் கேலி செய்யவில்லை - சரிபார்ப்புக்காக இந்தக் காகிதக் கட்டை அவர்கள் ஒப்படைத்தார்கள்:

மொத்தம் மூன்று பணிகள் இருந்தன:

• சுமை சமநிலைக்கு எடைகள் மூலம் பிரதிகளைத் தேர்ந்தெடுப்பது பற்றி
• இன்-மெமரி தரவுத்தளத்திற்கு எதிராக வினவல் முடிவுகளை வரிசைப்படுத்துவது பற்றி
• ஒரு ரிங் டோபாலஜியுடன் ஒரு விநியோகிக்கப்பட்ட அமைப்பில் மாநில பரிமாற்றம்

பணி 1. ClusterClient

விநியோகிக்கப்பட்ட அமைப்பின் N எடையுள்ள பிரதிகளிலிருந்து K இன் திறமையான தேர்வுக்கான வழிமுறையை முன்மொழிவது அவசியம்:

N முனைகளின் பெருமளவில் விநியோகிக்கப்பட்ட கிளஸ்டருக்கான கிளையன்ட் லைப்ரரியை உருவாக்கும் பணியில் உங்கள் குழு உள்ளது. நூலகம் முனைகளுடன் தொடர்புடைய பல்வேறு மெட்டாடேட்டாவைக் கண்காணிக்கும் (எ.கா., அவற்றின் தாமதங்கள், 4xx/5xx மறுமொழி விகிதங்கள், முதலியன) மற்றும் மிதக்கும் புள்ளி எடைகள் W1..WN ஐ அவர்களுக்கு ஒதுக்கும். ஒரே நேரத்தில் செயல்படுத்தும் உத்தியை ஆதரிப்பதற்காக, நூலகம் N முனைகளின் K ஐத் தோராயமாகத் தேர்ந்தெடுக்க முடியும் - தேர்ந்தெடுக்கப்படுவதற்கான வாய்ப்பு ஒரு முனையின் எடைக்கு விகிதாசாரமாக இருக்க வேண்டும்.

முனைகளை திறம்பட தேர்ந்தெடுக்க ஒரு அல்காரிதத்தை முன்மொழியவும். பெரிய O குறியீட்டைப் பயன்படுத்தி அதன் கணக்கீட்டு சிக்கலை மதிப்பிடவும்.

ஏன் எல்லாம் ஆங்கிலத்தில்?

ஏனெனில் இந்த வடிவத்தில் மாநாட்டில் பங்கேற்பாளர்கள் அவர்களுடன் சண்டையிட்டனர் மற்றும் ஆங்கிலம் ஹைட்ராவின் அதிகாரப்பூர்வ மொழியாக இருந்தது. பணிகள் இப்படி இருந்தது:

காகிதம் மற்றும் பென்சிலை எடுத்துக் கொள்ளுங்கள், சிந்தியுங்கள், உடனடியாக ஸ்பாய்லர்களைத் திறக்க அவசரப்பட வேண்டாம் 🙂

தீர்வு பற்றிய பகுப்பாய்வு (வீடியோ)

5:53 இல் தொடங்கி, 4 நிமிடங்கள் மட்டுமே:

ஃபிளிப்சார்ட்டைக் கொண்ட தோழர்கள் தங்கள் தீர்வை எவ்வாறு உருவாக்கினார்கள் என்பது இங்கே:

தீர்வின் பகுப்பாய்வு (உரை)

பின்வரும் தீர்வு மேற்பரப்பில் உள்ளது: அனைத்து பிரதிகளின் எடைகளையும் கூட்டவும், 0 முதல் அனைத்து எடைகளின் கூட்டுத்தொகை வரை ஒரு சீரற்ற எண்ணை உருவாக்கவும், பின்னர் 0 முதல் (i-1) வரையிலான பிரதி எடைகளின் கூட்டுத்தொகை ஐ-பிரதியைத் தேர்ந்தெடுக்கவும். ரேண்டம் எண்ணை விட குறைவாக உள்ளது, மேலும் 0 முதல் i-th வரையிலான பிரதி எடைகளின் கூட்டுத்தொகை - அதை விட அதிகம். எனவே ஒரு பிரதியைத் தேர்ந்தெடுக்க முடியும், அடுத்ததைத் தேர்ந்தெடுக்க, தேர்ந்தெடுக்கப்பட்ட பிரதியைக் கருத்தில் கொள்ளாமல் முழு செயல்முறையையும் மீண்டும் செய்ய வேண்டும். அத்தகைய வழிமுறையுடன், ஒரு பிரதியைத் தேர்ந்தெடுப்பதில் உள்ள சிக்கலானது O(N), K பிரதிகளைத் தேர்ந்தெடுப்பதில் உள்ள சிக்கலானது O(N K) ~ O(N2) ஆகும்.

இருபடி சிக்கலானது மோசமானது, ஆனால் அதை மேம்படுத்தலாம். இதைச் செய்ய, நாங்கள் கட்டுவோம் பிரிவு மரம் எடைகளின் தொகைகளுக்கு. ஆழமான lg N இன் ஒரு மரம் பெறப்படும், அதன் இலைகளில் பிரதி எடைகள் இருக்கும், மற்றும் மீதமுள்ள முனைகளில் - பகுதித் தொகைகள், மரத்தின் வேரில் உள்ள அனைத்து எடைகளின் கூட்டுத்தொகை வரை. அடுத்து, 0 முதல் அனைத்து எடைகளின் கூட்டுத்தொகை வரை ஒரு சீரற்ற எண்ணை உருவாக்கி, i-வது பிரதியைக் கண்டுபிடித்து, மரத்திலிருந்து அதை அகற்றி, மீதமுள்ள பிரதிகளைக் கண்டறியும் செயல்முறையை மீண்டும் செய்கிறோம். இந்த அல்காரிதம் மூலம், ஒரு மரத்தை உருவாக்குவதற்கான சிக்கலானது O(N), i-th பிரதியை கண்டுபிடித்து மரத்திலிருந்து அகற்றுவது O(lg N), K பிரதிகளைத் தேர்ந்தெடுப்பதில் உள்ள சிக்கலானது O(N + K lg N) ~ O(N lg N) .

லீனியர்-லாக் சிக்கலானது இருபடி சிக்கலை விட நன்றாக இருக்கிறது, குறிப்பாக பெரிய K க்கு.

இது இந்த அல்காரிதம் குறியீட்டில் செயல்படுத்தப்பட்டது திட்டத்தில் இருந்து கிளஸ்டர் கிளையண்ட் நூலகங்கள் "கிழக்கு". (அங்கு, மரம் O(N lg N) இல் கட்டப்பட்டுள்ளது, ஆனால் இது அல்காரிதத்தின் இறுதி சிக்கலைப் பாதிக்காது.)

பணி 2. வரிக்குதிரை

தன்னிச்சையான குறியிடப்படாத புலத்தின் மூலம் நினைவகத்தில் ஆவணங்களை திறம்பட வரிசைப்படுத்துவதற்கான வழிமுறையை முன்மொழிவது அவசியம்:

துண்டிக்கப்பட்ட இன்-மெமரி ஆவண தரவுத்தளத்தை உருவாக்கும் பணியில் உங்கள் குழு உள்ளது. M (பொதுவாக N <100 << M) அளவின் தொகுப்பிலிருந்து தன்னிச்சையான (குறியீடு செய்யப்படாத) எண் புலத்தால் வரிசைப்படுத்தப்பட்ட மேல் N ஆவணங்களைத் தேர்ந்தெடுப்பது பொதுவான பணிச்சுமையாகும். மேல் S ஆவணங்களை (S ~ N) தவிர்த்துவிட்டு மேல் N ஐத் தேர்ந்தெடுப்பது சற்று குறைவான பொதுவான பணிச்சுமையாகும்.

அத்தகைய வினவல்களை திறம்பட செயல்படுத்த ஒரு அல்காரிதத்தை முன்மொழியவும். சராசரி வழக்கு மற்றும் மோசமான சூழ்நிலைகளில் பெரிய O குறியீட்டைப் பயன்படுத்தி அதன் கணக்கீட்டு சிக்கலை மதிப்பிடவும்.

தீர்வு பற்றிய பகுப்பாய்வு (வீடியோ)

34:50 இல் தொடங்கி, 6 நிமிடங்கள் மட்டுமே:

தீர்வின் பகுப்பாய்வு (உரை)

மேற்பரப்பு தீர்வு: அனைத்து ஆவணங்களையும் வரிசைப்படுத்தவும் (உதாரணமாக குவிகார்ட்), பின்னர் N+S ஆவணங்களை எடுக்கவும். இந்த வழக்கில், வரிசைப்படுத்துதலின் சிக்கலானது சராசரியாக O(M lg M), மோசமான O(M2) இல் உள்ளது.

அனைத்து எம் ஆவணங்களையும் வரிசைப்படுத்தி, அதில் ஒரு சிறிய பகுதியை மட்டும் எடுத்துக்கொள்வது திறமையற்றது என்பது வெளிப்படையானது. அனைத்து ஆவணங்களையும் வரிசைப்படுத்தாமல் இருக்க, ஒரு அல்காரிதம் பொருத்தமானது விரைவான தேர்வு, இது விரும்பிய ஆவணங்களில் N + S ஐத் தேர்ந்தெடுக்கும் (அவை எந்த அல்காரிதம் மூலமாகவும் வரிசைப்படுத்தப்படலாம்). இந்த வழக்கில், சிக்கலானது சராசரியாக O(M) ஆக குறையும், அதே சமயம் மோசமான நிலை அப்படியே இருக்கும்.

இருப்பினும், நீங்கள் அதை இன்னும் திறமையாக செய்யலாம் - வழிமுறையைப் பயன்படுத்தவும் பைனரி ஹீப் ஸ்ட்ரீமிங். இந்த வழக்கில், முதல் N+S ஆவணங்கள் குறைந்தபட்ச அல்லது அதிகபட்சக் குவியலில் (வரிசைப்படுத்தும் திசையைப் பொறுத்து) சேர்க்கப்படும், பின்னர் ஒவ்வொரு அடுத்த ஆவணமும் தற்போதைய குறைந்தபட்ச அல்லது அதிகபட்ச ஆவணத்தைக் கொண்ட மரத்தின் வேருடன் ஒப்பிடப்படுகிறது, தேவைப்பட்டால் மரத்தில் சேர்க்கப்படும். . இந்த வழக்கில், மோசமான நிலையில், நீங்கள் தொடர்ந்து மரத்தை மீண்டும் கட்டியெழுப்ப வேண்டியிருக்கும் போது, ​​O(M lg M) சிக்கலானது, விரைவுத் தேர்வைப் போலவே, சராசரியாக O(M) சிக்கலானது.

இருப்பினும், ஹீப் ஸ்ட்ரீமிங் மிகவும் திறமையானதாக மாறுகிறது, ஏனெனில் நடைமுறையில் பெரும்பாலான ஆவணங்களை அதன் மூல உறுப்புடன் ஒரே ஒரு ஒப்பீட்டிற்குப் பிறகு குவியலை மீண்டும் உருவாக்காமல் நிராகரிக்க முடியும். கோண்டூரில் உருவாக்கப்பட்ட மற்றும் பயன்படுத்தப்படும் Zebra இன்-மெமரி ஆவண தரவுத்தளத்தில் இத்தகைய வரிசையாக்கம் செயல்படுத்தப்படுகிறது.

பணி 3. மாநில பரிமாற்றங்கள்

மாநிலங்களை மாற்றுவதற்கு மிகவும் திறமையான வழிமுறையை முன்மொழிவது அவசியம்:

N முனைகளின் விநியோகிக்கப்பட்ட கிளஸ்டருக்கான ஆடம்பரமான நிலை பரிமாற்ற பொறிமுறையை உருவாக்கும் பணியில் உங்கள் குழு உள்ளது. i-th node இன் நிலை (i+1)-th node க்கு மாற்றப்பட வேண்டும், N-th node இன் நிலை முதல் முனைக்கு மாற்றப்பட வேண்டும். இரண்டு கணுக்கள் தங்கள் நிலைகளை அணுவாகப் பரிமாறிக்கொள்ளும் போது மாநில இடமாற்றம் மட்டுமே ஆதரிக்கப்படும் செயல்பாடு ஆகும். ஒரு ஸ்டேட் ஸ்வாப் M மில்லி விநாடிகள் எடுக்கும் என்று அறியப்படுகிறது. ஒவ்வொரு முனையும் எந்த நேரத்திலும் ஒற்றை நிலை மாற்றத்தில் பங்கேற்க முடியும்.

ஒரு கிளஸ்டரில் உள்ள அனைத்து முனைகளின் நிலைகளையும் மாற்ற எவ்வளவு நேரம் ஆகும்?

தீர்வின் பகுப்பாய்வு (உரை)

மேற்பரப்பு தீர்வு: முதல் மற்றும் இரண்டாவது உறுப்புகளின் நிலைகளை மாற்றவும், பின்னர் முதல் மற்றும் மூன்றாவது, பின்னர் முதல் மற்றும் நான்காவது, மற்றும் பல. ஒவ்வொரு பரிமாற்றத்திற்கும் பிறகு, ஒரு தனிமத்தின் நிலை விரும்பிய நிலையில் இருக்கும். நீங்கள் O(N) வரிசைமாற்றங்களைச் செய்து O(NM) நேரத்தைச் செலவிட வேண்டும்.

நேரியல் நேரம் நீண்டது, எனவே நீங்கள் உறுப்புகளின் நிலைகளை ஜோடிகளாகப் பரிமாறிக்கொள்ளலாம்: முதலாவது இரண்டாவது, மூன்றாவது நான்காவது, மற்றும் பல. ஒவ்வொரு மாநில பரிமாற்றத்திற்குப் பிறகு, ஒவ்வொரு இரண்டாவது உறுப்பும் சரியான நிலையில் இருக்கும். நீங்கள் O(lg N) வரிசைமாற்றங்களைச் செய்து O(M lg N) நேரத்தைச் செலவிட வேண்டும்.

இருப்பினும், மாற்றத்தை இன்னும் திறமையாக செய்ய முடியும் - நேரியல் அல்ல, ஆனால் நிலையான நேரத்தில். இதைச் செய்ய, முதல் கட்டத்தில், நீங்கள் முதல் உறுப்பின் நிலையை கடைசியாக மாற்ற வேண்டும், இரண்டாவது இறுதி நிலை மற்றும் பல. கடைசி உறுப்பு நிலை சரியான நிலையில் இருக்கும். இப்போது நாம் இரண்டாவது தனிமத்தின் நிலையை கடைசி ஒன்றுடனும், மூன்றாவது ஒன்றை இறுதியான ஒன்றுடனும், மற்றும் பலவற்றுடனும் பரிமாறிக்கொள்ள வேண்டும். இந்த சுற்று பரிமாற்றங்களுக்குப் பிறகு, அனைத்து உறுப்புகளின் நிலைகளும் சரியான நிலையில் இருக்கும். மொத்தத்தில் O(2M) ~ O(1) வரிசைமாற்றங்கள் இருக்கும்.

சுழற்சி என்பது இரண்டு அச்சு சமச்சீர்களின் கலவை என்பதை இன்னும் நினைவில் வைத்திருக்கும் ஒரு கணிதவியலாளரை அத்தகைய தீர்வு ஆச்சரியப்படுத்தாது. மூலம், இது ஒரு மாற்றத்திற்காக அற்பமாக பொதுமைப்படுத்தப்படுகிறது, ஆனால் K <N நிலைகள் மூலம். (எவ்வாறு சரியாக கருத்துகளில் எழுதுங்கள்.)

நீங்கள் புதிர்களை விரும்பினீர்களா? உங்களுக்கு வேறு தீர்வுகள் தெரியுமா? கருத்துகளில் பகிரவும்.

இறுதியில் சில பயனுள்ள இணைப்புகள் இங்கே:

• இன்னும் அறிந்து கொள்ள உள்கட்டமைப்பு வளர்ச்சி விளிம்பில்
• உள் பதிவுகளைப் பார்க்கவும் அறிக்கைகளுடன் ஃப்ளையர் விநியோகிக்கப்பட்ட அமைப்புகள் பற்றி
• வீடியோ விரிவுரைகளின் தொடரைப் பாருங்கள்சாதாரண மக்களுக்கு அசாதாரண வழிமுறைகள்»
• எங்கள் குழுசேர டெலிகிராமில் சேனல்

ஆதாரம்: www.habr.com