Retroactive data structure
कंप्यूटर विज्ञान में एक पूर्वव्यापी डेटा संरचना एक डेटा संरचना है जो संरचना पर किए गए संचालन के अनुक्रम में कुशल संशोधनों का समर्थन करती है। ये संशोधन पूर्वव्यापी सम्मिलन, विलोपन या अतीत में किसी समय किए गए ऑपरेशन को अद्यतन करने का रूप ले सकते हैं। पूर्वव्यापी डेटा संरचनाओं के कुछ अनुप्रयोग वास्तविक दुनिया में ऐसे कई मामले हैं जहां कोई पिछले संचालन को संचालन के अनुक्रम से संशोधित करना चाहेगा। नीचे कुछ संभावित अनुप्रयोग सूचीबद्ध किए गए हैंः त्रुटि सुधारः डेटा का गलत इनपुट। डेटा को ठीक किया जाना चाहिए और गलत डेटा के सभी गौण प्रभावों को हटा दिया जाना चाहिए। खराब डेटाः बड़ी प्रणालियों के साथ काम करते समय, विशेष रूप से जिनमें बड़ी मात्रा में स्वचालित डेटा हस्तांतरण शामिल होता है, यह असामान्य नहीं है। उदाहरण के लिए, मान लीजिए कि मौसम नेटवर्क की खराबी के लिए सेंसर में से एक कचरा डेटा या गलत डेटा की रिपोर्ट करना शुरू कर देता है। आदर्श समाधान यह होगा कि संवेदक द्वारा उत्पादित सभी डेटा को हटा दिया जाए क्योंकि यह समग्र प्रणाली पर खराब डेटा के सभी प्रभावों के साथ खराब हो गया था। पुनर्प्राप्तिः मान लीजिए कि एक हार्डवेयर संवेदक क्षतिग्रस्त हो गया था लेकिन अब उसकी मरम्मत की गई है और संवेदक से डेटा को पढ़ा जा सकता है। हम डेटा को सिस्टम में वापस डालने में सक्षम होना चाहते हैं जैसे कि सेंसर कभी भी क्षतिग्रस्त नहीं हुआ था। अतीत का हेरफेरः अतीत को बदलना क्षति नियंत्रण के मामलों में सहायक हो सकता है और पूर्वव्यापी डेटा संरचनाओं को अतीत के जानबूझकर हेरफेर के लिए डिज़ाइन किया गया है। समय को एक स्थानिक आयाम के रूप में समय को एक अतिरिक्त स्थानिक आयाम के रूप में मानना संभव नहीं है। इसे स्पष्ट करने के लिए मान लीजिए कि हम समय के आयाम को अंतरिक्ष के एक अक्ष पर मानचित्रित करते हैं। स्थानिक समय आयाम को जोड़ने के लिए हम जिस डेटा संरचना का उपयोग करेंगे, वह एक न्यूनतम राशि है। मान लीजिए कि y अक्ष ढेर के भीतर वस्तुओं के प्रमुख मूल्यों का प्रतिनिधित्व करता है और x अक्ष स्थानिक समय आयाम है। कई सम्मिलन और डिलीट-मिन संचालन के बाद (सभी गैर-रेट्रोएक्टिव रूप से किए गए) हमारा मिन-हीप चित्र 1 की तरह दिखाई देगा। अब मान लीजिए कि हम ऑपरेशन सूची की शुरुआत में पूर्वव्यापी रूप से शून्य डालते हैं। हमारा न्यूनतम-ढेर चित्र 2 की तरह दिखाई देगा। ध्यान दें कि कैसे एकल ऑपरेशन एक कैस्केडिंग प्रभाव पैदा करता है जो पूरे डेटा संरचना को प्रभावित करता है। इस प्रकार हम देख सकते हैं कि समय को एक स्थानिक आयाम के रूप में खींचा जा सकता है, समय के साथ संचालन निर्भरता पैदा करता है जिसमें समय के संबंध में संशोधन किए जाने पर एक लहर होती है। दृढ़ता से तुलना पहली नज़र में एक पूर्वव्यापी डेटा संरचनाओं की धारणा स्थायी डेटा संरचनाओं के समान लगती है क्योंकि वे दोनों समय के आयाम को ध्यान में रखते हैं। स्थायी डेटा संरचनाओं और पूर्वव्यापी डेटा संरचनाओं के बीच प्रमुख अंतर यह है कि वे समय के तत्व को कैसे संभालते हैं। एक स्थायी डेटा संरचना डेटा संरचना के कई संस्करणों को बनाए रखती है और डेटा संरचना के दूसरे संस्करण का उत्पादन करने के लिए एक संस्करण पर संचालन किया जा सकता है। चूँकि प्रत्येक ऑपरेशन एक नया संस्करण उत्पन्न करता है, इस प्रकार प्रत्येक संस्करण एक संग्रह बन जाता है जिसे बदला नहीं जा सकता है (केवल नए संस्करणों को इससे पैदा किया जा सकता है)। चूँकि प्रत्येक संस्करण नहीं बदलता है, इसलिए प्रत्येक संस्करण के बीच निर्भरता भी नहीं बदलती है। पूर्वव्यापी डेटा संरचनाओं में हम परिवर्तनों को सीधे पिछले संस्करणों में करने की अनुमति देते हैं। चूँकि प्रत्येक संस्करण अब परस्पर निर्भर है, एक एकल परिवर्तन सभी बाद के संस्करणों के परिवर्तनों की लहर पैदा कर सकता है। चित्र 1 और 2 इस लहरदार प्रभाव का एक उदाहरण दिखाते हैं। परिभाषा किसी भी डेटा संरचना को पूर्वव्यापी सेटिंग में सुधार किया जा सकता है। सामान्य तौर पर डेटा संरचना में कुछ समय में किए गए अद्यतन और प्रश्नों की एक श्रृंखला शामिल होती है। मान लीजिए कि यू = [यू. टी. 1, यू. टी. 2, यू. टी. 3,., यू. टी. एम] टी1 से टी. एम. तक अद्यतन संचालन का अनुक्रम है जैसे कि टी1 <टी2 <. <टी. एम.। यहाँ यह धारणा है कि किसी दिए गए समय के लिए अधिक से अधिक एक ऑपरेशन किया जा सकता है t. आंशिक रूप से पूर्वव्यापी हम डेटा संरचना को आंशिक रूप से पूर्वव्यापी होने के लिए परिभाषित करते हैं यदि यह वर्तमान समय में अद्यतन और प्रश्न संचालन कर सकता है और अतीत में सम्मिलन और विलोपन संचालन का समर्थन कर सकता है। इस प्रकार आंशिक रूप से पूर्व सक्रिय होने के लिए हम निम्नलिखित कार्यों में रुचि रखते हैंः सम्मिलित करें (टी, यू): समय टी पर सूची यू में एक नया ऑपरेशन यू डालें। हटाएं (टी): सूची यू से समय टी पर ऑपरेशन को हटाएं। उपरोक्त पूर्वव्यापी संक्रियाओं को देखते हुए, एक मानक प्रविष्टि संक्रिया अब प्रविष्टि (टी, "प्रविष्टि (एक्स)") का रूप होगी। डेटा संरचना के परिचालन इतिहास पर सभी पूर्वव्यापी परिवर्तन संभावित रूप से संचालन के समय से लेकर वर्तमान तक के सभी कार्यों को प्रभावित कर सकते हैं। उदाहरण के लिए, यदि हमारे पास ti-1 <t <ti + 1 है, तो सम्मिलित करें (t, सम्मिलित करें (x)) संचालन opi-1 और opi + 1 के बीच एक नया संचालन, op, रखेगा। डेटा संरचना की वर्तमान स्थिति (अर्थात। : वर्तमान समय में डेटा संरचना) तब ऐसी स्थिति में होगी जैसे ऑपरेशन ओपीआई-1, ओपी और ओपीआई + 1 सभी एक अनुक्रम में हुए, जैसे कि ऑपरेशन ऑप हमेशा था। एक दृश्य उदाहरण के लिए चित्र 1 और 2 देखें। हम डेटा संरचना को पूरी तरह से पूर्वव्यापी होने के लिए परिभाषित करते हैं यदि आंशिक रूप से पूर्वव्यापी संचालन के अलावा हम अतीत के बारे में प्रश्न करने की भी अनुमति देते हैं। जिस तरह से मानक ऑपरेशन इन्सर्ट (x) आंशिक रूप से पूर्वव्यापी मॉडल में इन्सर्ट (t ", इन्सर्ट (x)") बन जाता है, उसी तरह पूरी तरह से पूर्वव्यापी मॉडल में ऑपरेशन क्वेरी (x) में अब क्वेरी (t ", क्वेरी (x)") का रूप है। पूर्व-सक्रिय चलने का समय पूर्व-सक्रिय डेटा संरचनाओं का चलने का समय संरचना पर किए गए संचालन की संख्या, m, पूर्व-सक्रिय संचालन से पहले किए गए संचालन की संख्या और किसी भी एक समय में संरचना में तत्वों की अधिकतम संख्या पर आधारित होता है। डेटा संरचनाओं के संबंध में स्वचालित पूर्वव्यापी-गतिविधि के बारे में मुख्य प्रश्न यह है कि क्या कोई सामान्य तकनीक है जो किसी भी डेटा संरचना को एक कुशल पूर्वव्यापी समकक्ष में बदल सकती है या नहीं। एक सरल तरीका यह है कि लागू किए जाने वाले पूर्वव्यापी संचालन से पहले संरचना में किए गए सभी परिवर्तनों पर एक रोल-बैक किया जाए। एक बार जब हम डेटा संरचना को उपयुक्त स्थिति में वापस ले लेते हैं तो हम जो बदलाव चाहते थे उसे करने के लिए पूर्वव्यापी संचालन को लागू कर सकते हैं। एक बार परिवर्तन किए जाने के बाद हमें उन सभी परिवर्तनों को फिर से लागू करना होगा जिन्हें हमने डेटा संरचना को इसकी नई स्थिति में लाने के लिए पहले वापस कर दिया था। हालांकि यह किसी भी डेटा संरचना के लिए काम कर सकता है, यह अक्सर अक्षम और व्यर्थ होता है, विशेष रूप से जब हमें रोल-बैक करने के लिए आवश्यक परिवर्तनों की संख्या अधिक होती है। एक कुशल पूर्वव्यापी डेटा संरचना बनाने के लिए हमें संरचना के गुणों पर एक नज़र डालनी चाहिए ताकि यह निर्धारित किया जा सके कि गति को कहाँ प्राप्त किया जा सकता है। इस प्रकार किसी भी डेटा संरचना को एक कुशल पूर्वव्यापी समकक्ष में बदलने का कोई सामान्य तरीका नहीं है। एरिक डी. डेमाइन, जॉन आइकानो और स्टीफन लैंगरमैन इसे साबित करते हैं। निरंतर डेटा संरचना संदर्भ डेटा संरचनाएँ भी देखें।