लोड किए गए एप्लिकेशन विकसित करते समय शब्दकोश के साथ काम करने के कुछ पहलू

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

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

इस लेख में हम इनमें से कुछ मुद्दों से निपटने की कोशिश करेंगे।

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

वास्तुकला की एक महत्वपूर्ण विशेषता यह है कि एक ही आकार के दो सरणियों का उपयोग करके डेटा भंडारण का आयोजन किया जाता है:

    int[] _buckets = new int[size];
    Entry[] _entries = new Entry[size];

ये सरणियाँ उनके त्वरित उपयोग के लिए उपयोगी डेटा और सेवा तत्वों को संग्रहीत करती हैं। अंतराल को एक मार्जिन के साथ बनाया जाता है, अर्थात, वे लगभग हमेशा खाली होते हैं।

एंट्री हेल्पर इकाई जो प्रत्येक कुंजी-मूल्य जोड़ी को लपेटती है, एक महत्वपूर्ण प्रकार है:

    private struct Entry
    {
        public uint hashCode;
        public int next;
        public TKey key;
        public TValue value;
    }

, , , _entries. , ConcurrentDictionary, . ( 64 16 8 ) , .

_entries Dictionary 85000 LOH (, , 64 3372 , 1932). , , .

Microsoft _entries , Entry? LOH (, , ). , , .

, . 12 (4 _buckets 4 hashCode next Entry). , , , 12 . ? .

Dictionary . . Dictionary<int, int> ( ). , – ( ). 500 . 13 . 500 .

, . , , , .

, _buckets _entries , «», . LOH, .
, 746 3 .

, Dictionary . , , , .NET Core TrimExcess, .

:

• , EnsureCapacity. .
• , 400 10. (80 ). new Dictionary<int, int>(10001000), 190. , , .
• , Dictionary EnsureCapacity(capacity*), . , _buckets _entries . . , EnsureCapacity(0).
• , ( ) , , Dictionary: . , . , ( ).
• TrimExcess. LOH . .

Dictionary. , Dictionary<Key, Value>, :

    public class Key
    {
        public int Item { get; set; }
        public Key(int item)
        {
            Item = item;
        }
        public override bool Equals(object obj)
        {
            return Item.Equals(obj);
        }
        public override int GetHashCode()
        {
            return Item.GetHashCode();
        }
    }
    public class Value
    {
        public int Item { get; set; }
        public Value(int item)
        {
            Item = item;
        }
    }

.

?

:

• 64 (8 ) (8 ).
• , , 8 «» .
• Item Key Value 8 , , Item 4 .

20 76 .

:

• ( ), .
• , . .

, . ? , ( 10-20-30 ) . ?

. , Dictionary<int, int>(int count) :

    struct Entry<TValue>
    {
        public int[] Keys;
        public TValue[] Values;
        public Entry(int count)
        {
            Keys = new int[count];
            Values = new TValue[count];
        }
        public bool TryGetValue(int key, out TValue value)
        {
            for (int j = 0; j < Keys.Length; ++j)
            {
                if (Keys[j] == key)
                {
                    value = Values[j];
                    return true;
                }
            }
            value = default(TValue);
            return false;
        }
    }

count – -, .
.

, 18 count=10 134 count=190 ( 50 . ). ( – 29 ), ( 150) , (, ).

, (, , Entry , ).
, (callvirt GetHashCode Equals). – . , , , (generic) . .

SortedList<int, int>.
.

, .

: , . .

प्रस्तुत सभी उदाहरणों में, यह ध्यान में रखा जाना चाहिए कि परीक्षण कॉन्फ़िगरेशन में छोटे डेटा का उपयोग किया जाता है, इसलिए, सेवा की जानकारी के लिए ओवरहेड अपेक्षाकृत अधिक है।
टेस्ट प्रोजेक्ट यहां देखे जा सकते हैं ।