2012-04-05 33 views
16

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

उत्तर

20

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

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

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

+0

आप एक पूरी तरह से लगातार डेटा संरचना नक्शा है, और आप पहले से ही सेट किया है, तो (1, 1), यदि आप फिर से (1, 1) सेट करते हैं, तो इसे एक उत्परिवर्तन माना जाता है, और क्या आपको डेटा संरचना का एक नया संस्करण वापस करना चाहिए, ev अगर कुछ भी वास्तव में बदल गया है? – CMCDragonkai

+0

@CMCDragonkai, मुझे नहीं लगता कि उस प्रश्न का एक "सही" जवाब है। – jbapple

12

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