Retroactive data structure
கணினி அறிவியலில் ஒரு பின்னோக்கிய தரவு அமைப்பு என்பது ஒரு தரவு அமைப்பு ஆகும், இது கட்டமைப்பில் நிகழ்த்தப்பட்ட செயல்பாடுகளின் வரிசையில் திறமையான மாற்றங்களை ஆதரிக்கிறது. இந்த மாற்றங்கள் கடந்த காலத்தில் சில நேரங்களில் நிகழ்த்தப்பட்ட ஒரு செயல்பாட்டை பின்னோக்கி செருகுதல், நீக்குதல் அல்லது புதுப்பித்தல் ஆகியவற்றின் வடிவத்தை எடுக்கலாம். பின்னோக்கிய தரவு கட்டமைப்புகளின் சில பயன்பாடுகள் நிஜ உலகில், செயல்பாடுகளின் வரிசையிலிருந்து கடந்தகால செயல்பாட்டை மாற்றியமைக்க விரும்பும் பல நிகழ்வுகள் உள்ளன. சாத்தியமான பயன்பாடுகளில் சில கீழே பட்டியலிடப்பட்டுள்ளனஃ பிழை திருத்தம்ஃ தரவின் தவறான உள்ளீடு. தரவு சரிசெய்யப்பட வேண்டும் மற்றும் தவறான தரவின் அனைத்து இரண்டாம் நிலை விளைவுகளும் அகற்றப்பட வேண்டும். மோசமான தரவுஃ பெரிய அமைப்புகளைக் கையாளும் போது, குறிப்பாக அதிக அளவு தானியங்கி தரவு பரிமாற்றத்தை உள்ளடக்கியது, இது அசாதாரணமானது அல்ல. எடுத்துக்காட்டாக, வானிலை நெட்வொர்க் செயலிழப்புகளுக்கான சென்சார்களில் ஒன்று மற்றும் குப்பைத் தரவு அல்லது தவறான தரவைப் புகாரளிக்கத் தொடங்குகிறது என்று வைத்துக்கொள்வோம். ஒட்டுமொத்த அமைப்பில் மோசமான தரவு ஏற்படுத்திய அனைத்து விளைவுகளுடன் சென்சார் செயலிழந்ததால் அது உருவாக்கிய அனைத்து தரவுகளையும் அகற்றுவதே சிறந்த தீர்வாக இருக்கும். மீட்புஃ ஒரு வன்பொருள் சென்சார் சேதமடைந்துள்ளது, ஆனால் இப்போது சரிசெய்யப்பட்டுள்ளது மற்றும் தரவை சென்சாரில் இருந்து படிக்க முடியும் என்று வைத்துக்கொள்வோம். சென்சார் முதலில் ஒருபோதும் சேதமடையவில்லை என்பது போல தரவை மீண்டும் கணினியில் செருக முடியும் என்று நாங்கள் விரும்புகிறோம். கடந்த காலத்தை கையாளுதல்ஃ சேதக் கட்டுப்பாடு நிகழ்வுகளில் கடந்த காலத்தை மாற்றுவது உதவியாக இருக்கும், மேலும் கடந்த காலத்தை வேண்டுமென்றே கையாளுவதற்காக முன்கூட்டிய தரவு கட்டமைப்புகள் வடிவமைக்கப்பட்டுள்ளன. நேரம் ஒரு இடஞ்சார்ந்த பரிமாணமாக நேரத்தை ஒரு கூடுதல் இடஞ்சார்ந்த பரிமாணமாக கருத முடியாது. இதை விளக்குவதற்கு, காலத்தின் பரிமாணத்தை ஒரு இடைவெளி அச்சில் வரைகிறோம் என்று வைத்துக்கொள்வோம். இடஞ்சார்ந்த நேர பரிமாணத்தைச் சேர்க்க நாம் பயன்படுத்தும் தரவு அமைப்பு ஒரு மினி-ஹீப் ஆகும். y அச்சு குவியலுக்குள் உள்ள பொருட்களின் முக்கிய மதிப்புகளைக் குறிக்கட்டும் மற்றும் x அச்சு இடஞ்சார்ந்த நேர பரிமாணமாகும். பல செருகல்கள் மற்றும் நீக்குதல்-குறைந்தபட்ச செயல்பாடுகளுக்குப் பிறகு (அனைத்தும் மறுபயன்பாட்டுடன் செய்யப்படாதவை) நமது குறைந்தபட்ச-குவியல் படம் 1 இல் உள்ளதைப் போல தோன்றும். இப்போது செயல்பாட்டு பட்டியலின் தொடக்கத்தில் பூஜ்ஜியத்தை பின்னோக்கி செருகுகிறோம் என்று வைத்துக்கொள்வோம். நமது மின்-ஹீப் படம் 2 இல் உள்ளதைப் போல தோன்றும். ஒற்றை செயல்பாடு ஒரு அடுக்கு விளைவை எவ்வாறு உருவாக்குகிறது என்பதைக் கவனியுங்கள், இது முழு தரவு கட்டமைப்பையும் பாதிக்கிறது. எனவே நேரத்தை ஒரு இடஞ்சார்ந்த பரிமாணமாக வரைய முடியும் என்றாலும், நேரத்துடன் தொடர்புடைய செயல்பாடுகள் சார்ந்திருப்பதை உருவாக்குகின்றன, அவை நேரத்தைப் பொறுத்தவரை மாற்றங்கள் செய்யப்படும்போது ஒரு சிற்றலை கொண்டுள்ளன. விடாமுயற்சியுடனான ஒப்பீடு முதல் பார்வையில் ஒரு பின்னோக்கிய தரவு கட்டமைப்புகளின் கருத்து நிலையான தரவு கட்டமைப்புகளுடன் மிகவும் ஒத்ததாகத் தெரிகிறது, ஏனெனில் அவை இரண்டும் நேரத்தின் பரிமாணத்தை கணக்கில் எடுத்துக்கொள்கின்றன. தொடர்ச்சியான தரவு கட்டமைப்புகளுக்கும் பின்னோக்கிய தரவு கட்டமைப்புகளுக்கும் இடையிலான முக்கிய வேறுபாடு என்னவென்றால், அவை நேரத்தின் கூறுகளை எவ்வாறு கையாளுகின்றன என்பதுதான். ஒரு நிலையான தரவு அமைப்பு ஒரு தரவு கட்டமைப்பின் பல பதிப்புகளை பராமரிக்கிறது மற்றும் தரவு கட்டமைப்பின் மற்றொரு பதிப்பை உருவாக்க ஒரு பதிப்பில் செயல்பாடுகளைச் செய்யலாம். ஒவ்வொரு செயல்பாடும் ஒரு புதிய பதிப்பை உருவாக்குவதால், ஒவ்வொரு பதிப்பும் மாற்ற முடியாத ஒரு காப்பகமாக மாறுகிறது (அதிலிருந்து புதிய பதிப்புகளை மட்டுமே உருவாக்க முடியும்). ஒவ்வொரு பதிப்பும் மாறாது என்பதால், ஒவ்வொரு பதிப்பிற்கும் இடையிலான சார்பும் மாறாது. ரெட்ரோஆக்டிவ் தரவு கட்டமைப்புகளில் முந்தைய பதிப்புகளில் நேரடியாக மாற்றங்களைச் செய்ய அனுமதிக்கிறோம். ஒவ்வொரு பதிப்பும் இப்போது ஒன்றையொன்று சார்ந்திருப்பதால், ஒரு மாற்றம் அனைத்து பிற்கால பதிப்புகளிலும் மாற்றங்களின் சிற்றலைகளை ஏற்படுத்தும். படம் 1 மற்றும் 2 இந்த சிற்றலை விளைவுக்கு ஒரு உதாரணத்தைக் காட்டுகின்றன. வரையறை எந்தவொரு தரவு கட்டமைப்பும் ஒரு முந்தைய செயல்பாட்டு அமைப்பில் மறுசீரமைக்கப்படலாம். பொதுவாக தரவு அமைப்பு ஒரு குறிப்பிட்ட காலப்பகுதியில் செய்யப்பட்ட தொடர்ச்சியான புதுப்பிப்புகள் மற்றும் கேள்விகளை உள்ளடக்கியது. U = [ut1, ut2, ut3,., utm] என்பது t1 முதல் tm வரையிலான புதுப்பிப்பு செயல்பாடுகளின் வரிசையாக இருக்கட்டும், அதாவது t1 <t2 <. இங்கே அனுமானம் என்னவென்றால், ஒரு குறிப்பிட்ட நேரத்திற்கு அதிகபட்சம் ஒரு செயல்பாட்டைச் செய்ய முடியும் t. தற்போதைய நேரத்தில் புதுப்பிப்பு மற்றும் வினவல் செயல்பாடுகளைச் செய்ய முடிந்தால், கடந்த காலத்தில் செருகுதல் மற்றும் நீக்குதல் செயல்பாடுகளை ஆதரிக்க முடிந்தால், தரவு கட்டமைப்பை ஓரளவு ரெட்ரோஆக்டிவ் என்று வரையறுக்கிறோம். எனவே ஓரளவு ரெட்ரோஆக்டிவ் செய்ய நாம் பின்வரும் செயல்பாடுகளில் ஆர்வமாக உள்ளோம்ஃ (t, u) ஐச் செருகவும்ஃ t நேரத்தில் U பட்டியலில் ஒரு புதிய செயல்பாட்டை u ஐச் செருகவும். நீக்கவும் (t): U பட்டியலில் இருந்து t நேரத்தில் செயல்பாட்டை நீக்கவும். மேற்கூறிய ரெட்ரோஆக்டிவ் செயல்பாடுகளைப் பொறுத்தவரை, ஒரு நிலையான செருகும் செயல்பாடு இப்போது செருகல் (t, "செருகல் (x)") வடிவமாக இருக்கும். தரவு கட்டமைப்பின் செயல்பாட்டு வரலாற்றில் அனைத்து முன்கூட்டிய மாற்றங்களும் செயல்பாட்டின் போது தற்போது வரை அனைத்து செயல்பாடுகளையும் பாதிக்கக்கூடும். எடுத்துக்காட்டாக, நம்மிடம் ti-1 <t <ti + 1 இருந்தால், செருகவும் (t, செருகவும் (x)) என்பது ஓபி-1 மற்றும் ஓபி + 1 செயல்பாடுகளுக்கு இடையில் ஒரு புதிய செயல்பாட்டை, ஆப், வைக்கும். தரவு கட்டமைப்பின் தற்போதைய நிலை (அதாவது. : தற்போதைய நேரத்தில் தரவு அமைப்பு) பின்னர் செயல்பாடுகள் ஓபிஐ-1, ஓபி மற்றும் ஓபிஐ + 1 போன்ற ஒரு நிலையில் இருக்கும், இவை அனைத்தும் ஒரு வரிசையில் நிகழ்ந்தன, செயல்பாடு ஆப் எப்போதும் இருப்பதைப் போல. ஒரு காட்சி உதாரணத்திற்கு படம் 1 மற்றும் 2 ஐப் பார்க்கவும். ஓரளவு ரெட்ரோஆக்டிவ் செயல்பாடுகளுக்கு கூடுதலாக, கடந்த காலத்தைப் பற்றிய கேள்விகளைச் செய்ய ஒருவரை அனுமதித்தால், தரவு கட்டமைப்பை முழுமையாக ரெட்ரோஆக்டிவ் என்று வரையறுக்கிறோம். ஓரளவு ரெட்ரோஆக்டிவ் மாதிரியில் நிலையான செயல்பாட்டு செருகல் (x) எவ்வாறு செருகப்படுகிறது (t, "செருகல் (x)") என்பதைப் போலவே, முழு ரெட்ரோஆக்டிவ் மாதிரியில் செயல்பாட்டு வினவல் (x) இப்போது வினவல் (t, வினவல் (x)) வடிவத்தைக் கொண்டுள்ளது. ரெட்ரோஆக்டிவ் ரன்னிங் டைம்ஸ் ரெட்ரோஆக்டிவ் டேட்டா ஸ்ட்ரக்சர்களின் ரன்னிங் டைம் என்பது கட்டமைப்பில் நிகழ்த்தப்பட்ட செயல்பாடுகளின் எண்ணிக்கை, m, ரெட்ரோஆக்டிவ் செயல்பாடு செய்யப்படுவதற்கு முன்பு நிகழ்த்தப்பட்ட செயல்பாடுகளின் எண்ணிக்கை மற்றும் எந்த நேரத்திலும் கட்டமைப்பில் உள்ள அதிகபட்ச உறுப்புகளின் எண்ணிக்கையை அடிப்படையாகக் கொண்டது. தானியங்கி ரெட்ரோ-செயல்பாடு தரவு கட்டமைப்புகளைப் பொறுத்தவரை தானியங்கி ரெட்ரோ-செயல்பாடு தொடர்பான முக்கிய கேள்வி என்னவென்றால், எந்தவொரு தரவு கட்டமைப்பையும் திறமையான ரெட்ரோஆக்டிவ் எதிர்ப்பாளராக மாற்றக்கூடிய ஒரு பொதுவான நுட்பம் உள்ளதா இல்லையா என்பதுதான். ஒரு எளிய அணுகுமுறை என்னவென்றால், பயன்படுத்தப்பட வேண்டிய ரெட்ரோஆக்டிவ் செயல்பாட்டிற்கு முன்னர் கட்டமைப்பில் செய்யப்பட்ட அனைத்து மாற்றங்களுக்கும் ஒரு ரோல்-பேக் செய்ய வேண்டும். தரவு கட்டமைப்பை பொருத்தமான நிலைக்கு மாற்றியவுடன், நாம் விரும்பிய மாற்றத்தைச் செய்ய ரெட்ரோஆக்டிவ் செயல்பாட்டைப் பயன்படுத்தலாம். மாற்றம் செய்யப்பட்டவுடன், தரவு கட்டமைப்பை அதன் புதிய நிலைக்கு கொண்டு வருவதற்கு முன்பு நாம் திரும்பப் பெற்ற அனைத்து மாற்றங்களையும் மீண்டும் பயன்படுத்த வேண்டும். இது எந்தவொரு தரவு கட்டமைப்பிற்கும் வேலை செய்ய முடியும் என்றாலும், இது பெரும்பாலும் திறமையற்றது மற்றும் வீணானது, குறிப்பாக நாம் திரும்பப் பெற வேண்டிய மாற்றங்களின் எண்ணிக்கை அதிகமாக இருக்கும்போது. ஒரு திறமையான ரெட்ரோஆக்டிவ் தரவு கட்டமைப்பை உருவாக்க, வேகத்தை எங்கு உணர முடியும் என்பதை தீர்மானிக்க கட்டமைப்பின் பண்புகளை நாம் பார்க்க வேண்டும். எனவே எந்தவொரு தரவு கட்டமைப்பையும் ஒரு திறமையான ரெட்ரோஆக்டிவ் எதிர்ப்பாளராக மாற்றுவதற்கான பொதுவான வழி இல்லை. எரிக் டி. டெமெய்ன், ஜான் ஐகோனோ மற்றும் ஸ்டீபன் லாங்கர்மேன் ஆகியோர் இதை நிரூபிக்கின்றனர். மேலும் காண்கஃ நிலையான தரவு அமைப்பு குறிப்புகள் தரவு கட்டமைப்புகள்