Introselect
கணினி அறிவியலில், இன்ட்ரோசெலெக்ட் ("உள்நோக்க தேர்வு" என்பதன் சுருக்கம்) என்பது ஒரு தேர்வு வழிமுறை ஆகும், இது விரைவான தேர்வு மற்றும் மீடியன்களின் கலப்பு ஆகும், இது வேகமான சராசரி செயல்திறன் மற்றும் உகந்த மோசமான செயல்திறனைக் கொண்டுள்ளது. இன்ட்ரோசெலெக்ட் என்பது இன்ட்ரோஸோர்ட் வரிசைப்படுத்தல் வழிமுறையுடன் தொடர்புடையதுஃ இவை அடிப்படை விரைவான தேர்வு மற்றும் விரைவான தொகுப்பு வழிமுறைகளின் ஒத்த சுத்திகரிப்புகளாகும், இதில் அவை இரண்டும் விரைவான வழிமுறையுடன் தொடங்குகின்றன, இது நல்ல சராசரி செயல்திறன் மற்றும் குறைந்த மேல்நிலை ஆகியவற்றைக் கொண்டுள்ளது, ஆனால் விரைவான வழிமுறை விரைவாக முன்னேறவில்லை என்றால் உகந்த மோசமான-வழக்கு வழிமுறைக்கு (அதிக மேல்நிலை கொண்ட) திரும்பும். வேகமான சராசரி செயல்திறன் மற்றும் உகந்த மோசமான செயல்திறன் ஆகிய இரண்டையும் கொண்ட சி + + நிலையான நூலகத்திற்கான பொதுவான வழிமுறைகளை வழங்கும் நோக்கத்துடன் டேவிட் முஸ்ஸர் இரண்டு வழிமுறைகளையும் அறிமுகப்படுத்தினார், இதனால் செயல்திறன் தேவைகளை இறுக்க அனுமதிக்கிறது. இருப்பினும், பெரும்பாலான சி + + நிலையான நூலக செயல்பாடுகளில், ஒரு வித்தியாசமான "இன்ட்ரோசெலெக்ட்" வழிமுறை பயன்படுத்தப்படுகிறது, இது விரைவான தேர்வு மற்றும் ஹீப்ஸெலெக்ட் ஆகியவற்றை ஒருங்கிணைக்கிறது, மேலும் ஓ (என் லாக் என்) இன் மோசமான வழக்கு இயங்கும் நேரத்தைக் கொண்டுள்ளது. சி + + வரைவு தரநிலை, 2022 ஆம் ஆண்டு நிலவரப்படி, மோசமான செயல்திறன் குறித்த தேவைகள் இல்லை, எனவே அத்தகைய தேர்வை அனுமதிக்கிறது. வழிமுறை இன்ட்ரோஸார்ட் விரைவு வரிசையுடன் ஒப்பிடக்கூடிய நடைமுறை செயல்திறனை அடைகிறது, அதே நேரத்தில் ஓ (என் லாக் என்) மோசமான-வழக்கு நடத்தையைப் பாதுகாப்பதன் மூலம் விரைவு வரிசை மற்றும் ஹீப்சோர்ட்டின் கலப்பினத்தை உருவாக்குகிறது. இன்ட்ரோசார்ட் குயிக்சார்ட்டில் தொடங்குகிறது, எனவே குயிக்சார்ட் வேலை செய்தால் அது குயிக்சார்ட்டைப் போன்ற செயல்திறனை அடைகிறது, மேலும் குயிக்சார்ட் விரைவாக முன்னேறவில்லை என்றால் அது மீண்டும் ஹீப்ஸார்ட்டுக்கு (உகந்த மோசமான செயல்திறனைக் கொண்டுள்ளது) விழுகிறது. இதேபோல், இன்ட்ரோசெலெக்ட் விரைவாக தேர்ந்தெடுக்கப்படுவதைப் போன்ற செயல்திறனுடன் மோசமான-வழக்கு நேரியல் தேர்வை அடைய மீடியன்களின் மீடியனுடன் விரைவாக தேர்ந்தெடுக்கப்படுகிறது. இன்ட்ரோசெலெக்ட் விரைவாகத் தேர்ந்தெடுப்பதன் மூலம் நம்பிக்கையுடன் தொடங்குவதன் மூலமும், போதுமான முன்னேற்றம் ஏற்படாமல் பல முறை மீண்டும் மீண்டும் செய்தால் மோசமான-வழக்கு நேரியல்-நேரத் தேர்வு வழிமுறையை (மீடியன்ஸ் வழிமுறையின் ப்ளம்-ஃப்ளாய்ட்-பிராட்-ரிவஸ்ட்-டார்ஜன் மீடியன்) மட்டுமே மாற்றுவதன் மூலமும் செயல்படுகிறது. மாறுதல் உத்தி என்பது வழிமுறையின் முக்கிய தொழில்நுட்ப உள்ளடக்கமாகும். மறுநிகழ்வை நிலையான ஆழத்திற்கு மட்டுப்படுத்துவது போதாது, ஏனெனில் இது வழிமுறையை போதுமான பெரிய பட்டியல்களில் மாற்றும். முஸர் இரண்டு எளிய அணுகுமுறைகளைப் பற்றி விவாதிக்கிறார்ஃ இதுவரை செயலாக்கப்பட்ட உட்பிரிவுகளின் அளவுகளின் பட்டியலைக் கண்காணிக்கவும். எந்த நேரத்திலும் பட்டியலின் அளவை பாதியாக குறைக்காமல் k மறுநிகழ்வு அழைப்புகள் செய்யப்பட்டிருந்தால், சில சிறிய நேர்மறை k க்கு, மோசமான-வழக்கு நேரியல் வழிமுறைக்கு மாறவும். இதுவரை உருவாக்கப்பட்ட அனைத்து பகிர்வுகளின் அளவையும் கூட்டவும். இது பட்டியலின் அளவை சில சிறிய நேர்மறை மாறிலி k ஐ விட அதிகமாக இருந்தால், மோசமான-வழக்கு நேரியல் வழிமுறைக்கு மாறவும். இந்த தொகை ஒரு ஒற்றை அளவிடக்கூடிய மாறியில் கண்காணிக்க எளிதானது. இரண்டு அணுகுமுறைகளும் மறுநிகழ்வு ஆழத்தை k′ log n′ = O (log n) ஆகவும், மொத்த இயங்கும் நேரத்தை O (n) ஆகவும் கட்டுப்படுத்துகின்றன. இன்ட்ரோசெலெக்ட் பற்றிய கூடுதல் ஆராய்ச்சி வரவிருப்பதாக அந்த ஆய்வுக் கட்டுரை பரிந்துரைத்தது, ஆனால் ஆசிரியர் 2007 இல் ஓய்வு பெற்றார், அத்தகைய மேலும் ஆராய்ச்சியை வெளியிடவில்லை. மேலும் காண்க ஃப்ளாய்ட்-ரிவஸ்ட் வழிமுறை குறிப்புகள் தேர்வு வழிமுறைகள்