इस सरणी डेटा संरचना का नाम क्या है?

Question

sqrt(n) पॉइंटर्स की एक सरणी के रूप में n आकार की एक सरणी लागू करें।

i पर कोई आइटम डालने के लिए, i/sqrt(n) पर पॉइंटर पर जाएं। यदि वह सूचक null है, तो इसे sqrt(n) आकार की एक नई सरणी में असाइन करें। स्थिति i mod sqrt(n) पर अपने आइटम को नई सरणी में डालें।

लाभ सरल है: यह आपको एक बड़ी सरणी बनाने की अनुमति देता है जो प्रारंभ में केवल O(sqrt(n)) स्थान लेता है। आप निरंतर समय में किसी भी तत्व तक पहुंच सकते हैं, और यह आपको सभी n पदों के लिए स्थान आवंटित किए बिना सरणी के भाग भरने की अनुमति देता है।

यह पहले से ही हैश-टेबल के लिए उपयोग किया जा सकता है, और मेरे पास एक और अनुप्रयोग है। मेरा सवाल है: क्या इसके लिए कोई नाम है? कोई भी सामान्य कार्यान्वयन मैं उपयोग कर सकता हूँ?

Answer 1

यह डेटा संरचना hashed array tree (HAT) डेटा संरचना से निकटता से संबंधित है।एक हैश किए गए सरणी पेड़ को ऊपर वर्णित की तरह संरचित किया गया है - आपके पास √ n आकार का शीर्ष-स्तर सरणी है, जहां प्रत्येक प्रविष्टि √ n तत्वों के साथ एक सरणी के लिए सूचक है। यह सम्मिलन और लुकअप को काफी तेज बनाता है और केवल ओ (√ एन) पारंपरिक गतिशील सरणी के ओ (एन) मेमोरी ओवरहेड की तुलना में मेमोरी ओवरहेड होता है।

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

आशा है कि इससे मदद मिलती है!

Answer 2

ठीक है, मैं उस पंक्ति वैक्टर के साथ एक वर्ग मैट्रिक्स को कॉल करूंगा। यदि पूरी तरह से आबादी नहीं है, तो यह स्पैस पंक्ति वैक्टर के साथ वर्ग मैट्रिक्स है। ^1.

यहां काम पर दो अनुकूलन हैं। पहला स्पैस मेमोरी आवंटन है, और दूसरा पंक्ति सबस्क्रिप्ट गणना के strength reduction है। यह ऑप्टिमाइज़ेशन शायद सुपरस्केकर सीपीयू के निष्पादन निर्देशों के बाहर बहुत महत्वपूर्ण नहीं है, और उस उम्र में जहां संकलक नियमित रूप से वैश्विक प्रवाह अनुकूलन करते हैं।

लेकिन यह पंक्ति आकार से गुणा करने के बजाय पंक्ति सूचकांक के माध्यम से पंक्ति सूचकांक की अनुमति देता है।

---

^{1. हालांकि, संख्यात्मक विश्लेषण में, एक विरल मैट्रिक्स एक ज्यादातर शून्य है कि, और इसलिए एक विरल डेटा संरचना औपचारिक रूप से एक ही परिभाषा है। इस मामले में, यह आंशिक डेटा संरचना का अधिक है, लेकिन मेरे ज्ञान के लिए, इन चीजों के लिए स्वीकार्य शर्तें नहीं हैं।}

Answer 3

यह बाल्टी की एक सरणी है।

जावा का जल्दबाजी कार्यान्वयन ऐसा "बाल्टी आधारित हैशटेबल" है।
यहां buckets

के लिए एक ग्राफिक यहां क्वाड पेड़ जैसी अन्य संरचनाएं हैं, जो भी ऐसी बाल्टी का उपयोग करती हैं।

आपके मामले में आपके पास sqrt (n) बाल्टी है।

Answer 4

मैं इसे एक खंडित सरणी कहता हूं। पॉइंटर्स को हैंडल मैप करते समय मैं इनका उपयोग करता हूं।

Answer 5

यह Van Emde Boas Tree के पहले स्तर के समान ही है।

एक वैन एम्डे बोस ट्री पहले स्तर पर sqrt (n) पॉइंटर्स स्टोर करता है, लेकिन इस प्रश्न में केवल एक साधारण सरणी के बजाय निचले स्तर पर अतिरिक्त पेड़ हैं।

Answer 6

यह प्रति डेटा संरचना नहीं है। ऐसा लगता है कि इस तकनीक का उपयोग अन्य संग्रह प्रकार डेटा संरचनाओं में किया जा सकता है।

संपादित करें: यह निश्चित रूप से डेटा संग्रह या व्यवस्थित करने के लिए एक तंत्र है, लेकिन मैंने हमेशा भंडारण/पुनर्प्राप्ति (पढ़ने/लिखने) तंत्र के साथ डेटा संरचना को जोड़ा है।