स्थायी डेटा संरचना

कम्प्यूटिंग में, सतत आंकड़ा संरचना या पूरक क्षणिक आंकड़ा संरचना है जो संशोधित होने पर हमेशा अपने पिछले संस्करण को संरक्षित करती है। ऐसी आंकड़ा संरचनाएं प्रभावी रूप से अपरिवर्त्य वस्तु हैं, क्योंकि उनके संचालन जगह-जगह संरचना को नवीनीकरण नहीं करते हैं, बल्कि हमेशा एक नई अद्यतन संरचना उत्पन्न करते हैं। यह शब्द ड्रिस्कॉल, सरनाक, सलेटर और टारजन्स के 1986 के लेख में पेश किया गया था।^[1]

सभी संस्करणों तक पहुँचा जा सकता है, लेकिन केवल नवीनतम संस्करण को संशोधित किया जा सकता है, तो आंकड़ा संरचना आंशिक रूप से स्थायी होती है। यदि प्रत्येक संस्करण को अभिगम और संशोधित दोनों किया जा सकता है, तो आंकड़ा संरचना पूरी तरह से स्थायी है। यदि कोई मिश्रण या विलय ऑपरेशन भी है जो पिछले दो संस्करणों से नया संस्करण बना सकता है, तो आंकड़ा संरचना को धाराप्रवाह लगातार कहा जाता है। ऐसी संरचनाएं जो स्थायी नहीं होती हैं उन्हें 'अल्पकालिक' कहा जाता है।^[2]

तर्क प्रोग्रामिंग और कार्यात्मक प्रोग्रामिंग में इस प्रकार की आंकड़ा संरचनाएं विशेष रूप से आम हैं,^[2]उन प्रतिमानों में भाषाओं के रूप में परिवर्तनशील आंकड़ा के उपयोग को हतोत्साहित (या पूरी तरह से मना) करते हैं।

आंशिक बनाम पूर्ण दृढ़ता

आंशिक दृढ़ता मॉडल में, प्रोग्रामर आंकड़ा संरचना के किसी भी पिछले संस्करण को परिप्रश्न कर सकता है, लेकिन केवल नवीनतम संस्करण को नवीनीकरण कर सकता है। इसका तात्पर्य आंकड़ा संरचना के प्रत्येक संस्करण के बीच कुल क्रम से है।^[3] पूरी तरह से स्थायी मॉडल में, आंकड़ा संरचना के किसी भी संस्करण पर अद्यतन और प्रश्न दोनों की अनुमति है। कुछ स्थितियों में आंकड़ा संरचना के पुराने संस्करणों को परिप्रश्न या नवीनीकरण करने के कंप्यूटर के प्रदर्शन को अपक्षीणन की अनुमति दी जा सकती है, जैसा कि रोप (आंकड़ा संरचना) के साथ सच है।^[4] इसके अतिरिक्त, आंकड़ा संरचना को धाराप्रवाह रूप से लगातार के रूप में संदर्भित किया जा सकता है, यदि पूरी तरह से लगातार होने के अतिरिक्त, एक ही आंकड़ा संरचना के दो संस्करणों को नया संस्करण बनाने के लिए जोड़ा जा सकता है जो अभी भी पूरी तरह से स्थायी है।^[5]

पिछले संस्करणों के संरक्षण के लिए तकनीक

कॉपी-ऑन-राइट

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

फैट नोड

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

फैट नोड की जटिलता

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

पाथ कॉपीइंग

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

पाथ कॉपीइंग की जटिलता

m संशोधनों के साथ, यह O(log m) योगात्मक लुकअप तालिका समय लागत है। संशोधन समय और स्थान आंकड़ा संरचना में सबसे लंबे पथ के आकार और क्षणिक आंकड़ा संरचना में अद्यतन की लागत से बंधे हैं। मूल पॉइंटर्स के बिना बैलेंस्ड द्विभाजी अन्वेषण ट्री में सबसे खराब स्थिति संशोधन समय जटिलता O(log n + नवीनीकरण लागत) है। हालाँकि, संयोजन की गई सूची में सबसे खराब स्थिति संशोधन समय जटिलता O (n + अद्यतन लागत) है।

संयोजन

ड्रिस्कॉल, सरनाक, डेनियल स्लेटर, रॉबर्ट टार्जन आए^[1]फैट नोड्स और पाथ कॉपीइंग की तकनीकों को संयोजित करने के तरीके के साथ, O(1) पहुंच मंदी और O(1) संशोधन स्थान और समय जटिलता प्राप्त करना है।

प्रत्येक नोड में, संशोधन बॉक्स संग्रहीत होता है। यह बॉक्स नोड में संशोधन को नियन्त्रित कर सकता है—या तो पॉइंटर्स में से किसी एक के लिए संशोधन, या नोड की कुंजी, या नोड-विशिष्ट आंकड़ा के किसी अन्य भाग के लिए—और उस संशोधन को लागू करने के लिए टाइमस्टैम्प है। प्रारंभ में, प्रत्येक नोड का संशोधन बॉक्स खाली होता है।

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

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

इस कलन विधि के साथ, किसी भी समय t को देखते हुए, समय t के साथ आंकड़ा संरचना में अधिकतम संशोधन बॉक्स सम्मिलित होता है। इस प्रकार, समय t पर संशोधन को तीन भागों में विभाजित करता है: एक भाग में समय t से पहले का आंकड़ा होता है, एक भाग में समय t के बाद का आंकड़ा होता है, और एक भाग संशोधन से अप्रभावित रहता है।

संयोजन की जटिलता

संशोधनों के लिए समय और स्थान को परिशोधित विश्लेषण की आवश्यकता होती है। संशोधन O(1) परिशोधित स्थान और O(1) परिशोधित समय लेता है। यह देखने के लिए कि क्यों, संभावित विधि ϕ का उपयोग करें, जहां ϕ(T), T में पूर्ण लाइव नोड्स की संख्या है। T के लाइव नोड्स केवल वे नोड हैं जो वर्तमान समय में वर्तमान मूलरूप से उपलब्ध हैं (अर्थात, अंतिम संशोधन के बाद)। पूर्ण लाइव नोड वे लाइव नोड हैं जिनके संशोधन बॉक्स भरे हुए हैं।

प्रत्येक संशोधन में कुछ संख्या में प्रतियां सम्मिलित होती हैं, k कहते हैं, जिसके बाद संशोधन बॉक्स में 1 चेंज होता है। प्रत्येक k प्रतियों पर विचार करें। प्रत्येक की लागत O(1) स्थान और समय है, लेकिन संभावित कार्य को एक से कम कर देता है। (सबसे पहले, कॉपी किया जाने वाला नोड पूर्ण और सजीवता होना चाहिए, इसलिए यह संभावित फ़ंक्शन में योगदान देता है। संभावित फ़ंक्शन केवल तभी गिरेगा, यदि पुराना नोड नए ट्री में उपलब्ध नहीं है। लेकिन यह ज्ञात है कि यह नए ट्री में पहुंच योग्य नहीं है—कलन विधि में अगला चरण कॉपी को इंगित करने के लिए नोड के मूल को संशोधित करना होता है। अंत में, यह ज्ञात है कि कॉपी का संशोधन बॉक्स खाली है। इस प्रकार, पूर्ण लाइव नोड को बदल दिया गया है खाली लाइव नोड के साथ प्रतिस्थापित किया जाता है, और ϕ एक से नीचे चला जाता है।) अंतिम चरण एक संशोधन बॉक्स भरता है, जिसकी लागत O(1) समय होती है और ϕ एक से बढ़ जाती है।

इन सभी को एक साथ रखने पर, ϕ में चेंज Δϕ =1− k है। इस प्रकार, कलन विधि O(k +Δϕ)= O(1) स्थान और O(k +Δϕ +1) = O(1) समय लेता है

दृढ़ता का सामान्यीकृत रूप

पाथ कॉपी करना एक निश्चित आंकड़ा संरचना जैसे द्विभाजी अन्वेषण ट्री में दृढ़ता प्राप्त करने के सरल तरीकों में से एक है। दृढ़ता को लागू करने के लिए सामान्य रणनीति होना अच्छा है जो किसी भी आंकड़ा संरचना के साथ काम करता है। इसे प्राप्त करने के लिए, हम निर्देशित ग्राफ पर विचार करते हैं $G$ . हम मानते हैं कि प्रत्येक शीर्ष $v$ में $G$ की स्थिर संख्या है $c$ बहिर्गामी किनारों का जो पॉइंटर्स द्वारा दर्शाए जाते हैं। प्रत्येक शीर्षकोण में आंकड़ा का प्रतिनिधित्व करने वाला लेबल होता है। हम मानते हैं कि शीर्ष की परिबद्ध संख्या होती है इसमें d जाने वाले किनारों के जिन्हें हम inedges( $v$ ) के रूप में परिभाषित करते हैं, हम निम्नलिखित विभिन्न परिचालनों को चालू करने की अनुमति देते हैं $G$ .

क्रिएट-नोड (): एक नया शीर्षकोण बनाता है जिसमें कोई आगमिक या बहिर्गामी एज नहीं होता है।
चेंज-एज ( $v$ , $i$ , $u$ ): बदलता है $i$ ^th का किनारा $v$ केंद्र से $u$ केंद्र तक
लेबल चेंज ( $v$ , $x$ ): पर संग्रहीत आंकड़ा के मान को बदलता है $v$ को $x$

उपरोक्त में से कोई भी ऑपरेशन विशिष्ट समय पर किया जाता है और लगातार ग्राफ प्रतिनिधित्व का उद्देश्य किसी भी संस्करण का उपयोग $G$ दिये गये समय पर करने में सक्षम होना है। इस उद्देश्य के लिए हम प्रत्येक शीर्ष के लिए तालिका परिभाषित करते हैं $v$ में $G$ , तालिका में $c$ कॉलम और $d+1$ पंक्तियाँ सम्मिलित है। प्रत्येक पंक्ति में बहिर्गामी किनारों के लिए पॉइंटर्स के अतिरिक्त, एक लेबल होता है जो शीर्ष पर आंकड़ा का प्रतिनिधित्व करता है और समय $t$ जिस पर ऑपरेशन किया गया है। इसके अतिरिक्त ऐरे inedges(v) है जो आने वाले सभी $v$ किनारों का ट्रैक रखता है, जब तालिका भर जाती है, तो नई तालिका के साथ $d+1$ कतारें बनाई जा सकती हैं। पुरानी तालिका निष्क्रिय हो जाती है और नई तालिका सक्रिय तालिका बन जाती है।

क्रिएट-नोड

क्रिएट-नोड के लिए कॉल एक नई तालिका बनाता है और सभी संदर्भों को शून्य पर उत्पन्न करता है

चेंज-एज

यदि हम मान लें कि चेंज-एज ( $v$ , $i$ , $u$ ) कहा जाता है, तो विचार करने के लिए दो मामले हैं।

शीर्ष की तालिका में एक खाली पंक्ति है $v$ : इस मामले में हम तालिका में अंतिम पंक्ति की प्रतिलिपि बनाते हैं और हम इसे बदलते हैं $i$ th शिखर का किनारा $v$ नए शीर्ष $u$ को इंगित करने के लिए है
शिखर की तालिका $v$ भर गया है: इस मामले में हमें नई तालिका बनाने की जरूरत है। हम पुरानी तालिका की अंतिम पंक्ति को नई तालिका में कॉपी करते हैं। हमें ऐरे inedges( $v$ ) में लूप करने की आवश्यकता है ऐरे में प्रत्येक शीर्ष को नई बनाई गई तालिका की ओर इंगित करने के लिए है। इसके अतिरिक्त, हमें प्रविष्टि को बदलने की आवश्यकता है $v$ प्रत्येक शीर्ष के लिए inedges(w) में $w$ ऐसा किनारा $v,w$ ग्राफ $G$ में सम्मिलित है

चेंज-लेबल

यह चेंज-एज के समान ही काम करता है सिवाय इसके कि इसे बदलने के अतिरिक्त $i$ ^th शीर्ष के किनारे, हम $i$ ^th लेबल बदलते हैं।

सामान्यीकृत लगातार आंकड़ा संरचना की दक्षता

ऊपर प्रस्तावित योजना की दक्षता का पता लगाने के लिए, हम ऋण योजना के रूप में परिभाषित तर्क का उपयोग करते हैं। ऋण मुद्रा का प्रतिनिधित्व करता है। उदाहरण के लिए ऋण का उपयोग तालिका के भुगतान के लिए किया जा सकता है। तर्क निम्नलिखित बताता है:

तालिका बनाने के लिए ऋण की आवश्यकता होती है
क्रिएट-नोड के लिए प्रत्येक कॉल दो ऋण के साथ आती है
चेंज-एज की प्रत्येक कॉल ऋण के साथ आती है

ऋण योजना को हमेशा निम्नलिखित अपरिवर्त्य को संतुष्ट करना चाहिए: प्रत्येक सक्रिय तालिका की प्रत्येक पंक्ति में ऋण होता है और तालिका में पंक्तियों की संख्या के समान ऋण होते हैं। आइए पुष्टि करें कि इनवेरिएंट तीनों ऑपरेशन क्रिएट-नोड, चेंज-एज और चेंज-लेबल पर लागू होता है।

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

संक्षेप में, हम यह निष्कर्ष निकालते हैं कि $n_{1}$ क्रिएट-नोड को कॉल करता है और $n_{2}$ चेंज-एज को कॉल करने से $2\cdot n_{1}+n_{2}$ तालिका का निर्माण होता है। चूंकि प्रत्येक तालिका का आकार होता है $O(d)$ पुनरावर्ती कॉलों को ध्यान में रखे बिना, फिर तालिका भरने की आवश्यकता होती है $O(d^{2})$ जहां अतिरिक्त डी कारक अन्य नोड्स पर किनारे को अद्यतन करने से आता है। इसलिए संचालन के अनुक्रम को पूरा करने के लिए आवश्यक कार्य की मात्रा $O(d^{2})$ गुणा की गई तालिकाओं की संख्या से बंधी हुई है, प्रत्येक अभिगम ऑपरेशन में किया जा सकता है $O(Log(d))$ और वहाँ है $m$ किनारे और लेबल संचालन, इस प्रकार इसकी $m\cdot O(Log(d))$ आवश्यकता होती है। हम निष्कर्ष निकालते हैं कि आंकड़ा संरचना सम्मिलित है जो किसी को भी $n$ क्रिएट-नोड, चेंज-एज और चेंज-लेबल का क्रम $O(n\cdot d^{2})+m\cdot O(Log(d))$ पूरा कर सकती है।

लगातार आंकड़ा संरचनाओं के अनुप्रयोग

नेक्स्ट एलिमेंट सर्च या बिंदु स्थान

उपयोगी अनुप्रयोगों में से जिसे दृढ़ता का उपयोग करके कुशलता से हल किया जा सकता है, वह नेक्स्ट एलिमेंट सर्च है। मान लीजिए कि हैं $n$ गैर-प्रतिच्छेदी रेखा खंड जो एक दूसरे को पार नहीं करते हैं जो x-अक्ष के समानांतर हैं। हम एक आंकड़ा संरचना बनाना चाहते हैं जो एक बिंदु को परिप्रश्न कर सके $p$ और उपरोक्त खंड वापस करें $p$ (यदि कोई)। हम नेव पद्धति का उपयोग करके नेक्स्ट एलिमेंट सर्च को हल करके शुरू करेंगे, फिर हम यह दिखाएंगे कि लगातार आंकड़ा संरचना पद्धति का उपयोग करके इसे कैसे हल किया जाता है।

नेव विधि

हम लंबवत रेखा खंड से शुरू करते हैं जो अनंत से शुरू होता है और हम रेखा खंडों को बाएं से दाएं घुमाते हैं। हर बार जब हम इन खंडों के अंत बिंदु का सामना करते हैं तो हम विराम लेते हैं। ऊर्ध्वाधर रेखाएँ विमान को ऊर्ध्वाधर पट्टियों में विभाजित करती हैं। यदि वहाँ $n$ रेखा खंड तब हम प्राप्त $2\cdot n+1$ कर सकते हैं, लंबवत पट्टियां क्योंकि प्रत्येक खंड में $2$ अंत बिंदु है। कोई खंड पट्टी में शुरू और समाप्त नहीं होता है। हर खंड या तो पट्टी को छूता नहीं है या पूरी तरह से इसे पार कर जाता है। हम खंडों को कुछ वस्तुओं के रूप में सोच सकते हैं जो किसी क्रमबद्ध क्रम में ऊपर से नीचे तक हैं। हम इस बात की परवाह करते हैं कि हम जिस बिंदु को देख रहे हैं वह इस क्रम में कहां फिट बैठता है। हम खंड केअंतबिंदु को उनके $x$ समन्वय द्वारा भेद करते हैं। प्रत्येक पट्टी के लिए $s_{i}$ , हम पार करने वाले उपवर्ग खंड को $s_{i}$ शब्दकोश मे भण्डार करते हैं। जब ऊर्ध्वाधर रेखा, रेखा खंड को प्रसर्प करती है, जब भी यह खंड के बायें अंतबिंदु के ऊपर से गुजरती है तो हम इसे कोश में जोड़ देते हैं। जब यह खंड के दाहिने समापन बिंदु से होकर गुजरता है, तो हम इसे शब्दकोश से हटा देते हैं। प्रत्येक समापन बिंदु पर, हम शब्दकोश की प्रति सहेजते हैं और हम $x$ निर्देशांक द्वारा क्रमबद्ध सभी प्रतियाँ संग्रहीत करते हैं। इस प्रकार हमारे पास आंकड़ा संरचना है जो किसी भी प्रश्न का उत्तर दे सकती है। एक बिंदु के ऊपर खंड खोजने के लिए $p$ , हम देख सकते हैं $x$ का समन्वय $p$ यह जानने के लिए कि यह किस प्रति या पट्टी का है। तब हम देख सकते हैं $y$ इसके ऊपर के खंड को खोजने के लिए समन्वय करें। इस प्रकार हमें दो द्वयाधारी खोजों की आवश्यकता है, एक के लिए $x$ पट्टी या प्रतिलिपि खोजने के लिए समन्वय करें, और दूसरा इसके लिए $y$ इसके ऊपर के खंड को खोजने के लिए समन्वय करें। इस प्रकार परिप्रश्न $O(Log(n))$ समय लगता है इस आंकड़ा संरचना में, स्थान मुद्दा है क्योंकि यदि हम मानते हैं कि हमारे पास खंड इस तरह से संरचित हैं कि प्रत्येक खंड किसी अन्य खंड के अंत से पहले शुरू होता है, तो नेव विधि का उपयोग करके संरचना के निर्माण के लिए $O(n^{2})$ आवश्यक स्थान होगा।आइए देखें कि हम एक ही परिप्रश्न समय के साथ लेकिन बेहतर स्थान के साथ एक और लगातार आंकड़ा संरचना कैसे बना सकते हैं।

लगातार आंकड़ा संरचना विधि

हम देख सकते हैं कि नेव पद्धति में उपयोग की जाने वाली आंकड़ा संरचना में वास्तव में जो समय लगता है, वह यह है कि जब भी हम एक पट्टी से अगली पट्टी पर जाते हैं, तो हमें क्रमबद्ध क्रम में रखने के लिए हम जो भी आंकड़ा संरचना का उपयोग कर रहे हैं, उसका आशुचित्र लेने की आवश्यकता होती है। हम देख सकते हैं कि एक बार हमें खंड मिलते हैं जो प्रतिच्छेद $s_{i}$ करते हैं , जब हम $s_{i+1}$ जाते हैं या तो चीज छूटती है या प्रवेश करती है। यदि जो है उसमें $s_{i}$ अंतर है और इसमें $s_{i+1}$ क्या है केवल सम्मिलन या विलोपन है तो सब कुछ कॉपी करना अच्छा विचार $s_{i}$ को $s_{i+1}$ नहीं है चाल यह है कि चूंकि प्रत्येक प्रति पिछले एक से केवल एक सम्मिलन या विलोपन से भिन्न होती है, इसलिए हमें केवल उन भागों की प्रतिलिपि बनाने की आवश्यकता होती है जो बदलते हैं। मान लीजिए कि हमारे पास एक ट्री है जिसकी जड़ें $T$ हैं जब हम कुंजी डालते हैं $k$ ट्री में, हम नया पत्ता युक्त $k$ बनाते हैं . ट्री को पुनर्संतुलित करने के लिए घूर्णन करने से केवल पथ के नोड्स संशोधित होंगे $k$ को $T$ चाबी डालने से पहले $k$ ट्री में, हम रास्ते के सभी नोड्स $k$ को $T$ कॉपी करते हैं अब हमारे पास ट्री के 2 संस्करण हैं, मूल जिसमें सम्मिलित नहीं है $k$ और नया ट्री जिसमें $k$ सम्मिलित है और किसकी मूलरूप की $T$ कॉपी है से पथ की प्रतिलिपि बनाने के बाद से $k$ को $T$ स्थिर कारक से अधिक सम्मिलन समय में वृद्धि नहीं करता है तो लगातार आंकड़ा संरचना में सम्मिलन $O(Log(n))$ समय लेता है। विलोपन के लिए, हमें यह पता लगाने की आवश्यकता है कि विलोपन से कौन से नोड प्रभावित होंगे। प्रत्येक नोड के लिए $v$ विलोपन से प्रभावित, हम पथ को मूलरूप से कॉपी करते हैं $v$ . यह एक नया ट्री प्रदान करेगा जिसकी मूलरूप मूल ट्री की मूलरूप की कॉपी है। फिर हम नए ट्री पर विलोपन करते हैं। हम ट्री के 2 संस्करणों के साथ समाप्त करेंगे। मूल एक जिसमें सम्मिलित है $k$ और नया जिसमें सम्मिलित नहीं है $k$ . चूँकि कोई भी विलोपन केवल पथ को मूलरूप से $v$ संशोधित करता है और कोई भी उपयुक्त विलोपन एल्गोरिथम चलता है $O(Log(n))$ , इस प्रकार लगातार आंकड़ा संरचना में विलोपन $O(Log(n))$ होता है, सम्मिलन और विलोपन का प्रत्येक क्रम शब्दकोशों या संस्करणों या ट्री के अनुक्रम के निर्माण का कारण बनेगा $S_{1},S_{2},\dots S_{i}$ जहां प्रत्येक $S_{i}$ क्रियाओं का परिणाम $S_{1},S_{2},\dots S_{i}$ है यदि प्रत्येक $S_{i}$ , $m$ तत्व, फिर प्रत्येक खोज में $S_{i}$ , $O(Log(m))$ लेता है इस लगातार आंकड़ा संरचना का उपयोग करके हम अगले तत्व खोज समस्या को हल कर सकते हैं $O(Log(n))$ परिप्रश्न समय और $O(n\cdot Log(n))$ के अतिरिक्त स्थल $O(n^{2})$ अगली खोज समस्या से संबंधित उदाहरण के लिए कृपया स्रोत कोड के नीचे खोज सकते है।

लगातार आंकड़ा संरचनाओं के उदाहरण

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

कई सामान्य संदर्भ-आधारित आंकड़ा संरचनाएं, जैसे कि रेड–ब्लैक ट्री,^[6] ढेर (सार जानकारी प्रकार),^[7] और ट्रेप्स,^[8] एक स्थायी संस्करण बनाने के लिए आसानी से अनुकूलित किया जा सकता है। कुछ अन्य लोगों को थोड़ा और प्रयास करने की आवश्यकता है, उदाहरण के लिए: कतार (आंकड़ा संरचना), डबल-एंडेड कतार, और मिन-डेक सहित एक्सटेंशन (जिसमें एक अतिरिक्त O (1) ऑपरेशन मिनट न्यूनतम तत्व लौटाता है) और रैंडम एक्सेस डेक (जिसमें है सब-लीनियर के साथ रैंडम अभिगम का अतिरिक्त ऑपरेशन, सबसे अधिक बार लॉगरिदमिक, जटिलता) है।

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

संयोजन की गई सूचियां

एकल रूप से जुड़ी हुई सूचियाँ कार्यात्मक भाषाओं में ब्रेड-एंड-बटर आंकड़ा संरचना हैं।^[9] कुछ एमएल प्रोग्रामिंग भाषा-व्युत्पन्न भाषाएं, जैसे हास्केल (प्रोग्रामिंग भाषा), विशुद्ध रूप से कार्यात्मक हैं क्योंकि एक बार सूची में नोड आवंटित किए जाने के बाद, इसे संशोधित नहीं किया जा सकता है, केवल कचरा संग्रह (कंप्यूटर विज्ञान) द्वारा कॉपी, संदर्भित या नष्ट किया जा सकता है जब कुछ भी नहीं इसे संदर्भित करता है। (ध्यान दें कि एमएल स्वयं विशुद्ध रूप से कार्यात्मक नहीं है, लेकिन गैर-विनाशकारी सूची संचालन उपवर्ग का समर्थन करता है, जो लिस्प (प्रोग्रामिंग भाषा) (एलआईएसटी प्रसंस्करण) कार्यात्मक भाषा बोलियों जैसे रैकेट (प्रोग्रामिंग भाषा) और रैकेट (प्रोग्रामिंग भाषा) में भी सच है। )

दो सूचियों पर विचार करें:

xs = [0, 1, 2]
ys = [3, 4, 5]

इनके द्वारा स्मृति में प्रतिनिधित्व किया जाएगा:

जहां वृत्त सूची में नोड को इंगित करता है (नोड के दूसरे तत्व का प्रतिनिधित्व करने वाला तीर जो दूसरे नोड के लिए सूचक है)।

अब दो सूचियों को जोड़ना:

zs = xs ++ ys

निम्नलिखित स्मृति संरचना में परिणाम:

ध्यान दें कि सूची में नोड्स xs कॉपी किया गया है, लेकिन अंदर नोड्स ys साझा किए जाते हैं। परिणामस्वरूप, मूल सूचियाँ (xs और ys) बना रहता है और संशोधित नहीं किया गया है।

प्रतिलिपि का कारण यह है कि अंतिम नोड xs (मूल मान वाला नोड 2) के प्रारंभ को इंगित करने के लिए संशोधित नहीं किया जा सकता है ys, क्योंकि इससे का मान बदल जाएगा xs.

ट्री

द्विभाजी अन्वेषण ट्री पर विचार करें,^[9]जहां ट्री में प्रत्येक नोड में प्रत्यावर्तन इनवेरिएंट (कंप्यूटर साइंस) है कि बाएं सबट्री में निहित सभी सबनोड्स का मान नोड में संग्रहीत मान से कम या उसके बराबर है, और दाएं सबट्री में निहित सबनोड्स का मान है नोड में संग्रहीत मान से अधिक है।

उदाहरण के लिए, आंकड़ा का उत्पन्न

xs = [a, b, c, d, f, g, h]

निम्नलिखित द्विभाजी अन्वेषण ट्री द्वारा दर्शाया जा सकता है:

एक फ़ंक्शन जो द्वयाधारी ट्री में आंकड़ा सम्मिलित करता है और इनवेरिएंट को बनाए रखता है:

 fun insert (x, E) = T (E, x, E)
   | insert (x, s as T (a, y, b)) =
        if x < y then T (insert (x, a), y, b)
        else if x > y then T (a, y, insert (x, b))
        else s

क्रियान्वित करने के बाद

वाईएस = डालें (ई, एक्सएस)

निम्न समाकृति उत्पन्न होता है:

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

लगातार हैश ऐरे मैप्ड ट्राई

सतत हैश ऐरे मैप्ड ट्राई, हैश ऐरे मैप्ड ट्राई का विशेष रूप है जो किसी भी नवीनीकरण पर अपने पिछले संस्करणों को संरक्षित रखती है। इसका उपयोग अधिकांशतः सामान्य प्रयोजन के सतत मैप्स आंकड़ा संरचना को लागू करने के लिए किया जाता है।^[10]

हैश ऐरे मैप किए गए प्रयासों को मूल रूप से 2001 में फिल बैगवेल द्वारा आइडियल हैश ट्रीज़ नामक पेपर में वर्णित किया गया था। इस पेपर ने म्यूटेबल हैश तालिका प्रस्तुत किया है, जहां इंसर्ट, सर्च और डिलीट का समय छोटा और स्थिर है, कुंजी उत्पन्न आकार से स्वतंत्र है, ऑपरेशन O(1) हैं। इंसर्ट, सर्च और डिलीट के संचालन के लिए सबसे खराब समय की गारंटी दी जा सकती है और सफल खोजों की तुलना में लागत कम होती है।^[11] इस आंकड़ा संरचना को तब रिच हिक्की द्वारा क्लोजर प्रोग्रामिंग भाषा में उपयोग के लिए पूरी तरह से स्थिर होने के लिए संशोधित किया गया था।^[12]

वैचारिक रूप से, हैश ऐरे मैप्ड किसी भी सामान्य ट्री (आंकड़ा संरचना) के समान काम करने की कोशिश करता है, जिसमें वे नोड्स को श्रेणीबद्ध रूप से संग्रहीत करते हैं और किसी विशेष तत्व के नीचे पथ का अनुसरण करके उन्हें पुनः प्राप्त करते हैं। मुख्य अंतर यह है कि हैश ऐरे मैप्ड ट्राइज़ अपनी लुकअप कुंजी को (सामान्यतः 32 या 64 बिट) पूर्णांक में बदलने के लिए पहले हैश फंकशन का उपयोग करते हैं। ट्री के नीचे का रास्ता तब ट्री के प्रत्येक स्तर पर विरल मैट्रिक्स में अनुक्रमित करने के लिए उस पूर्णांक के द्वयाधारी प्रतिनिधित्व के कतली का उपयोग करके निर्धारित किया जाता है। नोड्स हैश तालिका बनाने के लिए उपयोग की जाने वाली समूह के समान व्यवहार करते हैं और हैश टकराव के आधार पर कई उम्मीदवार हो सकते हैं या नहीं भी हो सकते हैं।^[10]

लगातार हैश ऐरे मैप किए गए अधिकांश कार्यान्वयन उनके कार्यान्वयन में 32 के ब्रांचिंग कारक का उपयोग करते हैं। इसका मतलब यह है कि अभ्यास में सतत हैश ऐरे मैप किए गए ट्राइ में सम्मिलन, विलोपन और लुकअप में O(log n) की संगणनात्मक जटिलता होती है, अधिकांश अनुप्रयोगों के लिए वे प्रभावी रूप से निरंतर समय होते हैं, क्योंकि इसके लिए बहुत बड़ी संख्या में प्रविष्टियों की आवश्यकता होती हैं। कोई भी ऑपरेशन करने के लिए एक दर्जन से अधिक कदम उठाए जाते है ।^[13]

प्रोग्रामिंग भाषाओं में उपयोग

हास्केल

हास्केल शुद्ध कार्यात्मक भाषा है और इसलिए उत्परिवर्तन की अनुमति नहीं देता है। इसलिए, भाषा में सभी आंकड़ा संरचनाएं लगातार बनी रहती हैं, क्योंकि कार्यात्मक शब्दार्थ के साथ आंकड़ा संरचना की पिछली स्थिति को संरक्षित नहीं करना असंभव है।^[14] ऐसा इसलिए है क्योंकि आंकड़ा संरचना में कोई भी परिवर्तन जो आंकड़ा संरचना के पिछले संस्करणों को अमान्य कर देगा, समुद्दिष्ट पारदर्शिता का उल्लंघन करता है।

अपने मानक लाइब्रेरी में हास्केल के पास संयोजन सूचियों के लिए कुशल निरंतर कार्यान्वयन है,^[15] मैप्स (आकार संतुलित ट्री के रूप में लागू),^[16] और उत्पन्न^[17] दूसरों के बीच में है।^[18]

क्लोजर

लिस्प (प्रोग्रामिंग भाषा) वर्ग में कई प्रोग्रामिंग भाषाओं की तरह, क्लोजर में संयोजन की गई सूची का कार्यान्वयन होता है, लेकिन अन्य बोलियों के विपरीत इसकी संयोजन सूची के कार्यान्वयन ने समागम द्वारा लगातार बने रहने के अतिरिक्त दृढ़ता को लागू किया है।^[19] क्लोजर में लगातार हैश ऐरे मैप किए गए प्रयासों के आधार पर लगातार वैक्टर, मैप्स और उत्पन्न के कुशल कार्यान्वयन भी होते हैं। ये आंकड़ा संरचनाएं जावा संग्रह ढांचे के अनिवार्य रीड-ओनली भागों को लागू करती हैं।^[20]

क्लोजर भाषा के डिजाइनर परिवर्तनीय आंकड़ा संरचनाओं पर लगातार आंकड़ा संरचनाओं के उपयोग की वकालत करते हैं क्योंकि उनके पास मूल्य अर्थ विज्ञान है जो उन्हें सस्ते उपनामों के साथ धागे के बीच स्वतंत्र रूप से साझा करने योग्य, बनाने में आसान और भाषा स्वतंत्र बनाने का लाभ देता है।^[21]

ये आंकड़ा संरचनाएं समानांतर कंप्यूटिंग के लिए क्लोजर के समर्थन का आधार बनाती हैं क्योंकि वे डेटा रेस और परमाणु तुलना-और-स्वैप शब्दार्थ को दूर करने के लिए संचालन की आसान पुनर्प्रयास की अनुमति देते हैं।^[22]

एल्म

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

एल्म कस्टम दस्तावेज़ ऑब्जेक्ट मॉडल कार्यान्वयन का उपयोग करता है जो एल्म आंकड़ा की निरंतर प्रकृति का लाभ उठाता है। 2016 तक एल्म के डेवलपर्स द्वारा यह बताया गया था कि यह वर्चुअल डोम एल्म भाषा को लोकप्रिय जावास्क्रिप्ट फ्रेमवर्क रियेक्ट (जावास्क्रिप्ट लाइब्रेरी) , एम्बर.जेएस और एंगुलर (अनुप्रयोग प्लेटफॉर्म) की तुलना में एचटीएमएल को तेजी से प्रस्तुत करने की अनुमति देता है।^[24]

जावा

जावा (प्रोग्रामिंग भाषा) विशेष रूप से कार्यात्मक नहीं है। इसके बावजूद, मूल जेडीके पैकेज java.util.concurrent में कॉपीऑनराइटएरेलिस्ट और कॉपीऑनराइटएरेसेट सम्मिलित हैं जो लगातार संरचनाएँ हैं, जिन्हें कॉपी-ऑन-राइट तकनीकों का उपयोग करके लागू किया गया है। जावा, समवर्ती हैशमैप में सामान्य समवर्ती मैप्स कार्यान्वयन, चूंकि, लगातार नहीं है। पूरी तरह से स्थायी संग्रह तृतीय-पक्ष लाइब्रेरी, या अन्य जेवीएम भाषाओं में उपलब्ध हैं।

जावास्क्रिप्ट

लोकप्रिय जावास्क्रिप्ट फ्रंटएंड फ्रेमवर्क रिएक्ट (जावास्क्रिप्ट लाइब्रेरी) का उपयोग अधिकांशतः स्टेट प्रबंधन प्रणाली के साथ किया जाता है जो फ्लक्स आर्किटेक्चर को लागू करता है,^[25]^[26] जिसका लोकप्रिय कार्यान्वयन जावास्क्रिप्ट लाइब्रेरी रेडक्स (जावास्क्रिप्ट लाइब्रेरी) है। रेडक्स लाइब्रेरी एल्म प्रोग्रामिंग भाषा में उपयोग किए जाने वाले स्टेट प्रबंधन पैटर्न से प्रेरित है, जिसका अर्थ है कि यह अनिवार्य है कि उपयोगकर्ता सभी आंकड़ा को लगातार मानते हैं।^[27] परिणाम स्वरुप, रेडक्स परियोजना अनुशंसा करती है कि कुछ स्थितियों में उपयोगकर्ता लागू और कुशल लगातार आंकड़ा संरचनाओं के लिए लाइब्रेरी का उपयोग करते हैं। नियमित जावास्क्रिप्ट वस्तुओं की तुलना करने या प्रतिलिपि बनाने की तुलना में यह कथित तौर पर अधिक प्रदर्शन की अनुमति देता है।^[28]

लगातार आंकड़ा संरचनाओं की एक ऐसी लाइब्रेरी Immutable.js उपलब्ध कराई गई आंकड़ा संरचनाओं पर आधारित है और क्लोजर और स्काला द्वारा लोकप्रिय है।^[29] रेडक्स के प्रलेखन द्वारा इसका उल्लेख उन संभावित लाइब्रेरी में से एक के रूप में किया गया है जो लागू अपरिवर्तनीयता प्रदान कर सकते हैं।^[28]Mori.js क्लोजर में जावास्क्रिप्ट के समान आंकड़ा संरचनाएं लाता है।^[30] Immer.js रुचिकर दृष्टिकोण लाता है जहां कोई वर्तमान को बदलकर अगली अपरिवर्त्य स्थिति बनाता है।^[31] Immer.js नेटिव जावास्क्रिप्ट ऑब्जेक्ट्स का उपयोग करता है न कि कुशल लगातार आंकड़ा संरचनाओं का और आंकड़ा आकार बड़ा होने पर यह प्रदर्शन समस्याओं का कारण बन सकता है।

प्रोलॉग

प्रोलॉग की शर्तें स्वाभाविक रूप से अपरिवर्त्य हैं और इसलिए आंकड़ा संरचनाएं सामान्यतः लगातार आंकड़ा संरचनाएं होती हैं। उनका प्रदर्शन प्रोलॉग प्रणाली द्वारा प्रस्तावित साझाकरण और कचरा संग्रह पर निर्भर करता है।^[32] सर्च स्पेस एक्सप्लोसिव के कारण गैर-जमीनी प्रोलॉग शर्तों के विस्तार हमेशा संभव नहीं होते हैं। विलंबित लक्ष्य समस्या को कम कर सकते हैं।

कुछ प्रोलॉग प्रणाली फिर भी सेटर्ग/3 जैसे विनाशकारी संचालन प्रदान करते हैं, जो अलग-अलग सुरुचि में कॉपी के साथ/बिना और स्टेट चेंज के बैकट्रैकिंग के साथ/बिना आ सकते हैं। ऐसे मामले हैं जहां प्रतिबंध सॉल्वर की तरह नई घोषणात्मक परत प्रदान करने के लिए सेटर्ग/3 का उपयोग किया जाता है।^[33]

स्कैला

स्काला प्रोग्रामिंग लैंग्वेज ऑब्जेक्ट-फंक्शनल स्टाइल का उपयोग करके कार्यक्रमों को लागू करने के लिए लगातार आंकड़ा संरचनाओं के उपयोग को बढ़ावा देती है।^[34] स्काला में संयोजन लिस्ट, रेड-ब्लैक ट्री सहित कई परसिस्टेंट आंकड़ा स्ट्रक्चर्स के कार्यान्वयन के साथ-साथ क्लोजर में पेश किए गए लगातार हैश ऐरे मैप किए गए प्रयास सम्मिलित हैं।^[35]

कचरा संग्रह

क्योंकि लगातार आंकड़ा संरचनाएँ अधिकांशतः इस तरह से कार्यान्वित की जाती हैं कि आंकड़ा संरचना के क्रमिक संस्करण अंतर्निहित मेमोरी को साझा करते हैं^[36] ऐसी आंकड़ा संरचनाओं के श्रमदक्षताशास्त्र उपयोग के लिए सामान्यतः स्वचालित कचरा संग्रह प्रणाली के कुछ रूपों की आवश्यकता होती है जैसे संदर्भ गिनती या मार्क और प्रसर्प ^[37] कुछ प्लेटफार्मों में जहां लगातार आंकड़ा संरचनाओं का उपयोग किया जाता है, यह कचरा संग्रह का उपयोग न करने का विकल्प है, ऐसा करने से मेमोरी लीक हो सकती है, कुछ स्थितियों में किसी अनुप्रयोग के समग्र प्रदर्शन पर सकारात्मक प्रभाव पड़ सकता है।^[38]

यह भी देखें

संदर्भ

↑ ^1.0 ^1.1 Driscoll JR, Sarnak N, Sleator DD, Tarjan RE (1986). "Making data structures persistent". Proceedings of the eighteenth annual ACM symposium on Theory of computing - STOC '86. pp. 109–121. CiteSeerX 10.1.1.133.4630. doi:10.1145/12130.12142. ISBN 978-0-89791-193-1. S2CID 364871. {{cite book}}: |journal= ignored (help)
↑ ^2.0 ^2.1 Kaplan, Haim (2001). "लगातार डेटा संरचनाएं". Handbook on Data Structures and Applications.
↑ Conchon, Sylvain; Filliâtre, Jean-Christophe (2008), "Semi-persistent Data Structures", Programming Languages and Systems, Lecture Notes in Computer Science, vol. 4960, Springer Berlin Heidelberg, pp. 322–336, doi:10.1007/978-3-540-78739-6_25, ISBN 9783540787389
↑ Tiark, Bagwell, Philip Rompf (2011). RRB-Trees: Efficient Immutable Vectors. OCLC 820379112.{{cite book}}: CS1 maint: multiple names: authors list (link)
↑ Brodal, Gerth Stølting; Makris, Christos; Tsichlas, Kostas (2006), "Purely Functional Worst Case Constant Time Catenable Sorted Lists", Lecture Notes in Computer Science, Springer Berlin Heidelberg, pp. 172–183, CiteSeerX 10.1.1.70.1493, doi:10.1007/11841036_18, ISBN 9783540388753
↑ Neil Sarnak; Robert E. Tarjan (1986). "निरन्तर खोज वृक्षों का प्रयोग करते हुए तलीय बिन्दु स्थान" (PDF). Communications of the ACM. 29 (7): 669–679. doi:10.1145/6138.6151. S2CID 8745316. Archived from the original (PDF) on 2015-10-10. Retrieved 2011-04-06.
↑ Chris Okasaki. "विशुद्ध रूप से कार्यात्मक डेटा संरचनाएं (थीसिस)" (PDF). {{cite journal}}: Cite journal requires |journal= (help)
↑ Liljenzin, Olle (2013). "लगातार लगातार सेट और मानचित्र". arXiv:1301.3388. Bibcode:2013arXiv1301.3388L. {{cite journal}}: Cite journal requires |journal= (help)
↑ ^9.0 ^9.1 This example is taken from Okasaki. See the bibliography.
↑ ^10.0 ^10.1 BoostCon (2017-06-13), C++Now 2017: Phil Nash "The Holy Grail!? A Persistent Hash-Array-Mapped Trie for C++", archived from the original on 2021-12-21, retrieved 2018-10-22
↑ Phil, Bagwell (2001). "आदर्श हैश पेड़" (in English). {{cite journal}}: Cite journal requires |journal= (help)
↑ "Are We There Yet?". InfoQ. Retrieved 2018-10-22.
↑ Steindorfer, Michael J.; Vinju, Jurgen J. (2015-10-23). "हैश-ऐरे मैप्ड का अनुकूलन तेजी से और दुबला अपरिवर्तनीय जेवीएम संग्रह के लिए प्रयास करता है". ACM SIGPLAN Notices. 50 (10): 783–800. doi:10.1145/2814270.2814312. ISSN 0362-1340. S2CID 10317844.
↑ "हास्केल भाषा". www.haskell.org. Retrieved 2018-10-22.
↑ "डेटा। सूची". hackage.haskell.org. Retrieved 2018-10-23.
↑ "डेटा.मैप.सख्त". hackage.haskell.org. Retrieved 2018-10-23.
↑ "डेटा.सेट". hackage.haskell.org. Retrieved 2018-10-23.
↑ "Performance/Arrays - HaskellWiki". wiki.haskell.org (in English). Retrieved 2018-10-23.
↑ "क्लोजर - अन्य लिस्प्स के साथ अंतर". clojure.org. Retrieved 2018-10-23.
↑ "क्लोजर - डेटा संरचनाएं". clojure.org. Retrieved 2018-10-23.
↑ "Keynote: The Value of Values". InfoQ. Retrieved 2018-10-23.
↑ "क्लोजर - परमाणु". clojure.org. Retrieved 2018-11-30.
↑ "कोर 1.0.0". package.elm-lang.org. Retrieved 2018-10-23.
↑ "blog/blazing-fast-html-round-two". elm-lang.org. Retrieved 2018-10-23.
↑ "Flux | Application Architecture for Building User Interfaces". facebook.github.io. Retrieved 2018-10-23.
↑ Mora, Osmel (2016-07-18). "रिएक्ट में स्टेट को कैसे हैंडल करें।". React Ecosystem. Retrieved 2018-10-23.
↑ "मुझे पढ़ें - रेडक्स". redux.js.org. Retrieved 2018-10-23.
↑ ^28.0 ^28.1 "अपरिवर्तनीय डेटा - Redux". redux.js.org. Retrieved 2018-10-23.
↑ "अपरिवर्तनीय.जेएस". facebook.github.io. Archived from the original on 2015-08-09. Retrieved 2018-10-23.
↑ "Mori".
↑ "हमेशा". GitHub. 26 October 2021.
↑ Djamboulian, Ara M.; Boizumault, Patrice (1993), The Implementation of Prolog - Patrice Boizumault, ISBN 9780691637709
↑ The Use of Mercury for the Implementation of a Finite Domain Solver - Henk Vandecasteele, Bart Demoen, Joachim Van Der Auwera, 1999
↑ "ऑब्जेक्ट-फंक्शनल प्रोग्रामिंग का सार और स्कैला की व्यावहारिक क्षमता - कोडेंट्रिक एजी ब्लॉग". codecentric AG Blog (in English). 2015-08-31. Retrieved 2018-10-23.
↑ ClojureTV (2013-01-07), Extreme Cleverness: Functional Data Structures in Scala - Daniel Spiewak, retrieved 2018-10-23^{[dead YouTube link]}
↑ "Vladimir Kostyukov - Posts / Slides". kostyukov.net. Retrieved 2018-11-30.
↑ "अपरिवर्तनीय वस्तुएं और कचरा संग्रह". wiki.c2.com. Retrieved 2018-11-30.
↑ "The Last Frontier in Java Performance: Remove the Garbage Collector". InfoQ. Retrieved 2018-11-30.

बाहरी संबंध

[Driscoll-1] 1.0 ^1.1 Driscoll JR, Sarnak N, Sleator DD, Tarjan RE (1986). "Making data structures persistent". Proceedings of the eighteenth annual ACM symposium on Theory of computing - STOC '86. pp. 109–121. CiteSeerX 10.1.1.133.4630. doi:10.1145/12130.12142. ISBN 978-0-89791-193-1. S2CID 364871. {{cite book}}: |journal= ignored (help)

[kaplan2-2] 2.0 ^2.1 Kaplan, Haim (2001). "लगातार डेटा संरचनाएं". Handbook on Data Structures and Applications.

[3] Conchon, Sylvain; Filliâtre, Jean-Christophe (2008), "Semi-persistent Data Structures", Programming Languages and Systems, Lecture Notes in Computer Science, vol. 4960, Springer Berlin Heidelberg, pp. 322–336, doi:10.1007/978-3-540-78739-6_25, ISBN 9783540787389

[4] Tiark, Bagwell, Philip Rompf (2011). RRB-Trees: Efficient Immutable Vectors. OCLC 820379112.{{cite book}}: CS1 maint: multiple names: authors list (link)

[5] Brodal, Gerth Stølting; Makris, Christos; Tsichlas, Kostas (2006), "Purely Functional Worst Case Constant Time Catenable Sorted Lists", Lecture Notes in Computer Science, Springer Berlin Heidelberg, pp. 172–183, CiteSeerX 10.1.1.70.1493, doi:10.1007/11841036_18, ISBN 9783540388753

[sarnak2-6] Neil Sarnak; Robert E. Tarjan (1986). "निरन्तर खोज वृक्षों का प्रयोग करते हुए तलीय बिन्दु स्थान" (PDF). Communications of the ACM. 29 (7): 669–679. doi:10.1145/6138.6151. S2CID 8745316. Archived from the original (PDF) on 2015-10-10. Retrieved 2011-04-06.

[okasaki2-7] Chris Okasaki. "विशुद्ध रूप से कार्यात्मक डेटा संरचनाएं (थीसिस)" (PDF). {{cite journal}}: Cite journal requires |journal= (help)

[8] Liljenzin, Olle (2013). "लगातार लगातार सेट और मानचित्र". arXiv:1301.3388. Bibcode:2013arXiv1301.3388L. {{cite journal}}: Cite journal requires |journal= (help)

[auto-9] 9.0 ^9.1 This example is taken from Okasaki. See the bibliography.

[:1-10] 10.0 ^10.1 BoostCon (2017-06-13), C++Now 2017: Phil Nash "The Holy Grail!? A Persistent Hash-Array-Mapped Trie for C++", archived from the original on 2021-12-21, retrieved 2018-10-22

[11] Phil, Bagwell (2001). "आदर्श हैश पेड़" (in English). {{cite journal}}: Cite journal requires |journal= (help)

[12] "Are We There Yet?". InfoQ. Retrieved 2018-10-22.

[13] Steindorfer, Michael J.; Vinju, Jurgen J. (2015-10-23). "हैश-ऐरे मैप्ड का अनुकूलन तेजी से और दुबला अपरिवर्तनीय जेवीएम संग्रह के लिए प्रयास करता है". ACM SIGPLAN Notices. 50 (10): 783–800. doi:10.1145/2814270.2814312. ISSN 0362-1340. S2CID 10317844.

[14] "हास्केल भाषा". www.haskell.org. Retrieved 2018-10-22.

[15] "डेटा। सूची". hackage.haskell.org. Retrieved 2018-10-23.

[16] "डेटा.मैप.सख्त". hackage.haskell.org. Retrieved 2018-10-23.

[17] "डेटा.सेट". hackage.haskell.org. Retrieved 2018-10-23.

[18] "Performance/Arrays - HaskellWiki". wiki.haskell.org (in English). Retrieved 2018-10-23.

[19] "क्लोजर - अन्य लिस्प्स के साथ अंतर". clojure.org. Retrieved 2018-10-23.

[20] "क्लोजर - डेटा संरचनाएं". clojure.org. Retrieved 2018-10-23.

[21] "Keynote: The Value of Values". InfoQ. Retrieved 2018-10-23.

[22] "क्लोजर - परमाणु". clojure.org. Retrieved 2018-11-30.

[23] "कोर 1.0.0". package.elm-lang.org. Retrieved 2018-10-23.

[24] "blog/blazing-fast-html-round-two". elm-lang.org. Retrieved 2018-10-23.

[25] "Flux | Application Architecture for Building User Interfaces". facebook.github.io. Retrieved 2018-10-23.

[26] Mora, Osmel (2016-07-18). "रिएक्ट में स्टेट को कैसे हैंडल करें।". React Ecosystem. Retrieved 2018-10-23.

[27] "मुझे पढ़ें - रेडक्स". redux.js.org. Retrieved 2018-10-23.

[:0-28] 28.0 ^28.1 "अपरिवर्तनीय डेटा - Redux". redux.js.org. Retrieved 2018-10-23.

[29] "अपरिवर्तनीय.जेएस". facebook.github.io. Archived from the original on 2015-08-09. Retrieved 2018-10-23.

[30] "Mori".

[31] "हमेशा". GitHub. 26 October 2021.

[32] Djamboulian, Ara M.; Boizumault, Patrice (1993), The Implementation of Prolog - Patrice Boizumault, ISBN 9780691637709

[33] The Use of Mercury for the Implementation of a Finite Domain Solver - Henk Vandecasteele, Bart Demoen, Joachim Van Der Auwera, 1999

[34] "ऑब्जेक्ट-फंक्शनल प्रोग्रामिंग का सार और स्कैला की व्यावहारिक क्षमता - कोडेंट्रिक एजी ब्लॉग". codecentric AG Blog (in English). 2015-08-31. Retrieved 2018-10-23.

[35] ClojureTV (2013-01-07), Extreme Cleverness: Functional Data Structures in Scala - Daniel Spiewak, retrieved 2018-10-23^{[dead YouTube link]}

[36] "Vladimir Kostyukov - Posts / Slides". kostyukov.net. Retrieved 2018-11-30.

[37] "अपरिवर्तनीय वस्तुएं और कचरा संग्रह". wiki.c2.com. Retrieved 2018-11-30.

[38] "The Last Frontier in Java Performance: Remove the Garbage Collector". InfoQ. Retrieved 2018-11-30.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

[21]

[22]

[23]

[24]

[25]

[26]

[27]

[28]

[29]

[30]

[31]

[32]

[33]

[34]

[35]

[36]

[37]

[38]

Anonymous

Search