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