कोई शब्दकोश क्यों नहीं है। TamExcess()?

Question

.NET में, Dictionary<TKey, TValue> के लिए एक कन्स्ट्रक्टर है जो एक पैरामीटर लेता है, int capacity। यह List<T>, Queue<T>, और Stack<T> जैसे कई अन्य संग्रहों के समान है; इसके अलावा, the MSDN documentation के अनुसार:

शब्दकोश की क्षमता तत्वों की संख्या है जो आकार बदलने से पहले शब्दकोश में जोड़ा जा सकता है। जैसे-जैसे तत्वों को एक शब्दकोश में जोड़ा जाता है, आंतरिक सरणी को पुन: आवंटित करके क्षमता स्वचालित रूप से बढ़ जाती है।

यह मेरे लिए काफी List<T>, आदि इन संग्रहों के बाद से जैसे अन्य संग्रह के साथ के रूप में ही लगता है की सुविधा स्वत: आकार व्यवहार जब आवश्यक है और इसलिए आवश्यक की तुलना में अधिक क्षमता होने की संभावना है, उनमें से ज्यादातर एक सुविधा TrimExcess विधि। यह आसान है अगर कहें, आप एक समय में संग्रह में अज्ञात संख्या में आइटम जोड़ रहे हैं, और इसके बाद आप कोई अतिरिक्त आइटम नहीं जोड़ेंगे।

Dictionary<TKey, TValue> क्यों TrimExcess विधि नहीं है?

(अस्वीकरण: मैं के साथ काफी परिचित हूँ प्रतिक्रिया "सुविधाएं डिफ़ॉल्ट रूप से मौजूद नहीं है", मुझे लगता है कि मैं ज्यादातर कर रहा हूँ बस वहाँ एक विशेष कारण है कि एक Dictionary के लिए TrimExcess मतलब नहीं है, या कारण है कि यह है कि अगर सोच List जैसे सरल संग्रहों के मुकाबले लागू करना काफी कठिन होगा।)

Answer 1

प्रति एमएसडीएन शब्दकोश एक हैश तालिका के रूप में लागू किया गया है। यदि आप अतिरिक्त छंटनी करते हैं तो आपको एक एल्गोरिदम के साथ आना होगा जो अभी भी ओ (1) लुकअप टाइम्स के करीब प्रदान करेगा जो प्रभावी रूप से यादृच्छिक रूप से क्रमबद्ध सूची में होगा।

Answer 2

मुझे लगता है कि इस मामले में क्षमता तर्क हैशिंग फ़ंक्शन के साथ-साथ बाल्टी की संख्या को परिभाषित करने में मदद करता है; डेटा के एक दुर्लभ संग्रह को आकार देने/ट्रिम करने के लिए शेष संग्रहित वस्तुओं के पुनर्मूल्यांकन की आवश्यकता होगी।

Answer 3

यह आंशिक रूप से अनुमान है: एक शब्दकोश हैश तालिका के रूप में "आदेश दिया गया" है। आरक्षित क्षमता, बस आपके शब्दकोश के शीर्ष पर मुफ्त मेमोरी पते का एक गुच्छा नहीं है। इसके बजाय, इसमें पूरे शब्दकोश में खाली कमरा होता है। यह बहुत ही कुशल जोड़ने/स्थानांतरित/निकालने आदि के लिए किया जाता है। यदि आपके पास शब्दकोश के लिए TrimExcess विधि थी, तो पूरे शब्दकोश को तत्वों के बीच किसी भी अंतर के बिना सब कुछ एक नए स्थान पर कॉपी करना होगा।

दरअसल: अंतर को अन्यथा रहना चाहिए, अन्यथा हैश तालिका का लाभ शून्य हो जाता है, ट्रिमिंग (TrimExcess), लागू होने पर, केवल आंतरिक ValueCollection को ट्रिम करना चाहिए।

अद्यतन: विस्तार किया है और मेरी बीमार चुना शब्द बदल
अद्यतन:the BCL team says TrimExcess for Dictionaries "could be useful"।
अद्यतन: सुविधा अनुरोध के रूप में हल किया गया को ठीक नहीं करेगा: "दुर्भाग्यवश, हम .NET की अगली रिलीज के लिए इसे प्राप्त नहीं कर पाएंगे, इसलिए मैं इसे हल नहीं करूँगा । "

Answer 4

असल में मैं वह था जिसने माइक्रोसॉफ्ट से TrimExcess को लागू करने के लिए कहा था। मैंने पहले से ही एक से अधिक आलेख प्रस्तुत किए हैं जो शब्दकोशों से संबंधित हैं और सभी मामलों में मैंने TrimExcess लागू किया है।वास्तव में, बाल्टी के आकार को बढ़ाने या घटाने के दौरान जब बाल्टी बहुत छोटी होती है तो आकार का उपयोग किया जा सकता है। http://www.codeproject.com/Articles/761040/A-NET-like-Dictionary-in-Cplusplus

एक और कार्यान्वयन (.NET) इस लेख में पाया जा सकता है:

आज मैं सिर्फ एक और लेख प्रकाशित किया है, यह एक सी ++ एक शब्दकोश के कार्यान्वयन, जो TrimExcess का समर्थन करता है http://www.codeproject.com/Articles/548406/Dictionary-plus-Locking-versus-ConcurrentDictionar