आपका पहली पसंद प्रत्याशित पहुँच पैटर्न पर निर्भर होना चाहिए, और आप कितना डेटा भंडारण होने की संभावना कर रहे हैं: ...
- वहाँ कभी नहीं अधिक डेटा है कि अगर (30 कम से कम एन, कहते हैं), एक unsorted सरणी ठीक हो जाएगा;
- यदि आप लगभग कभी भी जोड़ना, हटाना या अपडेट नहीं करना चाहते हैं, तो एक सॉर्टेड सरणी ठीक होगी;
- यदि एन कम है, कहें, 1 मिलियन, और आप केवल शीर्ष तत्व (पहले स्थान पर या आखिरी स्थान पर) के लिए खोज रहे हैं, तो ढेर (विशेष रूप से यदि आप अक्सर चुने गए तत्वों को अपडेट कर रहे हैं) यादृच्छिक रूप से, जैसा कि आप में एक कैश के लिए एक एलआरयू (कम से कम हाल ही में उपयोग की गई) कतार में करते हैं, कहते हैं, क्योंकि औसतन अद्यतन ओ (लॉग) (एन) के बजाय ओ (1) है)
- यदि एन से कम है, तो कहें, 1 मिलियन, और आप सुनिश्चित नहीं हैं कि आप खोज रहे हैं, एक संतुलित पेड़ (कहें, लाल-काला या एवीएल) ठीक होगा;
- यदि एन बड़ा है (1 मिलियन और ऊपर, कहें), तो आप शायद बी-पेड़ या एक ट्राई के साथ बेहतर हो जाएं (संतुलित द्विआधारी पेड़ का प्रदर्शन "एक चट्टान से गिरने" के बाद होता है पर्याप्त: मेमोरी एक्सेस बहुत बिखरे हुए होते हैं, और कैश मिस वास्तव में चोट लगने लगते हैं)
...लेकिन मैं विकल्प को जितना संभव हो उतना खोलने की सलाह देता हूं, ताकि आप कम से कम एक विकल्प को बेंचमार्क कर सकें और यदि यह बेहतर प्रदर्शन करता है तो इसे स्विच कर सकते हैं।
पिछले बीस वर्षों में, मैंने केवल दो अनुप्रयोगों पर काम किया है जहां एक ही चीज के लिए ढेर सबसे अच्छा विकल्प था (एक बार एलआरयू के लिए, और एक बार एक बुरा संचालन-अनुसंधान अनुप्रयोग में, यादृच्छिक रूप से परेशान के-आयामी के लिए additivity बहाल करना हाइपरक्यूब, जहां हाइपरक्यूब में अधिकांश कोशिकाएं अलग-अलग ढेर में दिखाई देती हैं और स्मृति प्रीमियम पर होती है)। हालांकि, उन दो मौकों पर, उन्होंने विकल्पों की तुलना में काफी बेहतर प्रदर्शन किया: शाब्दिक रूप से संतुलित पेड़ों या बी-पेड़ों की तुलना में दर्जनों बार तेज।
पिछले पैराग्राफ में उल्लिखित हाइपरक्यूब समस्या के लिए, मेरी टीम के नेतृत्व वाले विचार लाल-काले पेड़ ढेर से बेहतर प्रदर्शन करेंगे, लेकिन बेंचमार्किंग से पता चला है कि लाल-काले पेड़ धीमे थे (जैसा कि मुझे याद है, वे थे लगभग बीस गुना धीमी), और हालांकि बी-पेड़ काफी तेजी से थे, हालांकि ढेर उन्हें आराम से हराते थे।
ढेर की महत्वपूर्ण विशेषता, ऊपर वर्णित दोनों मामलों में, न्यूनतम मूल्य की ओ (1) लुकअप नहीं थी, बल्कि यादृच्छिक रूप से चुने गए तत्व के लिए ओ (1) औसत अद्यतन समय ।
-जेम्स Barbetti (ठीक है, मैंने सोचा कि मैं था। लेकिन कैप्चा मुझे बता रहता है मैं मानव नहीं कर रहा हूँ) यदि आप एक खोज या तलाशी अभियान एक बहुत तो एक संतुलित द्विआधारी पेड़ पसंद किया जाता है का उपयोग करते हैं
यदि आपने सरणी के बजाय नोड संरचना का उपयोग करके एक ढेर लागू किया है, तो मैं विश्वास करूँगा कि आप क्या कह रहे हैं :)। –
एक हीप लागू करने के लिए एक बहुत ही सरल डेटा संरचना है ... –