Kinetic data structure
ஒரு இயக்க தரவு அமைப்பு என்பது தொடர்ந்து நகரும் ஒரு வடிவியல் அமைப்பின் பண்புக்கூறுகளைக் கண்காணிக்கப் பயன்படுத்தப்படும் ஒரு தரவு அமைப்பு ஆகும். எடுத்துக்காட்டாக, ஒரு இயக்க குவிந்த மேலோடு தரவு அமைப்பு நகரும் புள்ளிகளின் குழுவின் குவிந்த மேலோடு பராமரிக்கிறது. இயக்கவியல், அனிமேஷன் அல்லது கணினி கிராபிக்ஸ் ஆகியவற்றில் மோதல் அல்லது தெரிவுநிலை கண்டறிதல் போன்ற தொடர்ச்சியான இயக்கத்தில் இயற்பியல் பொருள்களை உள்ளடக்கிய கணக்கீட்டு வடிவியல் சிக்கல்களால் இயக்கவியல் தரவு கட்டமைப்புகளின் வளர்ச்சி உந்தப்பட்டது. கண்ணோட்டம் இயக்க தரவு கட்டமைப்புகள் ஒரு அறியப்பட்ட பாணியில், நேரத்தின் செயல்பாடாக மாறிவரும் மதிப்புகளின் தொகுப்பு இருக்கும் அமைப்புகளில் பயன்படுத்தப்படுகின்றன. எனவே அமைப்புக்கு சில மதிப்புகள் உள்ளன, ஒவ்வொரு மதிப்புக்கும், அது அறியப்படுகிறது. இயக்க தரவு கட்டமைப்புகள் தற்போதைய மெய்நிகர் நேரத்தில் ஒரு கணினியில் வினவல்களை அனுமதிக்கின்றன, மேலும் இரண்டு கூடுதல் செயல்பாடுகள்ஃ : தற்போதைய நேரத்திற்கு மதிப்பின் பாதையை மாற்றுகிறது. கூடுதல் செயல்பாடுகள் ஆதரிக்கப்படலாம். எடுத்துக்காட்டாக, இயக்க தரவு கட்டமைப்புகள் பெரும்பாலும் புள்ளிகளின் தொகுப்புடன் பயன்படுத்தப்படுகின்றன. இந்த வழக்கில், அமைப்பு பொதுவாக புள்ளிகளை செருகவும் நீக்கவும் அனுமதிக்கிறது. பாரம்பரிய தரவு கட்டமைப்புகளுடன் முரண்பாடு ஒரு இயக்க தரவு அமைப்பு அதில் சேமிக்கப்பட்ட மதிப்புகள் காலப்போக்கில் தொடர்ந்து மாற அனுமதிக்கிறது. கொள்கையளவில், குறிப்பிட்ட நேர இடைவெளியில் புள்ளிகளின் நிலையை மாதிரியாக எடுத்துக்கொள்வதன் மூலமும், ஒவ்வொரு புள்ளியையும் நீக்கி மீண்டும் ஒரு "நிலையான" (பாரம்பரிய) தரவு கட்டமைப்பில் செருகுவதன் மூலமும் இதை தோராயமாக மதிப்பிடலாம். இருப்பினும், அத்தகைய அணுகுமுறை எந்த நேர இடைவெளி பயன்படுத்தப்படுகிறது என்பதைப் பொறுத்து, அதிகப்படியான மாதிரி அல்லது குறைவான மாதிரியால் பாதிக்கப்படக்கூடியது, மேலும் கணக்கீட்டு வளங்களை வீணடிப்பதாகவும் இருக்கலாம். சான்றிதழ்கள் அணுகுமுறை இயக்க தரவு கட்டமைப்புகளை உருவாக்க பின்வரும் பொதுவான அணுகுமுறையைப் பயன்படுத்தலாம்ஃ தற்போதைய நேரத்தில் கணினியில் ஒரு தரவு கட்டமைப்பை சேமிக்கவும். இந்த தரவு அமைப்பு தற்போதைய மெய்நிகர் நேரத்தில் கணினியில் வினவல்களை அனுமதிக்கிறது. சான்றிதழ்களுடன் தரவு கட்டமைப்பை அதிகரிக்கவும். சான்றிதழ்கள் என்பது தரவு அமைப்பு துல்லியமாக இருக்கும் நிபந்தனைகள் ஆகும். சான்றிதழ்கள் அனைத்தும் இப்போது உண்மையாக உள்ளன, மேலும் சான்றிதழ்களில் ஒன்று இனி உண்மையாக இல்லாதபோது மட்டுமே தரவு அமைப்பு துல்லியமாக இருக்காது. ஒவ்வொரு சான்றிதழின் தோல்வியின் நேரத்தையும், அது உண்மையாக இருக்காது நேரத்தையும் கணக்கிடுங்கள். சான்றிதழ்களை முன்னுரிமை வரிசையில் சேமித்து வைக்கவும், அவை தோல்வியடையும் நேரத்தால் குறிக்கப்படுகின்றன நேரத்திற்கு முன்னேற, முன்னுரிமை வரிசையில் இருந்து மிகக் குறைந்த தோல்வியடையும் நேரத்துடன் சான்றிதழைப் பாருங்கள். சான்றிதழ் நேரத்திற்கு முன்பே தோல்வியுற்றால், அதை வரிசையில் இருந்து பாப் செய்து தரவு கட்டமைப்பை சரிசெய்து, அது தோல்வியடையும் நேரத்தில் துல்லியமாக இருக்கும், மேலும் சான்றிதழ்களைப் புதுப்பிக்கவும். முன்னுரிமை வரிசையில் மிகக் குறைந்த தோல்வி நேரத்தைக் கொண்ட சான்றிதழ் காலத்திற்குப் பிறகு தோல்வியடையும் வரை இதை மீண்டும் செய்யவும். முன்னுரிமை வரிசையில் மிகக் குறைந்த தோல்வி நேரத்தைக் கொண்ட சான்றிதழ் காலத்திற்குப் பிறகு தோல்வியுற்றால், அனைத்து சான்றிதழ்களும் சரியான நேரத்தில் இருக்கும், எனவே தரவு அமைப்பு சரியான நேரத்தில் கேள்விகளுக்கு பதிலளிக்க முடியும். நிகழ்வுகளின் வகைகள் சான்றிதழ் தோல்விகள் "நிகழ்வுகள்" என்று குறிப்பிடப்படுகின்றன. நிகழ்வு நிகழும்போது இயக்க தரவு கட்டமைப்பால் பராமரிக்கப்படும் பண்பு மாறவில்லை என்றால் ஒரு நிகழ்வு உள் நிகழ்வாகக் கருதப்படுகிறது. நிகழ்வு நிகழும்போது தரவு கட்டமைப்பால் பராமரிக்கப்படும் பண்பு மாறினால் ஒரு நிகழ்வு வெளிப்புறமாக கருதப்படுகிறது. செயல்திறன் சான்றிதழ்கள் அணுகுமுறையைப் பயன்படுத்தும் போது, செயல்திறனின் நான்கு அளவீடுகள் உள்ளன. ஒரு பல்லுறுப்புக்கோவை செயல்பாடு என்றால் ஒரு அளவு சிறியது என்று நாங்கள் கூறுகிறோம், அல்லது தன்னிச்சையாக சிறியதாக இருந்தால், பொருட்களின் எண்ணிக்கை எங்கேஃ பதிலளிப்பு என்பது தரவு கட்டமைப்பை சரிசெய்யவும், சான்றிதழ் தோல்வியடையும் போது சான்றிதழ்களை அதிகரிக்கவும் தேவைப்படும் மிக மோசமான நேரமாகும். ஒரு புதுப்பிப்புக்கு தேவைப்படும் மோசமான நேர அளவு சிறியதாக இருந்தால் ஒரு இயக்க தரவு அமைப்பு பதிலளிக்கக்கூடியது. இருப்பிடம் என்பது எந்தவொரு ஒரு மதிப்பிலும் சம்பந்தப்பட்ட அதிகபட்ச எண்ணிக்கையிலான சான்றிதழ்கள் ஆகும். நகரும் புள்ளிகளை உள்ளடக்கிய கட்டமைப்புகளுக்கு, இது எந்த ஒரு புள்ளியும் அதிகபட்ச எண்ணிக்கையிலான சான்றிதழ்களில் ஈடுபட்டுள்ளது. எந்த ஒரு மதிப்புடனும் தொடர்புடைய அதிகபட்ச சான்றிதழ்களின் எண்ணிக்கை சிறியதாக இருந்தால் ஒரு இயக்க தரவு அமைப்பு உள்ளூர் ஆகும். சுருக்கமானது எந்த நேரத்திலும் தரவு கட்டமைப்பை மேம்படுத்த பயன்படுத்தப்படும் சான்றிதழ்களின் அதிகபட்ச எண்ணிக்கையாகும். ஒரு இயக்க தரவு அமைப்பு அது பயன்படுத்தும் சான்றிதழ்களின் எண்ணிக்கை அல்லது தன்னிச்சையாக சிறியதாக இருந்தால் அது கச்சிதமானது. (நேரியல் இடத்தை விட ஒரு சிறிய காரணி) செயல்திறன் என்பது தரவு கட்டமைப்பில் "தேவையான மாற்றங்களின்" மோசமான எண்ணிக்கைக்கு கட்டமைப்பை மேம்படுத்தும்போது ஏற்படக்கூடிய மோசமான நிகழ்வுகளின் விகிதமாகும். "தேவையான மாற்றங்கள்" என்பதன் வரையறை சிக்கலைப் பொறுத்தது. எடுத்துக்காட்டாக, நகரும் புள்ளிகளின் தொகுப்பின் இயக்க மேலோட்டத்தை பராமரிக்கும் ஒரு இயக்க தரவு கட்டமைப்பின் விஷயத்தில், தேவையான மாற்றங்களின் எண்ணிக்கை நேரம் முன்னேறும்போது இயக்க மேலோட்டம் மாறும் எண்ணிக்கையாக இருக்கும். இந்த விகிதம் சிறியதாக இருந்தால் ஒரு இயக்க தரவு அமைப்பு திறமையானது என்று கூறப்படுகிறது. பாதைகளின் வகைகள் ஒரு குறிப்பிட்ட இயக்க தரவு கட்டமைப்பின் செயல்திறன் சில வகையான பாதைகளுக்கு பகுப்பாய்வு செய்யப்படலாம். பொதுவாக, பின்வரும் வகையான பாதைகள் கருதப்படுகின்றனஃ அஃபைன்ஃ (நேரியல் செயல்பாடுகள்) எல்லைக்குட்பட்ட-டிகிரி இயற்கணிதம்ஃ (எல்லைக்குட்பட்ட டிகிரியின் பல்லுறுப்புக்கோவை செயல்பாடுகள்) சில நிலையானவற்றிற்கு. போலி-இயற்கணிதம்-எந்தவொரு வட்டி சான்றிதழும் உண்மை மற்றும் தவறான நேரங்களுக்கு இடையில் புரட்டப்படும் வகையில் பாதைகள். எடுத்துக்காட்டுகள் இயக்கவியல் போட்டி இயக்கவியல் வரிசைப்படுத்தப்பட்ட பட்டியல் இயக்கவியல் குவியல் இயக்கவியல் குவிந்த மேலோடு இயக்கவியல் நெருங்கிய ஜோடி இயக்கவியல் குறைந்தபட்சம் பரவியிருக்கும் மரம் இயக்கவியல் யூக்ளிடியன் குறைந்தபட்சம் பரவியிருக்கும் மரம் குறிப்புகள் இயக்கவியல் தரவு கட்டமைப்புகள்