लगातार बनाम अपरिवर्तनीय डेटा संरचना

Question

क्या लगातार और अपरिवर्तनीय डेटा संरचना में कोई अंतर है? दृढ़ता पर चर्चा करते समय विकिपीडिया अपरिवर्तनीय डेटा संरचना को संदर्भित करता है लेकिन मुझे लगता है कि दोनों के बीच एक सूक्ष्म अंतर हो सकता है।

Answer 1

अपरिवर्तनीयता एक कार्यान्वयन तकनीक है। अन्य चीजों के अलावा, यह दृढ़ता प्रदान करता है, जो एक इंटरफ़ेस है। संस्करण v पर

• version update(operation o, version v) प्रदर्शन आपरेशन o, एक नया संस्करण लौटने: हठ API जैसी कोई चीज़ है। यदि डेटा संरचना अपरिवर्तनीय है, तो नया संस्करण एक नई संरचना है (जो पुरानी संरचना के अपरिवर्तनीय हिस्सों को साझा कर सकता है)। यदि डेटा संरचना अपरिवर्तनीय नहीं है, तो लौटा संस्करण केवल संस्करण संख्या हो सकता है। संस्करण v एक वैध संस्करण बना हुआ है, और इसे किसी भी observe में इस अद्यतन के कारण-योग्य तरीके से नहीं बदला जाना चाहिए - अद्यतन केवल लौटा संस्करण में दिखाई देता है, v में नहीं।
• data observe(query q, version v) इसे बदलने या नया संस्करण बनाने के बिना संस्करण v पर डेटा संरचना को देखता है।

इन मतभेदों के बारे में अधिक के लिए देखें:

• The chapter "Persistent data structures" by Haim Kaplan in Handbook on Data Structures and Applications
• "Making Data Structures Persistent" by Driscoll et al.
• The first lecture of the Spring 2012 incarnation of MIT's 6.851: Advanced Data Structures

Answer 2

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