मौलिक डेटा संरचनाएँ
मौलिक डेटा संरचनाएँ डेटा को संग्रहीत करने और एक्सेस करने के संगठित तरीके हैं — ऐरे, लिंक्ड लिस्ट, हैश टेबल, ट्री, हीप और उनके संबंधी — जो उन पर निर्मित ऑपरेशनों की दक्षता निर्धारित करते हैं।
Definition
एक डेटा संरचना डेटा को व्यवस्थित और संग्रहीत करने का एक तरीका है ताकि उसके अमूर्त डेटा प्रकार द्वारा परिभाषित संचालन कुशलता से किए जा सकें; मौलिक डेटा संरचनाएं सामान्य-उद्देश्य वाली संरचनाओं का एक छोटा समूह हैं जिनसे अधिकांश अन्य संरचनाएं निर्मित होती हैं।
Scope
यह क्षेत्र अमूर्त डेटा प्रकारों (सूचियाँ, शब्दकोश, प्राथमिकता कतारें, सेट) और उन्हें लागू करने वाली ठोस संरचनाओं को कवर करता है, साथ ही सबसे खराब स्थिति और परिशोधित विश्लेषण के तहत उनके मुख्य ऑपरेशनों (सम्मिलित करना, हटाना, खोजना, अद्यतन करना) की लागत को भी। यह बताता है कि संरचना का चुनाव एल्गोरिथम के प्रदर्शन को कैसे आकार देता है और इन संरचनाओं पर निर्भर डिजाइन प्रतिमानों और ग्राफ और स्ट्रिंग एल्गोरिदम से कैसे जुड़ता है। इसमें डेटाबेस और फाइल-सिस्टम स्टोरेज संरचनाएं शामिल नहीं हैं जिन्हें अन्य उपक्षेत्रों में संभाला जाता है।
Sub-topics
Core questions
- किसी एप्लिकेशन को किस अमूर्त डेटा प्रकार की आवश्यकता है, और कौन सी ठोस संरचना इसे सबसे अच्छी तरह से लागू करती है?
- किसी दी गई संरचना पर प्रत्येक ऑपरेशन की सबसे खराब स्थिति और परिशोधित लागत क्या है?
- संरचनाएँ समय के लिए मेमोरी, या अद्यतन गति के लिए पढ़ने की गति का व्यापार कैसे करती हैं?
- एक अपरिवर्तनीय (क्रमबद्धता, संतुलन, हीप गुण) को बनाए रखना ऑपरेशन लागतों को कैसे सीमित करता है?
- एक स्पर्शोन्मुख रूप से तेज़ लेकिन अधिक जटिल संरचना की तुलना में एक सरल संरचना कब बेहतर होती है?
Key concepts
- अमूर्त डेटा प्रकार
- ऐरे और लिंक्ड लिस्ट
- स्टैक और कतारें
- हैश टेबल
- बाइनरी सर्च ट्री
- संतुलित ट्री
- हीप और प्राथमिकता कतारें
- परिशोधित विश्लेषण
- समय-स्थान व्यापार-बंद
Key theories
- अमूर्त डेटा प्रकार बनाम कार्यान्वयन
- एक अमूर्त डेटा प्रकार प्रतिनिधित्व से स्वतंत्र संचालन और उनके अर्थशास्त्र को निर्दिष्ट करता है; कई ठोस डेटा संरचनाएं विभिन्न प्रदर्शन प्रोफाइल के साथ एक ही ADT को लागू कर सकती हैं, जिससे डिजाइनर शुद्धता और लागत के बारे में अलग-अलग तर्क कर सकते हैं।
- परिशोधित विश्लेषण
- कुछ संरचनाओं (डायनामिक ऐरे, स्प्ले ट्री) में कभी-कभी महंगे ऑपरेशन होते हैं, लेकिन एक अनुक्रम पर औसतन सस्ते ऑपरेशन होते हैं; परिशोधित विश्लेषण (समग्र, लेखांकन, संभावित विधियाँ) इस औसत लागत को कठोरता से सीमित करता है।
Clinical relevance
मौलिक डेटा संरचनाएँ अनिवार्य रूप से सभी सॉफ्टवेयर के बिल्डिंग ब्लॉक हैं: हैश टेबल शब्दकोशों और डेटाबेस इंडेक्स को आधार प्रदान करती हैं, संतुलित ट्री और बी-ट्री फाइल सिस्टम और डेटाबेस को व्यवस्थित करते हैं, प्राथमिकता कतारें शेड्यूलर और इवेंट सिमुलेशन को संचालित करती हैं, और सही संरचना का चुनाव अक्सर यह निर्धारित करता है कि कोई सिस्टम स्केल करता है या नहीं।
History
फाउंडेशनल डेटा संरचनाओं को नूथ की 'द आर्ट ऑफ कंप्यूटर प्रोग्रामिंग' में 1968 से सूचीबद्ध किया गया था। सेल्फ-बैलेंसिंग ट्री (एवीएल ट्री, 1962; रेड-ब्लैक ट्री और बी-ट्री 1970 के दशक में) और फिबोनाची हीप्स और स्प्ले ट्री (1980 के दशक में, मुख्य रूप से टार्जन और सहयोगियों के कारण) जैसी उन्नत संरचनाओं ने इस क्षेत्र का विस्तार किया, जबकि परिशोधित विश्लेषण ने उनके प्रदर्शन का कठोर विवरण दिया।
Key figures
- Donald Knuth
- Robert Sedgewick
- Robert Tarjan
- Rudolf Bayer
Related topics
Seminal works
- knuth1997vol1
- cormen2009
- sedgewick2011
Frequently asked questions
- मैं हैश टेबल और संतुलित सर्च ट्री के बीच कैसे चुनाव करूँ?
- हैश टेबल अपेक्षित O(1) लुकअप और इंसर्शन देते हैं लेकिन कोई क्रम नहीं, जबकि संतुलित सर्च ट्री O(log n) ऑपरेशन देते हैं और कुंजियों को क्रमबद्ध रखते हैं, रेंज क्वेरी और क्रमबद्ध ट्रैवर्सल का समर्थन करते हैं। शुद्ध कुंजी लुकअप के लिए हैशिंग चुनें और जब ऑर्डरिंग या रेंज ऑपरेशन मायने रखते हों तो ट्री चुनें।
- डेटा संरचना के लिए परिशोधित लागत का क्या अर्थ है?
- परिशोधित लागत ऑपरेशनों के सबसे खराब स्थिति वाले अनुक्रम पर प्रति ऑपरेशन औसत लागत है। उदाहरण के लिए, एक डायनामिक ऐरे, कभी-कभी आकार बदलने के लिए O(n) का भुगतान करता है, लेकिन प्रति अपेंड पर औसतन O(1) होता है क्योंकि सस्ते अपेंड की तुलना में आकार बदलना दुर्लभ होता है।