कुछ कम ज्ञात डेटा संरचनाएं और एल्गोरिदम क्या हैं जिन्हें किसी को पता होना चाहिए?

Question

हाल ही में मैं SkipList डेटा संरचना में आया था। यह वास्तव में मुझे अन्यथा मुश्किल से सुलझाने की समस्या को हल करने में मदद करता है। मैं संतुलित बाइनरी पेड़ का उपयोग करके इसे हल करने के लिए संघर्ष कर रहा था लेकिन यह बहुत जटिल हो गया क्योंकि पेड़ को हमेशा संतुलित होना चाहिए और मैं न केवल एक विशेष मूल्य के अस्तित्व को जानना चाहता था बल्कि एक निश्चित सीमा में मूल्यों को जानना चाहता था। SkipList ने मुझे उस समस्या को प्रभावी ढंग से हल करने में मदद की।

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

Answer 1

आपने ग्राफ का उल्लेख नहीं किया जो बहुत शक्तिशाली हैं और यदि आप उनके बारे में नहीं जानते हैं तो आपको निश्चित रूप से उन पर पढ़ना चाहिए। डिजस्ट्रा के एल्गोरिदम और ए * खोज एल्गोरिदम के साथ-साथ सामान्य गहराई पहली खोज और ब्रेडथ फर्स्ट सर्च देखें।

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

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

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

Answer 2

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

मुझे लगता है कि इनमें से कोई भी विशेष रूप से "हालिया" नहीं है - वे सभी दशकों से अब तक ज्ञात हैं। इनमें से अधिकतर सामान्य संरचनाएं काफी समय से जानी जाती हैं। हाल ही में खोजे गए अधिक विशिष्ट विषय क्षेत्रों से संबंधित हैं।