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

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

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

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

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

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

समय को एक अतिरिक्त स्थानिक आयाम के रूप में मानना ​​संभव नहीं है। इसे स्पष्ट करने के लिए मान लीजिए कि हम अंतरिक्ष के अक्ष पर समय के आयाम को मैप करते हैं। स्थानिक समय आयाम जोड़ने के लिए हम जिस डेटा संरचना का उपयोग करेंगे, वह एक न्यूनतम-ढेर है। बता दें कि 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 किसी एक पर समय।

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

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

यह भी देखें

• लगातार डेटा संरचना