पूर्वव्यापी डेटा संरचना: Difference between revisions
No edit summary |
No edit summary |
||
| (7 intermediate revisions by 4 users not shown) | |||
| Line 1: | Line 1: | ||
[[कंप्यूटर विज्ञान]] में पूर्वव्यापी [[डेटा संरचना]] एक डेटा संरचना है जो संरचना पर किए गए संचालन के अनुक्रम में दक्ष संशोधनों का समर्थन करती है। ये संशोधन विगत कुछ समय में किए गए संचालन को पूर्वव्यापी प्रविष्टि, हटाने या अद्यतन करने का रूप ले सकते हैं।<ref name=retroDS /> | |||
[[कंप्यूटर विज्ञान]] में | |||
== पूर्वव्यापी डेटा संरचनाओं के कुछ अनुप्रयोग == | == पूर्वव्यापी डेटा संरचनाओं के कुछ अनुप्रयोग == | ||
वास्तविक | वास्तविक संसार में ऐसी कई स्थितियाँ है जहां कोई विगत संचालन को संचालन के अनुक्रम से संशोधित करना चाहेगा। नीचे सूचीबद्ध कुछ संभावित अनुप्रयोग हैं: | ||
* त्रुटि सुधार: डेटा का | * त्रुटि सुधार: डेटा का त्रुटिपूर्ण निवेश। डेटा को ठीक किया जाना चाहिए और त्रुटिपूर्ण डेटा के सभी माध्यमिक प्रभावों को हटा दिया जाना चाहिए। | ||
* | * अनुपयुक्त डेटा: बड़ी प्रणालियों के साथ वितरण करते समय, विशेष रूप से बड़ी मात्रा में स्वचालित डेटा स्थानांतरण में, यह असामान्य नहीं है। उदाहरण के लिए, मान लें कि एक ऋतु नेटवर्क अनुपयुक्त होने के लिए संवेदक में से एक है और कचरा डेटा या त्रुटिपूर्ण डेटा का प्रतिवेदन करना प्रारम्भ करता है। आदर्श हल यह होगा कि संवेदक द्वारा उत्पन्न सभी डेटा को हटा दिया जाए क्योंकि यह अनुपयुक्त डेटा के साथ-साथ समग्र प्रणाली पर अनुपयुक्त डेटा के सभी प्रभावों के साथ उत्पन्न हुआ था। | ||
* पुनर्प्राप्ति: मान लीजिए कि एक हार्डवेयर | * पुनर्प्राप्ति: मान लीजिए कि एक हार्डवेयर संवेदक क्षतिग्रस्त हो गया था परन्तु अब उसकी मरम्मत की गई है और संवेदक से डेटा पढ़ा जा सकता है। हम डेटा को प्रणाली में वापस डालने में सक्षम होना चाहेंगे जैसे कि संवेदक पूर्व स्थान पर कभी क्षतिग्रस्त नहीं हुआ था। | ||
* | * विगत का परिचालन: विगत को बदलना क्षति नियंत्रण के स्थितियों में सहायक हो सकता है और पूर्वव्यापी डेटा संरचनाओं को विगत के इच्छानुरूप परिचालन के लिए डिज़ाइन किया गया है। | ||
== स्थानिक आयाम के रूप में समय == | == स्थानिक आयाम के रूप में समय == | ||
समय को | समय को अतिरिक्त स्थानिक आयाम के रूप में मानना संभव नहीं है। इसे स्पष्ट करने के लिए मान लीजिए कि हम अंतरिक्ष के अक्ष पर समय के आयाम को प्रतिचित्रित करते हैं। स्थानिक समय आयाम जोड़ने के लिए हम जिस डेटा संरचना का उपयोग करेंगे, वह न्यूनतम-राशि है। बता दें कि y अक्ष राशि के भीतर वस्तुओं के प्रमुख मूल्यों का प्रतिनिधित्व करता है और x अक्ष स्थानिक समय आयाम है। कई सम्मिलन और विलोपन-न्यूनतम संचालन के बाद(सभी गैर-पूर्वव्यापी रूप से किए गए) हमारी न्यूनतम-राशि चित्र 1 के जैसे दिखाई देगा। अब मान लें कि हम संचालन सूची की प्रारम्भ में शून्य को पूर्वव्यापी रूप से सम्मिलित करते हैं। हमारी न्यूनतम-राशि चित्र 2 के जैसे दिखाई देगा। ध्यान दें कि कैसे एकल संचालन व्यापक प्रभाव उत्पन्न करता है जो संपूर्ण डेटा संरचना को प्रभावित करता है। इस प्रकार हम देख सकते हैं कि समय को स्थानिक आयाम के रूप में खींचा जा सकता है, समय के साथ संचालन निर्भरता उत्पन्न करता है जो समय के संबंध में संशोधन किए जाने पर एक तरंग है। | ||
== दृढ़ता से तुलना == | == दृढ़ता से तुलना == | ||
प्रथम झलक में एक पूर्वव्यापी डेटा संरचनाओं की धारणा दृढ़ता डेटा संरचनाओं के समान ही लगती है क्योंकि वे दोनों समय के आयाम को ध्यान में रखते हैं। दृढ़ता डेटा संरचनाओं और पूर्वव्यापी डेटा संरचनाओं के बीच मुख्य अंतर यह है कि वे समय के अवयव को कैसे संभालते हैं। सतत डेटा संरचना डेटा संरचना के कई संस्करणों को बनाए रखती है और डेटा संरचना के दूसरे संस्करण का उत्पादन करने के लिए संस्करण पर संचालन किया जा सकता है। चूंकि प्रत्येक संचालन नवीन संस्करण उत्पन्न करता है, इसलिए प्रत्येक संस्करण एक संग्रह बन जाता है जिसे बदला नहीं जा सकता है(केवल नए संस्करण ही इससे उत्पन्न किए जा सकते हैं)। चूंकि प्रत्येक संस्करण नहीं बदलता है, प्रत्येक संस्करण के बीच निर्भरता भी नहीं बदलती है। पूर्वव्यापी डेटा संरचनाओं में हम सीधे विगत संस्करणों में परिवर्तन करने की अनुमति देते हैं। चूंकि प्रत्येक संस्करण अब अन्योन्याश्रित है, एक एकल परिवर्तन बाद के सभी संस्करणों के परिवर्तनों की तरंग उत्पन्न कर सकता है। चित्र 1 और 2 इस तरंग प्रभाव का एक उदाहरण दिखाते हैं। | |||
== परिभाषा == | == परिभाषा == | ||
किसी भी डेटा संरचना को पूर्वव्यापी | किसी भी डेटा संरचना को पूर्वव्यापी व्यवस्था में सुधारा जा सकता है। सामान्यतः डेटा संरचना में कुछ अवधि के समय किए गए अद्यतनों और प्रश्नों की एक श्रृंखला सम्मिलित होती है। बता दें कि U = [u<sub>t1</sub>, u<sub>t2</sub>, u<sub>t3</sub>, ..., u<sub>tm</sub>] t<sub>1</sub> से t<sub>m</sub> तक अद्यतन संचालन का क्रम है जैसे कि t<sub>1</sub> < t<sub>2</sub> < ... < t<sub>m</sub> । यहाँ धारणा यह है कि निश्चित समय t के लिए अधिकतम एक संचालन किया जा सकता है। | ||
=== आंशिक रूप से पूर्वव्यापी === | === आंशिक रूप से पूर्वव्यापी === | ||
हम डेटा संरचना को आंशिक रूप से पूर्वव्यापी होने के लिए परिभाषित करते हैं यदि यह वर्तमान समय में अद्यतन और | हम डेटा संरचना को आंशिक रूप से पूर्वव्यापी होने के लिए परिभाषित करते हैं यदि यह वर्तमान समय में अद्यतन और प्रश्न संचालन कर सकता है और विगत में सम्मिलन और विलोपन संचालन का समर्थन कर सकता है। इस प्रकार आंशिक रूप से पूर्वव्यापी के लिए हम निम्नलिखित कार्यों में रुचि रखते हैं: | ||
* सम्मिलित करें ( | * सम्मिलित करें(t,u): समय t पर सूची u में एक नवीन संचालन u डालें। | ||
* | * विलोपन(t): सूची u से समय t पर संचालन विलोपित करें। | ||
उपरोक्त पूर्वव्यापी संचालन को देखते हुए, एक मानक सम्मिलन | उपरोक्त पूर्वव्यापी संचालन को देखते हुए, एक मानक सम्मिलन संचालन अब इन्सर्ट(t, इन्सर्ट(x)) का रूप होगा। डेटा संरचना के परिचालन इतिहास पर सभी पूर्वव्यापी परिवर्तन संभावित रूप से संचालन के समय से लेकर वर्तमान तक के सभी कार्यों को प्रभावित कर सकते हैं। उदाहरण के लिए, यदि हमारे समीप t<sub>i-1</sub> < t < t<sub>i+1</sub> है, तो इन्सर्ट(t, इन्सर्ट(x)) नवीन संचालन, op, संचालन ''op<sub>i-1</sub>'' और ''op<sub>i+1</sub>'' के बीच रखेगा। डेटा संरचना की वर्तमान स्थिति(अर्थात्: वर्तमान समय में डेटा संरचना) तब ऐसी स्थिति में होगी जैसे संचालन ''op<sub>i-1</sub>'', ''op और op<sub>i+1</sub>'' सभी क्रम में होते हैं, जैसे कि संचालन ''op'' सदैव होता था। दृश्य उदाहरण के लिए चित्र 1 और 2 देखें। | ||
=== | === पूर्ण रूप से पूर्वव्यापी === | ||
हम डेटा संरचना को | हम डेटा संरचना को पूर्ण रूप से पूर्वव्यापी होने के लिए परिभाषित करते हैं यदि आंशिक रूप से पूर्वव्यापी संचालन के अतिरिक्त हम किसी को विगत के विषय में पूछताछ करने की अनुमति भी देते हैं। आंशिक रूप से पूर्वव्यापी मॉडल में मानक संचालन इन्सर्ट(x) कैसे इन्सर्ट(t, इन्सर्ट(x)) बन जाता है, इसी प्रकार पूर्ण रूप से पूर्वव्यापी मॉडल में संचालन क्वेरी(x) का रूप अब क्वेरी(t, क्वेरी(x)) है। | ||
=== पूर्वव्यापी चलने का समय === | === पूर्वव्यापी चलने का समय === | ||
पूर्वव्यापी डेटा संरचनाओं | पूर्वव्यापी डेटा संरचनाओं के चलने का समय संचालन की संख्या पर आधारित होता है, m, संरचना पर किया जाता है, संचालन की संख्या r जो पूर्वव्यापी संचालन से पूर्व किया जाता है, और किसी एक समय में संरचना में n अवयवों की अधिकतम संख्या है। | ||
=== स्वचालित | === स्वचालित पूर्व-गतिविधि === | ||
डेटा संरचनाओं के संबंध में स्वत: | डेटा संरचनाओं के संबंध में स्वत: पूर्व-गतिविधि के संबंध में मुख्य प्रश्न यह है कि क्या कोई सामान्य तकनीक है जो किसी भी डेटा संरचना को एक दक्ष पूर्वव्यापी समकक्ष में परिवर्तित कर सकती है या नहीं। लागू होने वाले पूर्वव्यापी संचालन से पूर्व संरचना में किए गए सभी परिवर्तनों पर नियमावली-वापस करना सरल उपाय है। एकदा जब हम डेटा संरचना को उपयुक्त स्थिति में वापस कर देते हैं, तो हम जो परिवर्तन चाहते हैं, उसे करने के लिए पूर्वव्यापी संचालन लागू कर सकते हैं। एकदा परिवर्तन किए जाने के बाद हमें डेटा संरचना को उसकी नवीन स्थिति में लाने के लिए पूर्व किए गए सभी परिवर्तनों को फिर से लागू करना होगा। जबकि यह किसी भी डेटा संरचना के लिए काम कर सकता है, यह प्रायः अदक्ष और व्यर्थ होता है, विशेष रूप से एकदा नियमावली-वापस करने के लिए आवश्यक परिवर्तनों की संख्या बड़ी होने के बाद। एक दक्ष पूर्वव्यापी डेटा संरचना बनाने के लिए हमें यह निर्धारित करने के लिए संरचना के गुणों पर दृष्टि डालनी चाहिए कि गति को कहाँ सिद्ध किया जा सकता है। इस प्रकार किसी भी डेटा संरचना को एक दक्ष पूर्वव्यापी समकक्ष में परिवर्तित करने का कोई सामान्य विधि नहीं है। एरिक डी. डेमैन, [[जॉन इकोनो]] और [[स्टीफन लैंगरमैन]] इसे सिद्ध करते हैं।<ref name ="retroDS">{{cite journal|last1=Demaine|first1=Erik D.|author1-link=Erik Demaine |last2=Iacono|first2=John|author2-link=John Iacono |last3=Langerman|first3=Stefan|author3-link=Stefan Langerman|title=पूर्वव्यापी डेटा संरचनाएं|journal=ACM Transactions on Algorithms|year=2007|volume=3|issue=2 |page=13 |url=http://doi.acm.org/10.1145/1240233.1240236|accessdate=21 April 2012|doi=10.1145/1240233.1240236|s2cid=5555302 }}</ref> | ||
== यह भी देखें == | == यह भी देखें == | ||
* [[लगातार डेटा संरचना]] | * [[लगातार डेटा संरचना|दृढ़ता डेटा संरचना]] | ||
==संदर्भ== | ==संदर्भ== | ||
{{Reflist}} | {{Reflist}} | ||
[[Category:Created On 24/02/2023]] | [[Category:Created On 24/02/2023]] | ||
[[Category:Machine Translated Page]] | |||
[[Category:Pages with script errors]] | |||
[[Category:Templates Vigyan Ready]] | |||
[[Category:डेटा संरचनाएं]] | |||
Latest revision as of 11:03, 10 March 2023
कंप्यूटर विज्ञान में पूर्वव्यापी डेटा संरचना एक डेटा संरचना है जो संरचना पर किए गए संचालन के अनुक्रम में दक्ष संशोधनों का समर्थन करती है। ये संशोधन विगत कुछ समय में किए गए संचालन को पूर्वव्यापी प्रविष्टि, हटाने या अद्यतन करने का रूप ले सकते हैं।[1]
पूर्वव्यापी डेटा संरचनाओं के कुछ अनुप्रयोग
वास्तविक संसार में ऐसी कई स्थितियाँ है जहां कोई विगत संचालन को संचालन के अनुक्रम से संशोधित करना चाहेगा। नीचे सूचीबद्ध कुछ संभावित अनुप्रयोग हैं:
- त्रुटि सुधार: डेटा का त्रुटिपूर्ण निवेश। डेटा को ठीक किया जाना चाहिए और त्रुटिपूर्ण डेटा के सभी माध्यमिक प्रभावों को हटा दिया जाना चाहिए।
- अनुपयुक्त डेटा: बड़ी प्रणालियों के साथ वितरण करते समय, विशेष रूप से बड़ी मात्रा में स्वचालित डेटा स्थानांतरण में, यह असामान्य नहीं है। उदाहरण के लिए, मान लें कि एक ऋतु नेटवर्क अनुपयुक्त होने के लिए संवेदक में से एक है और कचरा डेटा या त्रुटिपूर्ण डेटा का प्रतिवेदन करना प्रारम्भ करता है। आदर्श हल यह होगा कि संवेदक द्वारा उत्पन्न सभी डेटा को हटा दिया जाए क्योंकि यह अनुपयुक्त डेटा के साथ-साथ समग्र प्रणाली पर अनुपयुक्त डेटा के सभी प्रभावों के साथ उत्पन्न हुआ था।
- पुनर्प्राप्ति: मान लीजिए कि एक हार्डवेयर संवेदक क्षतिग्रस्त हो गया था परन्तु अब उसकी मरम्मत की गई है और संवेदक से डेटा पढ़ा जा सकता है। हम डेटा को प्रणाली में वापस डालने में सक्षम होना चाहेंगे जैसे कि संवेदक पूर्व स्थान पर कभी क्षतिग्रस्त नहीं हुआ था।
- विगत का परिचालन: विगत को बदलना क्षति नियंत्रण के स्थितियों में सहायक हो सकता है और पूर्वव्यापी डेटा संरचनाओं को विगत के इच्छानुरूप परिचालन के लिए डिज़ाइन किया गया है।
स्थानिक आयाम के रूप में समय
समय को अतिरिक्त स्थानिक आयाम के रूप में मानना संभव नहीं है। इसे स्पष्ट करने के लिए मान लीजिए कि हम अंतरिक्ष के अक्ष पर समय के आयाम को प्रतिचित्रित करते हैं। स्थानिक समय आयाम जोड़ने के लिए हम जिस डेटा संरचना का उपयोग करेंगे, वह न्यूनतम-राशि है। बता दें कि y अक्ष राशि के भीतर वस्तुओं के प्रमुख मूल्यों का प्रतिनिधित्व करता है और x अक्ष स्थानिक समय आयाम है। कई सम्मिलन और विलोपन-न्यूनतम संचालन के बाद(सभी गैर-पूर्वव्यापी रूप से किए गए) हमारी न्यूनतम-राशि चित्र 1 के जैसे दिखाई देगा। अब मान लें कि हम संचालन सूची की प्रारम्भ में शून्य को पूर्वव्यापी रूप से सम्मिलित करते हैं। हमारी न्यूनतम-राशि चित्र 2 के जैसे दिखाई देगा। ध्यान दें कि कैसे एकल संचालन व्यापक प्रभाव उत्पन्न करता है जो संपूर्ण डेटा संरचना को प्रभावित करता है। इस प्रकार हम देख सकते हैं कि समय को स्थानिक आयाम के रूप में खींचा जा सकता है, समय के साथ संचालन निर्भरता उत्पन्न करता है जो समय के संबंध में संशोधन किए जाने पर एक तरंग है।
दृढ़ता से तुलना
प्रथम झलक में एक पूर्वव्यापी डेटा संरचनाओं की धारणा दृढ़ता डेटा संरचनाओं के समान ही लगती है क्योंकि वे दोनों समय के आयाम को ध्यान में रखते हैं। दृढ़ता डेटा संरचनाओं और पूर्वव्यापी डेटा संरचनाओं के बीच मुख्य अंतर यह है कि वे समय के अवयव को कैसे संभालते हैं। सतत डेटा संरचना डेटा संरचना के कई संस्करणों को बनाए रखती है और डेटा संरचना के दूसरे संस्करण का उत्पादन करने के लिए संस्करण पर संचालन किया जा सकता है। चूंकि प्रत्येक संचालन नवीन संस्करण उत्पन्न करता है, इसलिए प्रत्येक संस्करण एक संग्रह बन जाता है जिसे बदला नहीं जा सकता है(केवल नए संस्करण ही इससे उत्पन्न किए जा सकते हैं)। चूंकि प्रत्येक संस्करण नहीं बदलता है, प्रत्येक संस्करण के बीच निर्भरता भी नहीं बदलती है। पूर्वव्यापी डेटा संरचनाओं में हम सीधे विगत संस्करणों में परिवर्तन करने की अनुमति देते हैं। चूंकि प्रत्येक संस्करण अब अन्योन्याश्रित है, एक एकल परिवर्तन बाद के सभी संस्करणों के परिवर्तनों की तरंग उत्पन्न कर सकता है। चित्र 1 और 2 इस तरंग प्रभाव का एक उदाहरण दिखाते हैं।
परिभाषा
किसी भी डेटा संरचना को पूर्वव्यापी व्यवस्था में सुधारा जा सकता है। सामान्यतः डेटा संरचना में कुछ अवधि के समय किए गए अद्यतनों और प्रश्नों की एक श्रृंखला सम्मिलित होती है। बता दें कि U = [ut1, ut2, ut3, ..., utm] t1 से tm तक अद्यतन संचालन का क्रम है जैसे कि t1 < t2 < ... < tm । यहाँ धारणा यह है कि निश्चित समय t के लिए अधिकतम एक संचालन किया जा सकता है।
आंशिक रूप से पूर्वव्यापी
हम डेटा संरचना को आंशिक रूप से पूर्वव्यापी होने के लिए परिभाषित करते हैं यदि यह वर्तमान समय में अद्यतन और प्रश्न संचालन कर सकता है और विगत में सम्मिलन और विलोपन संचालन का समर्थन कर सकता है। इस प्रकार आंशिक रूप से पूर्वव्यापी के लिए हम निम्नलिखित कार्यों में रुचि रखते हैं:
- सम्मिलित करें(t,u): समय t पर सूची u में एक नवीन संचालन u डालें।
- विलोपन(t): सूची u से समय t पर संचालन विलोपित करें।
उपरोक्त पूर्वव्यापी संचालन को देखते हुए, एक मानक सम्मिलन संचालन अब इन्सर्ट(t, इन्सर्ट(x)) का रूप होगा। डेटा संरचना के परिचालन इतिहास पर सभी पूर्वव्यापी परिवर्तन संभावित रूप से संचालन के समय से लेकर वर्तमान तक के सभी कार्यों को प्रभावित कर सकते हैं। उदाहरण के लिए, यदि हमारे समीप ti-1 < t < ti+1 है, तो इन्सर्ट(t, इन्सर्ट(x)) नवीन संचालन, op, संचालन opi-1 और opi+1 के बीच रखेगा। डेटा संरचना की वर्तमान स्थिति(अर्थात्: वर्तमान समय में डेटा संरचना) तब ऐसी स्थिति में होगी जैसे संचालन opi-1, op और opi+1 सभी क्रम में होते हैं, जैसे कि संचालन op सदैव होता था। दृश्य उदाहरण के लिए चित्र 1 और 2 देखें।
पूर्ण रूप से पूर्वव्यापी
हम डेटा संरचना को पूर्ण रूप से पूर्वव्यापी होने के लिए परिभाषित करते हैं यदि आंशिक रूप से पूर्वव्यापी संचालन के अतिरिक्त हम किसी को विगत के विषय में पूछताछ करने की अनुमति भी देते हैं। आंशिक रूप से पूर्वव्यापी मॉडल में मानक संचालन इन्सर्ट(x) कैसे इन्सर्ट(t, इन्सर्ट(x)) बन जाता है, इसी प्रकार पूर्ण रूप से पूर्वव्यापी मॉडल में संचालन क्वेरी(x) का रूप अब क्वेरी(t, क्वेरी(x)) है।
पूर्वव्यापी चलने का समय
पूर्वव्यापी डेटा संरचनाओं के चलने का समय संचालन की संख्या पर आधारित होता है, m, संरचना पर किया जाता है, संचालन की संख्या r जो पूर्वव्यापी संचालन से पूर्व किया जाता है, और किसी एक समय में संरचना में n अवयवों की अधिकतम संख्या है।
स्वचालित पूर्व-गतिविधि
डेटा संरचनाओं के संबंध में स्वत: पूर्व-गतिविधि के संबंध में मुख्य प्रश्न यह है कि क्या कोई सामान्य तकनीक है जो किसी भी डेटा संरचना को एक दक्ष पूर्वव्यापी समकक्ष में परिवर्तित कर सकती है या नहीं। लागू होने वाले पूर्वव्यापी संचालन से पूर्व संरचना में किए गए सभी परिवर्तनों पर नियमावली-वापस करना सरल उपाय है। एकदा जब हम डेटा संरचना को उपयुक्त स्थिति में वापस कर देते हैं, तो हम जो परिवर्तन चाहते हैं, उसे करने के लिए पूर्वव्यापी संचालन लागू कर सकते हैं। एकदा परिवर्तन किए जाने के बाद हमें डेटा संरचना को उसकी नवीन स्थिति में लाने के लिए पूर्व किए गए सभी परिवर्तनों को फिर से लागू करना होगा। जबकि यह किसी भी डेटा संरचना के लिए काम कर सकता है, यह प्रायः अदक्ष और व्यर्थ होता है, विशेष रूप से एकदा नियमावली-वापस करने के लिए आवश्यक परिवर्तनों की संख्या बड़ी होने के बाद। एक दक्ष पूर्वव्यापी डेटा संरचना बनाने के लिए हमें यह निर्धारित करने के लिए संरचना के गुणों पर दृष्टि डालनी चाहिए कि गति को कहाँ सिद्ध किया जा सकता है। इस प्रकार किसी भी डेटा संरचना को एक दक्ष पूर्वव्यापी समकक्ष में परिवर्तित करने का कोई सामान्य विधि नहीं है। एरिक डी. डेमैन, जॉन इकोनो और स्टीफन लैंगरमैन इसे सिद्ध करते हैं।[1]
यह भी देखें
संदर्भ
- ↑ 1.0 1.1 Demaine, Erik D.; Iacono, John; Langerman, Stefan (2007). "पूर्वव्यापी डेटा संरचनाएं". ACM Transactions on Algorithms. 3 (2): 13. doi:10.1145/1240233.1240236. S2CID 5555302. Retrieved 21 April 2012.
