Kinetic data structure
एक गतिज डेटा संरचना एक डेटा संरचना है जिसका उपयोग एक ज्यामितीय प्रणाली की विशेषता को ट्रैक करने के लिए किया जाता है जो लगातार आगे बढ़ रही है। उदाहरण के लिए, एक गतिज उत्तल पतवार डेटा संरचना गतिशील बिंदुओं के एक समूह के उत्तल पतवार को बनाए रखती है। गतिज डेटा संरचनाओं का विकास निरंतर गति में भौतिक वस्तुओं से जुड़ी कम्प्यूटेशनल ज्यामिति समस्याओं से प्रेरित था, जैसे कि रोबोटिक्स, एनीमेशन या कंप्यूटर ग्राफिक्स में टकराव या दृश्यता का पता लगाना। अवलोकन गतिज डेटा संरचनाओं का उपयोग उन प्रणालियों पर किया जाता है जहां मूल्यों का एक समूह होता है जो एक ज्ञात तरीके से समय के कार्य के रूप में बदल रहे होते हैं। तो प्रणाली के कुछ मूल्य हैं, और प्रत्येक मूल्य के लिए, यह ज्ञात है। गतिज डेटा संरचना वर्तमान आभासी समय में एक प्रणाली पर प्रश्नों की अनुमति देती है, और दो अतिरिक्त संचालनःः प्रणाली को समय पर आगे बढ़ाती है। : मूल्य के प्रक्षेपवक्र को वर्तमान समय के अनुसार बदल देता है। अतिरिक्त संचालन का समर्थन किया जा सकता है। उदाहरण के लिए, गतिज डेटा संरचनाओं का उपयोग अक्सर बिंदुओं के एक समूह के साथ किया जाता है। इस मामले में, संरचना आम तौर पर बिंदुओं को डालने और हटाने की अनुमति देती है। पारंपरिक डेटा संरचनाओं के साथ विरोधाभास एक गतिज डेटा संरचना इसमें संग्रहीत मूल्यों को समय के साथ लगातार बदलने की अनुमति देती है। सिद्धांत रूप में, समय के निश्चित अंतराल पर बिंदुओं की स्थिति का नमूना लेकर और प्रत्येक बिंदु को "स्थिर" (पारंपरिक) डेटा संरचना में हटाकर और फिर से जोड़कर इसका अनुमान लगाया जा सकता है। हालाँकि, इस तरह का दृष्टिकोण ओवरसैम्पलिंग या अंडरसैम्पलिंग के लिए असुरक्षित है, जो इस बात पर निर्भर करता है कि किस समय के अंतराल का उपयोग किया जाता है, और कम्प्यूटेशनल संसाधनों की बर्बादी भी हो सकती है। प्रमाणपत्र दृष्टिकोण गतिज डेटा संरचनाओं के निर्माण के लिए निम्नलिखित सामान्य दृष्टिकोण का उपयोग किया जा सकता हैः वर्तमान समय में सिस्टम पर एक डेटा संरचना को संग्रहीत करें। यह डेटा संरचना वर्तमान आभासी समय में सिस्टम पर प्रश्नों की अनुमति देती है। प्रमाणपत्रों के साथ डेटा संरचना को बढ़ाएँ। प्रमाणपत्र वे स्थितियाँ हैं जिनके तहत डेटा संरचना सटीक होती है। प्रमाण पत्र अब सभी सही हैं, और डेटा संरचना केवल तभी सटीक नहीं होगी जब प्रमाण पत्रों में से एक अब सही नहीं होगा। प्रत्येक प्रमाणपत्र के विफलता समय की गणना करें, वह समय जब यह सही नहीं होगा। प्रमाणपत्रों को प्राथमिकता वाली कतार में रखें, जो उनके विफलता के समय पर आधारित हो। समय के साथ आगे बढ़ने के लिए, प्राथमिकता वाली कतार से सबसे कम विफलता के समय वाले प्रमाणपत्र को देखें। यदि प्रमाणपत्र समय से पहले विफल हो जाता है, तो इसे कतार से हटा दें और डेटा संरचना को ठीक करें ताकि यह विफलता के समय सटीक हो, और प्रमाणपत्रों को अद्यतन करें। इसे तब तक दोहराएं जब तक कि प्राथमिकता कतार में सबसे कम विफलता समय वाला प्रमाण पत्र समय के बाद विफल न हो जाए। यदि प्राथमिकता कतार में सबसे कम विफलता समय वाला प्रमाण पत्र समय के बाद विफल हो जाता है, तो सभी प्रमाण पत्र समय पर सही होते हैं ताकि डेटा संरचना समय पर प्रश्नों का सही उत्तर दे सके। घटनाओं के प्रकार प्रमाणपत्र विफलताओं को "घटनाओं" के रूप में संदर्भित किया जाता है। एक घटना को आंतरिक माना जाता है यदि गतिज डेटा संरचना द्वारा बनाए रखा गया गुण घटना होने पर नहीं बदलता है। एक घटना को बाहरी माना जाता है यदि घटना होने पर डेटा संरचना द्वारा बनाए रखा गया गुण बदल जाता है। प्रदर्शन प्रमाणपत्र दृष्टिकोण का उपयोग करते समय, प्रदर्शन के चार माप होते हैं। हम कहते हैं कि एक मात्रा कम होती है यदि यह एक बहुपदगणितीय कार्य है, या मनमाने ढंग से कम है, तो वस्तुओं की संख्या कहाँ हैः प्रतिक्रियाशीलता प्रतिक्रिया डेटा संरचना को ठीक करने और प्रमाणपत्र विफल होने पर प्रमाणपत्रों को बढ़ाने के लिए आवश्यक समय की सबसे खराब स्थिति है। एक गतिज डेटा संरचना प्रतिक्रियाशील होती है यदि किसी अद्यतन के लिए आवश्यक समय की सबसे खराब स्थिति कम होती है। स्थानीयता प्रमाणपत्रों की अधिकतम संख्या जिसमें कोई भी एक मूल्य शामिल है। गतिशील बिंदुओं से जुड़ी संरचनाओं के लिए, यह प्रमाणपत्रों की अधिकतम संख्या है जिसमें कोई भी एक बिंदु शामिल है। एक गतिज डेटा संरचना स्थानीय होती है यदि किसी एक मूल्य के साथ शामिल प्रमाणपत्रों की अधिकतम संख्या कम होती है। कॉम्पैक्टनेस किसी भी समय डेटा संरचना को बढ़ाने के लिए उपयोग किए जाने वाले प्रमाणपत्रों की अधिकतम संख्या है। एक गतिज डेटा संरचना सघन होती है यदि इसके द्वारा उपयोग किए जाने वाले प्रमाणपत्रों की संख्या या मनमाने ढंग से कम होती है। (रैखिक स्थान से अधिक एक छोटा कारक) दक्षता घटनाओं की सबसे खराब स्थिति संख्या का अनुपात जो तब हो सकता है जब संरचना को डेटा संरचना में "आवश्यक परिवर्तनों" की सबसे खराब स्थिति संख्या तक बढ़ाया जाता है। "आवश्यक परिवर्तन" की परिभाषा समस्या पर निर्भर है। उदाहरण के लिए, गतिशील डेटा संरचना के मामले में गतिशील बिंदुओं के एक समूह के गतिज पतवार को बनाए रखने के लिए, आवश्यक परिवर्तनों की संख्या समय के साथ गतिज पतवार में परिवर्तन की संख्या होगी। एक गतिज डेटा संरचना को कुशल कहा जाता है यदि यह अनुपात छोटा है। प्रक्षेपवक्रों के प्रकार एक निश्चित गतिज डेटा संरचना के प्रदर्शन का विश्लेषण कुछ प्रकार के प्रक्षेपवक्रों के लिए किया जा सकता है। आम तौर पर, निम्नलिखित प्रकार के प्रक्षेपवक्रों पर विचार किया जाता हैः एफ़ाइनः (रैखिक कार्य) बाउंडेड-डिग्री बीजगणितः (बाउंडेड डिग्री के बहुपद कार्य) कुछ निश्चित के लिए। छद्म-बीजगणितः प्रक्षेपवक्र इस तरह के होते हैं कि ब्याज का कोई भी प्रमाण पत्र सही और गलत समय के बीच पलट जाता है। उदाहरण काइनेटिक टूर्नामेंट काइनेटिक क्रमबद्ध सूची काइनेटिक हीप काइनेटिक उत्तल पतवार काइनेटिक निकटतम जोड़ी काइनेटिक न्यूनतम फैले हुए ट्री काइनेटिक यूक्लिडियन न्यूनतम फैले हुए ट्री संदर्भ काइनेटिक डेटा संरचनाएँ