Flashsort
ஃப்ளாஷ்ஸோர்ட் என்பது ஒரே மாதிரியாக விநியோகிக்கப்பட்ட தரவுத் தொகுப்புகளுக்கான நேரியல் கணக்கீட்டு சிக்கல் மற்றும் ஒப்பீட்டளவில் சிறிய கூடுதல் நினைவகத் தேவையைக் காட்டும் ஒரு விநியோக வரிசைப்படுத்தல் வழிமுறையாகும். அசல் படைப்பு 1998 இல் கார்ல்-டீட்ரிச் நியூபர்ட் என்பவரால் வெளியிடப்பட்டது. கருத்து ஃப்ளாஷ்ஸோர்ட் என்பது ஹிஸ்டோகிராம் வரிசையின் ஒரு திறமையான இடத்தில் செயல்படுத்தல் ஆகும், இது ஒரு வகை வாளி வகை. இது ஒவ்வொரு உள்ளீட்டு கூறுகளையும் ஒரு வாளியில் ஒதுக்குகிறது, வாளிகளை சரியான வரிசையில் வைக்க உள்ளீட்டை திறம்பட மறுசீரமைக்கிறது, பின்னர் ஒவ்வொரு வாளியையும் வரிசைப்படுத்துகிறது. அசல் வழிமுறை ஒரு உள்ளீட்டு வரிசையை பின்வருமாறு வரிசைப்படுத்துகிறதுஃ உள்ளீடு அல்லது முன்னுரிமை அறிவுக்கு மேல் முதல் பாஸைப் பயன்படுத்தி, குறைந்தபட்ச மற்றும் அதிகபட்ச வரிசைப்படுத்தல் விசைகளைக் கண்டறியவும். நேர்கோட்டில் வரம்பை வாளிகளாகப் பிரிக்கவும். ஒவ்வொரு வாளியிலும் விழும் உறுப்புகளின் எண்ணிக்கையை எண்ணி, உள்ளீட்டைக் கடந்து செல்லுங்கள். (நியூபர்ட் வாளிகளை "வகுப்புகள்" என்றும் அவற்றின் வாளிகளுக்கு கூறுகளை ஒதுக்குவதை "வகைப்பாடு" என்றும் அழைக்கிறார்.) ஒவ்வொரு வாளியிலும் உள்ள உறுப்புகளின் எண்ணிக்கையை ஒரு முன்னொட்டு தொகையாக மாற்றவும், அங்கு வாளியில் உள்ள உறுப்புகளின் எண்ணிக்கை அல்லது அதற்கும் குறைவாக இருக்கும். (மற்றும்.) உள்ளீட்டை மறுசீரமைக்கவும், இதனால் ஒவ்வொரு வாளியின் அனைத்து கூறுகளும் எந்த இடத்தில் சேமிக்கப்படுகின்றன. செருகும் வரிசையைப் பயன்படுத்தி ஒவ்வொரு வாளியையும் வரிசைப்படுத்துங்கள். படி 1-3 மற்றும் 6 எந்த வாளி வகைக்கும் பொதுவானவை, மேலும் வாளி வகைக்கு பொதுவான நுட்பங்களைப் பயன்படுத்தி மேம்படுத்தப்படலாம். குறிப்பாக, வாளிகள் தோராயமாக சம அளவு (ஒவ்வொன்றும் கூறுகள்) இருக்க வேண்டும், இலட்சியம் அளவுகளாகப் பிரிக்கப்பட வேண்டும். அடிப்படை வழிமுறை ஒரு நேரியல் இடைக்கணிப்பு வகை என்றாலும், உள்ளீட்டு விநியோகம் சீரானதல்ல என்று தெரிந்தால், ஒரு நேரியல் அல்லாத பிரிவு இந்த இலட்சியத்தை மிகவும் நெருக்கமாக தோராயமாக மதிப்பிடும். அதேபோல், இறுதி வரிசைப்படுத்தல் ஒரு தொடர்ச்சியான ஃபிளாஷ் வரிசைப்படுத்தல் உட்பட பல நுட்பங்களில் ஏதேனும் ஒன்றைப் பயன்படுத்தலாம். ஃபிளாஷ் வரிசையை வேறுபடுத்துவது படி 5: கூடுதல் நினைவகத்தின் சொற்களை மட்டுமே பயன்படுத்தி ஒவ்வொரு வாளியின் கூறுகளையும் சரியான ஒப்பீட்டு வரிசையில் ஒன்றாக சேகரிப்பதற்கான ஒரு திறமையான இடத்திலுள்ள வழிமுறை. நினைவக திறமையான அமலாக்கம் ஃப்ளாஷ்ஸோர்ட் மறுசீரமைப்பு கட்டம் சுழற்சிகளில் செயல்படுகிறது. கூறுகள் "வகைப்படுத்தப்படாதவை" என்று தொடங்கி, பின்னர் சரியான வாளிக்கு நகர்த்தப்பட்டு "வகைப்படுத்தப்பட்டவை" என்று கருதப்படுகின்றன. அடிப்படை செயல்முறை என்னவென்றால், ஒரு வகைப்படுத்தப்படாத உறுப்பைத் தேர்ந்தெடுப்பது, அதன் சரியான வாளியைக் கண்டுபிடிப்பது, அதை அங்கு வகைப்படுத்தப்படாத உறுப்புடன் பரிமாறிக்கொள்வது (இது இருக்க வேண்டும், ஏனென்றால் ஒவ்வொரு வாளியின் அளவையும் நாம் நேரத்திற்கு முன்பே கணக்கிட்டோம்), அதை வகைப்படுத்தப்பட்டதாகக் குறிக்கவும், பின்னர் மறுபரிசீலனை செய்யுங்கள். இறுதியில், உறுப்பு அதனுடன் பரிமாறப்பட்டு சுழற்சி முடிவடைகிறது. ஒரு வாளிக்கு இரண்டு (சொல் அளவிலான) மாறிகளைப் பயன்படுத்தி விவரங்களைப் புரிந்துகொள்வது எளிது. புத்திசாலித்தனமான பகுதி அந்த மாறிகளில் ஒன்றை அகற்றுவதாகும், இது இரண்டு மடங்கு பல வாளிகளைப் பயன்படுத்த அனுமதிக்கிறது, எனவே இறுதி வரிசைப்படுத்தலுக்கு பாதி நேரம் செலவிடப்படுகிறது. ஒரு வாளிக்கு இரண்டு மாறிகள் மூலம் அதைப் புரிந்துகொள்ள, கூடுதல் சொற்களின் இரண்டு வரிசைகள் உள்ளன என்று வைத்துக்கொள்வோம்ஃ வாளி (மற்றும்) இன் (நிலையான) மேல் வரம்பு, அதே நேரத்தில் வாளியில் ஒரு (அசையும்) குறியீடு, எனவே. ஒவ்வொரு வாளியும் ஒரு வகைப்படுத்தப்படாத முன்னொட்டு (அவற்றின் இலக்கு வாளிகளுக்கு இன்னும் நகர்த்தப்படவில்லை) மற்றும் ஒரு வகைப்படுத்தப்பட்ட பின்னொட்டு (இவை அனைத்தும் சரியான வாளியில் உள்ளன, மீண்டும் நகர்த்தப்படாது) என பிரிக்கப்படும் சுழற்சியை நாம் பராமரிக்கிறோம். ஆரம்பத்தில் மற்றும் அனைத்து கூறுகளும் வகைப்படுத்தப்படவில்லை. வரிசைப்படுத்தல் தொடரும்போது, அனைத்து உறுப்புகளும் சரியான வாளியாக வகைப்படுத்தப்படும் வரை அவை குறைக்கப்படும். ஒவ்வொரு சுற்றும் முதல் முழுமையற்ற வகைப்படுத்தப்பட்ட வாளியைக் கண்டுபிடிப்பதன் மூலமும், அந்த வாளியில் முதல் வகைப்படுத்தப்படாத உறுப்பை எடுத்துக்கொள்வதன் மூலமும் தொடங்குகிறது. (நியூபர்ட் இதை "சைக்கிள் தலைவர்" என்று அழைக்கிறார்.) ஒரு தற்காலிக மாறிக்கு நகலெடுத்து மீண்டும் செய்யவும்ஃ எந்த வாளிக்கு சொந்தமானது என்பதைக் கணக்கிடுங்கள். சேமிக்கப்படும் இடமாக இருக்கட்டும். உடன் பரிமாற்றம், அதாவது. முந்தைய மதிப்பைப் பெறும்போது சேமிப்பதன் மூலம் இடம்பெயர்ந்தது. இப்போது சரியாக வகைப்படுத்தப்பட்ட உண்மையை பிரதிபலிக்கும் சரிவு. இருந்தால், இந்த வளையத்தை புதியதுடன் மறுதொடக்கம் செய்யுங்கள். இந்த சுற்று முடிந்துவிட்டால், ஒரு புதிய முதல் வகைப்படுத்தப்படாத உறுப்பைக் கண்டறியவும். மேலும் வகைப்படுத்தப்படாத கூறுகள் இல்லாதபோது, வாளிகளில் விநியோகம் நிறைவடைகிறது. இந்த வழியில் ஒரு வாளிக்கு இரண்டு மாறிகளுடன் செயல்படுத்தப்படும்போது, ஒவ்வொரு சுற்றின் தொடக்க புள்ளியின் தேர்வும் உண்மையில் தன்னிச்சையானது; வகைப்படுத்தப்படாத எந்த உறுப்பும் சுழற்சித் தலைவராகப் பயன்படுத்தப்படலாம். ஒரே தேவை என்னவென்றால், சுழற்சி தலைவர்களை திறம்பட கண்டுபிடிக்க முடியும். முந்தைய விளக்கம் சுழற்சி தலைவர்களைக் கண்டுபிடிக்க பயன்படுத்துகிறது என்றாலும், உண்மையில் அது இல்லாமல் செய்ய முடியும், முழு-சொல் வரிசையையும் அகற்ற அனுமதிக்கிறது. (விநியோகம் முடிந்த பிறகு, வாளி எல்லைகளை இங்கு காணலாம்.) நாம் அனைத்து கூறுகளையும் வகைப்படுத்தியுள்ளோம் என்று வைத்துக்கொள்வோம், மேலும் ஒரு சாத்தியமான புதிய சுழற்சி தலைவராக கருதுகிறோம். அதன் இலக்கு வாளியை கணக்கிடுவது எளிது. சுழற்சி மாறாததன் மூலம், அது வகைப்படுத்தப்படுகிறது என்றால், மற்றும் அந்த வரம்பிற்கு வெளியே இருந்தால் வகைப்படுத்தப்படவில்லை. முதல் சமத்துவமின்மையை சோதிப்பது எளிது, ஆனால் இரண்டாவது மதிப்பு தேவை என்று தோன்றுகிறது. அனைத்து உறுப்புகளும் வகைப்படுத்தப்பட்டுள்ளன என்ற தூண்டல் கருதுகோள் அதைக் குறிக்கிறது, எனவே இரண்டாவது சமத்துவமின்மையை சோதிக்க வேண்டிய அவசியமில்லை. வாளி எந்த நிலையில் விழுகிறது என்பதைக் கவனியுங்கள். அதாவது,. தூண்டல் கருதுகோளின்படி, கீழே உள்ள அனைத்து கூறுகளும், அனைத்து வாளிகளையும் உள்ளடக்கியது, முற்றிலும் வகைப்படுத்தப்பட்டுள்ளன. ஐ. இ. அந்த வாளிகளில் உள்ள எந்த உறுப்புகளும் மீதமுள்ள வரிசையில் இல்லை. எனவே, அது சாத்தியமில்லை. மீதமுள்ள ஒரே வழக்கு, இது குறிக்கிறது, கியூ. இ. டி. இதை இணைத்து, ஃப்ளாஷ்ஸோர்ட் விநியோக வழிமுறை மேலே விவரிக்கப்பட்டுள்ளபடி தொடங்குகிறது மற்றும். பின்னர் தொடருங்கள்ஃ விநியோகம் முடிந்துவிட்டால். கொடுக்கப்பட்டிருந்தால், அது எந்த வாளிக்கு சொந்தமானது என்பதைக் கணக்கிடுங்கள். இருந்தால், அது வகைப்படுத்தப்படவில்லை. அதை ஒரு தற்காலிக மாறியை நகலெடுத்துஃ சேமிக்கப்படும் இடமாக இருக்கட்டும். உடன் பரிமாற்றம், அதாவது. முந்தைய மதிப்பைப் பெறும்போது சேமிப்பதன் மூலம் இடம்பெயர்ந்தது. இப்போது சரியாக வகைப்படுத்தப்பட்ட உண்மையை பிரதிபலிக்கும் சரிவு. அப்படியானால், அந்த வாளியை கணக்கிடுங்கள் மற்றும் இந்த (உள்) வளையத்தை புதியதுடன் மறுதொடக்கம் செய்யுங்கள். இப்போது சரியாக வகைப்படுத்தப்பட்டுள்ளது. (வெளிப்புற) வளையத்தை அதிகரிக்கவும் மறுதொடக்கம் செய்யவும். நினைவகத்தை சேமிக்கும் போது, ஃப்ளாஷ்ஸோர்ட் ஏற்கனவே வகைப்படுத்தப்பட்ட பல கூறுகளுக்கு வாளியை மறுபரிசீலனை செய்யும் குறைபாட்டைக் கொண்டுள்ளது. இது ஏற்கனவே ஒரு உறுப்புக்கு இரண்டு முறை செய்யப்படுகிறது (ஒரு முறை வாளி-எண்ணும் கட்டத்தில் மற்றும் இரண்டாவது முறையாக ஒவ்வொரு உறுப்பையும் நகர்த்தும்போது), ஆனால் முதல் வகைப்படுத்தப்படாத உறுப்பைத் தேடுவதற்கு பெரும்பாலான உறுப்புகளுக்கு மூன்றாவது கணக்கீடு தேவைப்படுகிறது. எளிய நேரியல் இடைக்கணிப்பை விட மிகவும் சிக்கலான சூத்திரத்தைப் பயன்படுத்தி வாளிகள் ஒதுக்கப்பட்டால் இது விலை உயர்ந்ததாக இருக்கும். ஒரு மாறுபாடு ஒரு முடிக்கப்படாத வாளியில் கடைசி வகைப்படுத்தப்படாத உறுப்பை சுழற்சி தலைவராக எடுத்துக்கொள்வதன் மூலம் கணக்கீடுகளின் எண்ணிக்கையை கிட்டத்தட்ட அதிகபட்சமாக குறைக்கிறதுஃ முதல் முழுமையற்ற வகைப்படுத்தப்பட்ட வாளியை அடையாளம் காணும் ஒரு மாறியை பராமரிக்கவும். தொடங்குங்கள், எப்போது விநியோகம் நிறைவடையும். விடுங்கள். என்றால், இந்த வளையத்தை அதிகரித்து மறுதொடக்கம் செய்யுங்கள். (.) எந்த வாளிக்குச் சொந்தமானது என்பதைக் கணக்கிடுங்கள். என்றால், பின்னர் மற்றும் நாம் வாளி முடிந்துவிட்டது. இந்த வளையத்தை அதிகரித்து மறுதொடக்கம் செய்யுங்கள். என்றால், வகைப்பாடு அற்பமானது. இந்த சுழற்சியை குறைத்து மறுதொடக்கம் செய்யுங்கள். இருந்தால், அது வகைப்படுத்தப்படவில்லை. முந்தைய வழக்கைப் போலவே அதே வகைப்பாடு சுழற்சியைச் செய்யுங்கள், பின்னர் இந்த சுழற்சியை மறுதொடக்கம் செய்யுங்கள். பெரும்பாலான உறுப்புகளின் வாளிகள் இரண்டு முறை மட்டுமே கணக்கிடப்படுகின்றன, ஒவ்வொரு வாளியிலும் உள்ள இறுதி உறுப்பைத் தவிர, இது பின்வரும் வாளியின் முடிவைக் கண்டறியப் பயன்படுகிறது. வகைப்படுத்தப்படாத கூறுகளின் எண்ணிக்கையை பராமரிப்பதன் மூலமும், அது பூஜ்ஜியத்தை அடையும் போது நிறுத்துவதன் மூலமும் மேலும் ஒரு சிறிய குறைப்பை அடைய முடியும். பக்கெட் வரம்புகளை சேமிப்பதற்கான துணை திசையன் மற்றும் பயன்படுத்தப்படும் பிற மாறிகளின் நிலையான எண்ணிக்கை மட்டுமே கூடுதல் நினைவகத் தேவைகள் ஆகும். மேலும், ஒவ்வொரு உறுப்பும் ஒரு முறை மட்டுமே நகர்த்தப்படுகிறது (ஒரு தற்காலிக இடையக வழியாக, எனவே இரண்டு நகர்வு செயல்பாடுகள்). இருப்பினும், இந்த நினைவக செயல்திறன் வரிசை சீரற்ற முறையில் அணுகப்படும் குறைபாட்டுடன் வருகிறது, எனவே முழு வரிசையையும் விட சிறிய தரவு தற்காலிக சேமிப்பைப் பயன்படுத்திக் கொள்ள முடியாது. அனைத்து பக்கெட் வகைகளையும் போலவே, செயல்திறனும் பக்கெட்டுகளின் சமநிலையைப் பொறுத்தது. ஒரு சீரான தரவு தொகுப்பின் சிறந்த விஷயத்தில், ஒவ்வொரு வாளியும் தோராயமாக ஒரே அளவாக இருக்கும். உள்ளீட்டு அளவில் வாளிகளின் எண்ணிக்கை நேரியல் என்றால், ஒவ்வொரு வாளியும் ஒரு நிலையான அளவைக் கொண்டுள்ளது, எனவே செருகும் வரிசை போன்ற ஒரு வழிமுறையுடன் ஒரு வாளியை வரிசைப்படுத்துவது சிக்கலானது. எனவே இறுதி செருகும் வகைகளின் இயங்கும் நேரம். ஒரு மதிப்பைத் தேர்ந்தெடுப்பது, வாளிகளின் எண்ணிக்கை, கூறுகளை வகைப்படுத்த செலவழித்த நேரம் (உயர்) மற்றும் இறுதி செருகல் வரிசைப்படுத்தல் படியில் (குறைந்த) செலவழித்த நேரம். எடுத்துக்காட்டாக, அதற்கு விகிதாசாரமாக தேர்ந்தெடுக்கப்பட்டால், இறுதி செருகல் வகைகளின் இயங்கும் நேரம் எனவே. கிட்டத்தட்ட அனைத்து கூறுகளும் ஒரு சில வாளிகளில் இருக்கும் மோசமான சூழ்நிலைகளில், வழிமுறையின் சிக்கலானது இறுதி வாளி-வரிசைப்படுத்தும் முறையின் செயல்திறனால் வரையறுக்கப்படுகிறது, எனவே தரக்குறைவாகிறது. வழிமுறையின் மாறுபாடுகள் ஒரு குறிப்பிட்ட அளவு வரம்பை மீறும் வாளிகளில் விரைவு அல்லது மறுசுழற்சி ஃப்ளாஷ்ஸோர்ட் போன்ற சிறந்த செயல்திறன் கொண்ட வகைகளைப் பயன்படுத்துவதன் மூலம் மோசமான செயல்திறனை மேம்படுத்துகின்றன. ஒரே மாதிரியாக விநியோகிக்கப்பட்ட சீரற்ற தரவுகளுடன், ஃப்ளாஷ்ஸோர்ட் அனைவருக்கும் ஹீப்சார்ட்டை விட வேகமாகவும், விரைவானதை விட வேகமாகவும் இருக்கும். இது வேகமான வேகத்தை விட இரண்டு மடங்கு வேகமாக மாறுகிறது. இந்த அளவீடுகள் 1990 களின் பிற்பகுதியில் எடுக்கப்பட்டன என்பதை நினைவில் கொள்க, நினைவக படிநிலைகள் தற்காலிக சேமிப்பை மிகவும் குறைவாக சார்ந்திருந்தன. ஃப்ளாஷ்ஸோர்ட் அதன் வகைப்பாட்டு செயல்பாட்டில் செயல்படும் இன் சிட்டு வரிசைமாற்றத்தின் காரணமாக, ஃப்ளாஷ்ஸோர்ட் நிலையானதாக இல்லை. நிலைத்தன்மை தேவைப்பட்டால், இரண்டாவது வரிசையைப் பயன்படுத்த முடியும், எனவே கூறுகளை தொடர்ச்சியாக வகைப்படுத்தலாம். இருப்பினும், இந்த விஷயத்தில், வழிமுறைக்கு கூடுதல் நினைவகம் தேவைப்படும். குறிப்புகளை வரிசைப்படுத்துவதை விட தேடலுக்காக உருப்படிகளின் விநியோகத்தைப் பயன்படுத்தி இன்டர்போலேஷன் தேடலை மேலும் காண்க வெளிப்புற இணைப்புகள் பெரிய இணையான இயந்திரங்களில் சீரற்ற வரிசைப்படுத்தலின் அமலாக்கங்கள் (1992) இணையான வழிமுறைகளின் அமலாக்கம் (1992) ஃப்ளாஷ்ஸோர்ட் வரிசைப்படுத்தல் வழிமுறைகளின் காட்சிப்படுத்தல்