هل يجب تهيئة القاموس العام .NET بقدرة تساوي عدد العناصر التي سيحتوي عليها؟

Question

إذا كان لدي ، على سبيل المثال ، 100 عنصر سيتم تخزينه في القاموس ، هل يجب أن أقوم بتهيئته بذلك؟

var myDictionary = new Dictionary<Key, Value>(100);

ما أفهمه هو أن قاموس .NET داخليًا يقيم نفسه داخليًا عندما يصل إلى تحميل معين ، وأن عتبة التحميل يتم تعريفها على أنها نسبة للسعة.

قد يشير ذلك إلى أنه إذا تمت إضافة 100 عنصر إلى القاموس أعلاه ، فسيتم تغيير حجمها عند إضافة أحد العناصر. إن تغيير حجم القاموس هو شيء أود تجنبه لأنه يحتوي على نجاح في الأداء وهو مضيء للذاكرة.

احتمال تصادم التجزئة يتناسب مع التحميل في القاموس. لذلك ، حتى لو لم يكن القاموس تغيير حجمه (ويستخدم جميع فتحاته) ، فيجب أن يتحلل الأداء بسبب هذه الاصطدامات.

كيف ينبغي للمرء أن يقرر أفضل ما هي القدرة على تهيئة القاموس إليه ، على افتراض أنك تعرف عدد العناصر الموجودة داخل القاموس؟

Answer 1

ما يجب عليك تهيئة قدرة القاموس إلى عاملين: (1) توزيع وظيفة GethashCode ، و (2) عدد العناصر التي يجب عليك إدراجها.

يجب توزيع وظيفة التجزئة إما بشكل عشوائي ، أو يجب صياغتها خصيصًا لمجموعة المدخلات الخاصة بك. لنفترض الأول ، ولكن إذا كنت مهتمًا بالبحث الثاني عن وظائف التجزئة المثالية.

إذا كان لديك 100 عنصر لإدراجه في القاموس ، وظيفة التجزئة الموزعة عشوائيًا ، وقمت بتعيين القدرة على 100 ، ثم عند إدراج عنصر ITH في جدول التجزئة ، لديك احتمال (I-1) / 100 سوف يصطدم العنصر مع عنصر آخر عند الإدراج. إذا كنت ترغب في خفض هذا الاحتمال للتصادم ، فقم بزيادة القدرة. مضاعفة النصف السعة المتوقعة فرصة الاصطدام.

علاوة على ذلك ، إذا كنت تعرف مدى تكرارك في الوصول إلى كل عنصر في القاموس ، فقد ترغب في إدراج العناصر من أجل تقليل التردد لأن العناصر التي تقوم بإدراجها أولاً ستكون أسرع في المتوسط.

Answer 2

لقد أجريت اختبارًا سريعًا ، ربما ليس علميًا ، ولكن إذا حددت الحجم ، فقد استغرق الأمر 1.2207780 ثانية لإضافة مليون عنصر واستغرق الأمر 1.5024960 ثانية لإضافة ما إذا لم أعطي القاموس حجمًا ... يبدو هذا ضئيلًا بالنسبة لي .

إليكم رمز الاختبار الخاص بي ، ربما يمكن لشخص ما إجراء اختبار أكثر صرامة ولكني أشك في أنه مهم.

static void Main(string[] args)
        {
            DateTime start1 = DateTime.Now;
            var dict1 = new Dictionary<string, string>(1000000);

            for (int i = 0; i < 1000000; i++)
                dict1.Add(i.ToString(), i.ToString());

            DateTime stop1 = DateTime.Now;

            DateTime start2 = DateTime.Now;
            var dict2 = new Dictionary<string, string>();

            for (int i = 0; i < 1000000; i++)
                dict2.Add(i.ToString(), i.ToString());

            DateTime stop2 = DateTime.Now;

            Console.WriteLine("Time with size initialized: " + (stop1.Subtract(start1)) + "\nTime without size initialized: " + (stop2.Subtract(start2)));
            Console.ReadLine();
        }

Answer 3

أعتقد أنك تزيد من تعقيد الأمور. إذا كنت تعرف عدد العناصر الموجودة في القاموس الخاص بك ، فحدد كل شيء عند البناء. سيساعد ذلك القاموس على تخصيص المساحة اللازمة في هياكل البيانات الداخلية الخاصة به لتجنب إعادة تخصيص البيانات وإعادة تشكيلها.

Answer 4

تحديد السعة الأولية إلى Dictionary يزيد المُنشئ الأداء لأنه سيكون هناك عدد أقل من التغييرات في الهياكل الداخلية التي تخزن قيم القاموس أثناء عمليات إضافة.

بالنظر إلى أنك تحدد سعة أولية لـ K إلى Dictionary مُنشئ ثم:

1. ال Dictionary سوف تحتفظ بكمية الذاكرة اللازمة لتخزين عناصر K ؛
2. لا يتأثر أداء الاستعلام ضد القاموس ولن يكون أسرع أو أبطأ ؛
3. لن تتطلب عمليات إضافة المزيد من تخصيصات الذاكرة (ربما باهظة الثمن) وبالتالي ستكون أسرع.

من MSDN:

إن قدرة القاموس (tkey ، tvalue) هي عدد العناصر التي يمكن إضافتها إلى القاموس (tkey ، tvalue) قبل تغيير الحجم. عند إضافة العناصر إلى القاموس (tkey ، tvalue) ، يتم زيادة السعة تلقائيًا كما هو مطلوب من خلال إعادة تخصيص الصفيف الداخلي.

إذا كان من الممكن تقدير حجم المجموعة ، فإن تحديد السعة الأولية يلغي الحاجة إلى إجراء عدد من العمليات تغيير حجمها أثناء إضافة عناصر إلى القاموس (Tkey ، TValue).

Answer 5

نعم ، على عكس أ HashTable الذي يستخدم إعادة التحويل كطريقة لحل الاصطدامات ، Dictionary سوف تستخدم التسلسل. لذا نعم ، من الجيد استخدام العد. ل HashTable ربما تريد استخدامها count * (1/fillfactor)

Answer 6

الحجم الأولي هو مجرد اقتراح. على سبيل المثال ، تحب معظم جداول التجزئة أن يكون لها أحجام هي أعداد أولية أو قوة 2.