पूर्वव्यापी डेटा संरचना

कंप्यूटर विज्ञान में एक पूर्वव्यापी डेटा संरचना एक डेटा संरचना है जो संरचना पर किए गए संचालन के अनुक्रम में दक्ष संशोधनों का समर्थन करती है। ये संशोधन विगत कुछ समय में किए गए संचालन को पूर्वव्यापी प्रविष्टि, हटाने या अद्यतन करने का रूप ले सकते हैं।

पूर्वव्यापी डेटा संरचनाओं के कुछ अनुप्रयोग

वास्तविक संसार में ऐसी कई स्थितियाँ है जहां कोई विगत संचालन को संचालन के अनुक्रम से संशोधित करना चाहेगा। नीचे सूचीबद्ध कुछ संभावित अनुप्रयोग हैं:

• त्रुटि सुधार: डेटा का त्रुटिपूर्ण निवेश। डेटा को ठीक किया जाना चाहिए और त्रुटिपूर्ण डेटा के सभी माध्यमिक प्रभावों को हटा दिया जाना चाहिए।
• अनुपयुक्त डेटा: बड़ी प्रणालियों के साथ वितरण करते समय, विशेष रूप से बड़ी मात्रा में स्वचालित डेटा स्थानांतरण में, यह असामान्य नहीं है। उदाहरण के लिए, मान लें कि एक ऋतु नेटवर्क अनुपयुक्त होने के लिए संवेदक में से एक है और कचरा डेटा या त्रुटिपूर्ण डेटा का प्रतिवेदन करना  प्रारम्भ करता है। आदर्श हल यह होगा कि संवेदक द्वारा उत्पन्न सभी डेटा को हटा दिया जाए क्योंकि यह अनुपयुक्त डेटा के साथ-साथ समग्र प्रणाली पर अनुपयुक्त डेटा के सभी प्रभावों के साथ उत्पन्न हुआ था।
• पुनर्प्राप्ति: मान लीजिए कि एक हार्डवेयर संवेदक क्षतिग्रस्त हो गया था परन्तु अब उसकी मरम्मत की गई है और संवेदक से डेटा पढ़ा जा सकता है। हम डेटा को प्रणाली में वापस डालने में सक्षम होना चाहेंगे जैसे कि संवेदक पूर्व स्थान पर कभी क्षतिग्रस्त नहीं हुआ था।
• विगत का परिचालन: विगत को बदलना क्षति नियंत्रण के स्थितियों में सहायक हो सकता है और पूर्वव्यापी डेटा संरचनाओं को विगत के इच्छानुरूप परिचालन के लिए डिज़ाइन किया गया है।

स्थानिक आयाम के रूप में समय

समय को एक अतिरिक्त स्थानिक आयाम के रूप में मानना ​​संभव नहीं है। इसे स्पष्ट करने के लिए मान लीजिए कि हम अंतरिक्ष के अक्ष पर समय के आयाम को प्रतिचित्रित करते हैं। स्थानिक समय आयाम जोड़ने के लिए हम जिस डेटा संरचना का उपयोग करेंगे, वह एक न्यूनतम-राशि है। बता दें कि y अक्ष राशि के भीतर वस्तुओं के प्रमुख मूल्यों का प्रतिनिधित्व करता है और x अक्ष स्थानिक समय आयाम है। कई सम्मिलन और विलोपन-न्यूनतम संचालन के बाद (सभी गैर-पूर्वव्यापी रूप से किए गए) हमारी न्यूनतम-राशि चित्र 1 के जैसे दिखाई देगा। अब मान लें कि हम संचालन सूची की प्रारम्भ में शून्य को पूर्वव्यापी रूप से सम्मिलित करते हैं। हमारी न्यूनतम-राशि चित्र 2 के जैसे दिखाई देगा। ध्यान दें कि कैसे एकल संचालन एक व्यापक प्रभाव उत्पन्न करता है जो संपूर्ण डेटा संरचना को प्रभावित करता है। इस प्रकार हम देख सकते हैं कि समय को एक स्थानिक आयाम के रूप में खींचा जा सकता है, समय के साथ संचालन निर्भरता उत्पन्न करता है जो समय के संबंध में संशोधन किए जाने पर एक तरंग है।

File:Wiki min heap ex1.png

चित्रा 1. न्यूनतम-राशि समयरेखा के साथ।

File:Wiki min heap ex2.png

चित्रा 2. न्यूनतम-राशि और पूर्वव्यापी कार्रवाई के बाद समयरेखा।

दृढ़ता से तुलना

प्रथम झलक में एक पूर्वव्यापी डेटा संरचनाओं की धारणा दृढ़ता डेटा संरचनाओं के समान ही लगती है क्योंकि वे दोनों समय के आयाम को ध्यान में रखते हैं। दृढ़ता डेटा संरचनाओं और पूर्वव्यापी डेटा संरचनाओं के बीच मुख्य अंतर यह है कि वे समय के तत्व को कैसे संभालते हैं। एक सतत डेटा संरचना डेटा संरचना के कई संस्करणों को बनाए रखती है और डेटा संरचना के दूसरे संस्करण का उत्पादन करने के लिए एक संस्करण पर संचालन किया जा सकता है। चूंकि प्रत्येक संचालन एक नया संस्करण उत्पन्न करता है, इसलिए प्रत्येक संस्करण एक संग्रह बन जाता है जिसे बदला नहीं जा सकता है (केवल नए संस्करण ही इससे उत्पन्न किए जा सकते हैं)। चूंकि प्रत्येक संस्करण नहीं बदलता है, प्रत्येक संस्करण के बीच निर्भरता भी नहीं बदलती है। पूर्वव्यापी डेटा संरचनाओं में हम सीधे विगत संस्करणों में परिवर्तन करने की अनुमति देते हैं। चूंकि प्रत्येक संस्करण अब अन्योन्याश्रित है, एक एकल परिवर्तन बाद के सभी संस्करणों के परिवर्तनों की तरंग उत्पन्न कर सकता है। चित्र 1 और 2 इस तरंग प्रभाव का एक उदाहरण दिखाते हैं।

परिभाषा

किसी भी डेटा संरचना को पूर्वव्यापी सेटिंग में सुधारा जा सकता है। सामान्य तौर पर डेटा संरचना में कुछ समय के दौरान किए गए अद्यतनों और प्रश्नों की एक श्रृंखला शामिल होती है। चलो यू = [यू_{t1</उप>, यूt2</उप>, यूt3</ उप>, ..., यूtm] टी से अद्यतन संचालन का क्रम हो1 टी के लिएm ऐसा कि टी1 <टी2 <... <टीm. यहाँ धारणा यह है कि एक निश्चित समय टी के लिए अधिकतम एक संचालन किया जा सकता है।}

आंशिक रूप से पूर्वव्यापी

हम डेटा संरचना को आंशिक रूप से पूर्वव्यापी होने के लिए परिभाषित करते हैं यदि यह वर्तमान समय में अद्यतन और क्वेरी संचालन कर सकता है और विगत में सम्मिलन और विलोपन संचालन का समर्थन कर सकता है। इस प्रकार आंशिक रूप से पूर्वव्यापी के लिए हम निम्नलिखित कार्यों में रुचि रखते हैं:

• सम्मिलित करें (टी, यू): समय टी पर सूची यू में एक नया संचालन यू डालें।
• हटाएं (टी): सूची यू से समय टी पर संचालन हटाएं।

उपरोक्त पूर्वव्यापी संचालन को देखते हुए, एक मानक सम्मिलन संचालन अब इन्सर्ट(t, इन्सर्ट(x)) का रूप होगा। डेटा संरचना के परिचालन इतिहास पर सभी पूर्वव्यापी परिवर्तन संभावित रूप से संचालन के समय से लेकर वर्तमान तक के सभी कार्यों को प्रभावित कर सकते हैं। उदाहरण के लिए, यदि हमारे पास टी_i-1 <टी <टी_i+1, फिर सम्मिलित करें (टी, सम्मिलित करें (एक्स)) संचालन सेशन के बीच एक नया संचालन, सेशन रखेगा_i-1और ऑप_i+1. डेटा संरचना की वर्तमान स्थिति (अर्थात्: वर्तमान समय में डेटा संरचना) तब ऐसी स्थिति में होगी जैसे संचालन ऑप_i-1, इत्यादि_i+1सब कुछ एक क्रम में हुआ, जैसे कि संचालन ऑप हमेशा से था। दृश्य उदाहरण के लिए चित्र 1 और 2 देखें।

पूरी तरह से पूर्वव्यापी

हम डेटा संरचना को पूरी तरह से पूर्वव्यापी होने के लिए परिभाषित करते हैं यदि आंशिक रूप से पूर्वव्यापी संचालन के अतिरिक्त हम किसी को विगत के बारे में पूछताछ करने की अनुमति भी देते हैं। आंशिक रूप से रेट्रोएक्टिव मॉडल में मानक संचालन इन्सर्ट(x) कैसे इन्सर्ट(t, इन्सर्ट(x) ) बन जाता है, इसी तरह पूरी तरह से रेट्रोएक्टिव मॉडल में संचालन क्वेरी (x) का फॉर्म अब Query(t, query(x) ) है .

पूर्वव्यापी चलने का समय

पूर्वव्यापी डेटा संरचनाओं का चलने का समय संचालन की संख्या पर आधारित होता है, m, संरचना पर किया जाता है, संचालन की संख्या r जो पूर्वव्यापी संचालन से पूर्व किया जाता है, और संरचना में तत्वों की अधिकतम संख्या n किसी एक पर समय।

स्वचालित रेट्रो-गतिविधि

डेटा संरचनाओं के संबंध में स्वत: रेट्रो-गतिविधि के संबंध में मुख्य प्रश्न यह है कि क्या कोई सामान्य तकनीक है जो किसी भी डेटा संरचना को एक दक्ष पूर्वव्यापी समकक्ष में परिवर्तित कर सकती है या नहीं। लागू होने वाले पूर्वव्यापी संचालन से पूर्व संरचना में किए गए सभी परिवर्तनों पर रोल-बैक करना एक सरल तरीका है। एक बार जब हम डेटा संरचना को उपयुक्त स्थिति में वापस कर देते हैं, तो हम जो परिवर्तन चाहते हैं, उसे करने के लिए पूर्वव्यापी संचालन लागू कर सकते हैं। एक बार परिवर्तन किए जाने के बाद हमें डेटा संरचना को उसकी नई स्थिति में लाने के लिए पूर्व किए गए सभी परिवर्तनों को फिर से लागू करना होगा। जबकि यह किसी भी डेटा संरचना के लिए काम कर सकता है, यह अक्सर अक्षम और बेकार होता है, विशेष रूप से एक बार रोल-बैक करने के लिए आवश्यक परिवर्तनों की संख्या बड़ी होने के बाद। एक दक्ष पूर्वव्यापी डेटा संरचना बनाने के लिए हमें यह निर्धारित करने के लिए संरचना के गुणों पर एक नज़र डालनी चाहिए कि गति को कहाँ महसूस किया जा सकता है। इस प्रकार किसी भी डेटा संरचना को एक दक्ष पूर्वव्यापी समकक्ष में परिवर्तित करने का कोई सामान्य तरीका नहीं है। एरिक डी. डेमैन, जॉन इकोनो और स्टीफन लैंगरमैन इसे साबित करते हैं।

यह भी देखें

• दृढ़ता डेटा संरचना