بعض جوانب العمل مع القاموس عند تطوير التطبيقات المحملة

لكتابة هذه المذكرة القصيرة ، دفعتني العديد من المقابلات الأخيرة لمنصب المطور الرئيسي في شركتنا. بعض المتقدمين ، كما اتضح ، ليسوا على دراية جيدة بأي نوع من الآلية ، هذا القاموس ، وكيف يجب استخدامه. لقد صادفت رأيًا راديكاليًا للغاية: يقولون أن القاموس يعمل ببطء شديد ، وبسبب حقيقة أنه عندما يتم وضعه على الفور في كومة من الأشياء الكبيرة (LOH) ، لا يمكن استخدامه في التعليمات البرمجية ومن الأفضل تطبيق الاستعلامات على المجموعات العادية باستخدام مرشحات LINQ !

بالطبع ، هذه ليست بيانات صحيحة بالكامل. غالبًا ما يكون هناك حاجة إلى القاموس كآلية في بناء كود عالي التحميل وتنفيذ منطق الأعمال. يجب على المطور أن يتخيل كيف يتم تنظيم القاموس ، وكيف يعمل مع الذاكرة ، ومدى تكلفته ، وعدد "الآثار" التي سيتركها في الأجيال و LOH ، مما يتسبب في حمل غير ضروري على جامع القمامة ؛ كيفية تهيئتها بشكل أفضل ، وفي هذه الحالات ، من الأفضل استخدام مجموعة من أزواج القيمة الرئيسية بدلاً من ذلك ، وفيها مجموعة مصنفة ، إلخ.

في هذه المقالة سنحاول التعامل مع بعض هذه القضايا.

يعتمد تطبيق القاموس من Microsoft ، كما يعلم الجميع ، على آلية جدول التجزئة. هذا يعطي في بعض السيناريوهات ما لا يمكن تحقيقه للخوارزميات الأخرى التعقيد الثابت المثالي O (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>.
.

, .

: , . .

في جميع الأمثلة المقدمة ، يجب أن يوضع في الاعتبار أنه يتم استخدام البيانات الصغيرة في تكوين الاختبار ؛ وبالتالي ، فإن النفقات العامة لمعلومات الخدمة مرتفعة نسبيًا.
يمكن العثور على مشاريع الاختبار هنا .