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

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

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

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

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

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

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

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

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

फैट नोड

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

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

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

पाथ कॉपीइंग

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

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

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

एक संयोजन

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

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

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

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

इस कलन विधि के साथ, किसी भी समय टी को देखते हुए, समय टी के साथ आंकड़ा संरचना में अधिकतम एक संशोधन बॉक्स मौजूद होता है। इस प्रकार, समय 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$ आउटगोइंग किनारों का जो पॉइंटर्स द्वारा दर्शाए जाते हैं। प्रत्येक वर्टेक्स में आंकड़ा का प्रतिनिधित्व करने वाला एक लेबल होता है। हम मानते हैं कि शीर्ष की एक परिबद्ध संख्या होती है {{mvar|d}इसमें जाने वाले किनारों के } जिन्हें हम inedges के रूप में परिभाषित करते हैं ( $v$ ). हम निम्नलिखित विभिन्न परिचालनों को चालू करने की अनुमति देते हैं $G$ .

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

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

क्रिएट-नोड

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

चेंज-एज

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

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

बदलें-लेबल

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

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

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

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

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

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

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

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

अगला तत्व खोज या बिंदु स्थान

उपयोगी अनुप्रयोगों में से एक जिसे दृढ़ता का उपयोग करके कुशलता से हल किया जा सकता है, वह है नेक्स्ट एलिमेंट सर्च। मान लीजिए कि हैं $n$ गैर-प्रतिच्छेदी रेखा खंड जो एक दूसरे को पार नहीं करते हैं जो एक्स-अक्ष के समानांतर हैं। हम एक आंकड़ा संरचना बनाना चाहते हैं जो एक बिंदु को परिप्रश्न कर सके $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] एक स्थायी संस्करण बनाने के लिए आसानी से अनुकूलित किया जा सकता है। कुछ अन्य लोगों को थोड़ा और प्रयास करने की आवश्यकता है, उदाहरण के लिए: कतार (आंकड़ा संरचना), डबल-एंडेड कतार, और दस मिनट सहित एक्सटेंशन (जिसमें एक अतिरिक्त ओ (1) ऑपरेशन मिनट न्यूनतम तत्व लौटाता है) और रैंडम अभिगम और (जिसमें है सब-लीनियर के साथ रैंडम अभिगम का एक अतिरिक्त ऑपरेशन, सबसे अधिक बार लॉगरिदमिक, जटिलता)।

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

लिंक की गई सूचियां

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

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

xs = [0, 1, 2]
वाईएस = [3, 4, 5]

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

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

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

zs = xs ++ ys

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

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

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

पेड़

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

उदाहरण के लिए, आंकड़ा का सेट

xs = [ए, बी, सी, डी, एफ, जी, एच]

निम्नलिखित बाइनरी सर्च ट्री द्वारा दर्शाया जा सकता है:

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

 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 में फिल बैगवेल द्वारा आइडियल हैश ट्रीज़ नामक पेपर में वर्णित किया गया था। इस पेपर ने एक म्यूटेबल हैश तालिका प्रस्तुत किया है, जहां इंसर्ट, सर्च और डिलीट का समय छोटा और स्थिर है, कुंजी सेट आकार से स्वतंत्र है, ऑपरेशन ओ (1) हैं। डालने, खोजने और हटाने के संचालन के लिए सबसे खराब समय की गारंटी दी जा सकती है और सफल खोजों की तुलना में लागत कम होती है।^[11] इस आंकड़ा संरचना को तब अमीर हिक्की द्वारा क्लोजर प्रोग्रामिंग भाषा में उपयोग के लिए पूरी तरह से स्थिर होने के लिए संशोधित किया गया था।^[12] वैचारिक रूप से, हैश ऐरे मैप्ड किसी भी सामान्य ट्री (आंकड़ा संरचना) के समान काम करने की कोशिश करता है, जिसमें वे नोड्स को श्रेणीबद्ध रूप से संग्रहीत करते हैं और किसी विशेष तत्व के नीचे पथ का अनुसरण करके उन्हें पुनः प्राप्त करते हैं। मुख्य अंतर यह है कि हैश ऐरे मैप्ड ट्राइज़ अपनी लुकअप कुंजी को एक (आमतौर पर 32 या 64 बिट) पूर्णांक में बदलने के लिए पहले हैश फंकशन का उपयोग करते हैं। पेड़ के नीचे का रास्ता तब पेड़ के प्रत्येक स्तर पर विरल मैट्रिक्स में अनुक्रमित करने के लिए उस पूर्णांक के बाइनरी प्रतिनिधित्व के स्लाइस का उपयोग करके निर्धारित किया जाता है। पेड़ के पत्ते के नोड्स हैश टेबल बनाने के लिए उपयोग की जाने वाली बाल्टी के समान व्यवहार करते हैं और हैश टकराव के आधार पर कई उम्मीदवार हो सकते हैं या नहीं भी हो सकते हैं।^[10]

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

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

हास्केल

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

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

क्लोजर

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

एल्म

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

जावा

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

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

लोकप्रिय जावास्क्रिप्ट फ्रंटएंड फ्रेमवर्क रिएक्ट (जावास्क्रिप्ट लाइब्रेरी) का उपयोग अक्सर राज्य प्रबंधन प्रणाली के साथ किया जाता है जो फ्लक्स आर्किटेक्चर को लागू करता है,^[25]^[26] जिसका एक लोकप्रिय कार्यान्वयन JavaScript लाइब्रेरी Redux (जावास्क्रिप्ट लाइब्रेरी) है। Redux लाइब्रेरी एल्म प्रोग्रामिंग भाषा में उपयोग किए जाने वाले राज्य प्रबंधन पैटर्न से प्रेरित है, जिसका अर्थ है कि यह अनिवार्य है कि उपयोगकर्ता सभी आंकड़ा को लगातार मानते हैं।^[27] नतीजतन, Redux परियोजना अनुशंसा करती है कि कुछ मामलों में उपयोगकर्ता लागू और कुशल लगातार आंकड़ा संरचनाओं के लिए पुस्तकालयों का उपयोग करते हैं। नियमित जावास्क्रिप्ट वस्तुओं की तुलना करने या प्रतिलिपि बनाने की तुलना में यह कथित तौर पर अधिक प्रदर्शन की अनुमति देता है।^[28] लगातार आंकड़ा संरचनाओं की एक ऐसी लाइब्रेरी Immutable.js उपलब्ध कराई गई आंकड़ा संरचनाओं पर आधारित है और क्लोजर और स्काला द्वारा लोकप्रिय है।^[29] Redux के प्रलेखन द्वारा इसका उल्लेख उन संभावित पुस्तकालयों में से एक के रूप में किया गया है जो लागू अपरिवर्तनीयता प्रदान कर सकते हैं।^[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