قائمة . تنفيذ التنفيذ دون المستوى الأمثل

Question

يشير التنميط الخاص بي بتطبيق C# إلى أن وقتًا مهمًا يقضي في List<T>.AddRange. يشير استخدام العاكس للنظر في الكود في هذه الطريقة إلى أنه يستدعي List<T>.InsertRange الذي يتم تنفيذه على هذا النحو:

public void InsertRange(int index, IEnumerable<T> collection)
{
    if (collection == null)
    {
        ThrowHelper.ThrowArgumentNullException(ExceptionArgument.collection);
    }
    if (index > this._size)
    {
        ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.index, ExceptionResource.ArgumentOutOfRange_Index);
    }
    ICollection<T> is2 = collection as ICollection<T>;
    if (is2 != null)
    {
        int count = is2.Count;
        if (count > 0)
        {
            this.EnsureCapacity(this._size + count);
            if (index < this._size)
            {
                Array.Copy(this._items, index, this._items, index + count, this._size - index);
            }
            if (this == is2)
            {
                Array.Copy(this._items, 0, this._items, index, index);
                Array.Copy(this._items, (int) (index + count), this._items, (int) (index * 2), (int) (this._size - index));
            }
            else
            {
                T[] array = new T[count];          // (*)
                is2.CopyTo(array, 0);              // (*)
                array.CopyTo(this._items, index);  // (*)
            }
            this._size += count;
        }
    }
    else
    {
        using (IEnumerator<T> enumerator = collection.GetEnumerator())
        {
            while (enumerator.MoveNext())
            {
                this.Insert(index++, enumerator.Current);
            }
        }
    }
    this._version++;
}

private T[] _items;

يمكن للمرء أن يجادل بأن بساطة الواجهة (التي تحتوي فقط على الحمل الزائد من inserTrange) تبرر الأداء النفقات العامة لنوع وقت التشغيل من نوع Runtime Cheching والصب. ولكن ما الذي يمكن أن يكون السبب وراء الأسطر الثلاثة التي أشرت إليها (*) ؟ أعتقد أنه يمكن إعادة كتابته إلى البديل الأسرع:

is2.CopyTo(this._items, index);

هل ترى أي سبب لعدم استخدام هذا البديل الأكثر بساطة وأسرع على ما يبدو؟

تعديل:

شكرا على الإجابات. لذا فإن رأي الإجماع هو أن هذا مقياس وقائي ضد مجموعة المدخلات التي تنفذ نسخها بطريقة معيبة/ضارة. بالنسبة لي ، يبدو أنه من المبالغة في دفع سعر 1) نوع التشغيل المستمر 2) التخصيص الديناميكي للمصفوفة المؤقتة 3) مضاعفة عملية النسخ ، عندما يكون كل هذا قد تم حفظه عن طريق تحديد 2 أو بضع أحمال زائدة من inserTrange ، الحصول على واحد IEnumerable كما هو الحال الآن ، والثاني يحصل List<T>, ، الحصول على ثالث T[]. كان من الممكن تنفيذ الاثنان اللاحقين للركض مرتين بالسرعة التي في الحالة الحالية.

تحرير 2:

لقد قمت بتطبيق قائمة فئة سريعة ، مطابقة للقائمة ، إلا أنها توفر أيضًا حمولة زائدة من الإضافات التي تأخذ وسيطة T []. لا يحتاج هذا الحمل الزائد إلى التحقق من النوع الديناميكي ، والكشف المزدوج للعناصر. لقد قمت بعمل ملف تعريف هذا fastlist. يتفوق تنفيذي على سرعة القائمة القياسية. يستغرق القائمة. MadDrange حوالي 5 ٪ من وقت التشغيل في أحد سيناريوهات الاستخدام المهمة لتطبيقنا ، حيث يمكن استبدال القائمة بفئة توفير إضافة أسرع يمكن تحسين وقت تشغيل التطبيق بنسبة 4 ٪.

Answer 1

إنهم يمنعون تنفيذ ICollection<T> من الوصول إلى مؤشرات قائمة الوجهة خارج حدود الإدراج. يؤدي التنفيذ أعلاه إلى IndexOutOfBoundsException إذا كان تنفيذ (أو "التلاعب") CopyTo يسمى.

لا تنسى T[].CopyTo يتم تنفيذها حرفيًا داخليًا تمامًا memcpy, ، وبالتالي فإن الأداء النفقات العامة لإضافة هذا الخط هو دقيقة. عندما يكون لديك تكلفة منخفضة لإضافة السلامة إلى عدد هائل من المكالمات ، يمكنك القيام بذلك أيضًا.

تعديل: الجزء الذي أجده غريبًا هو حقيقة أن الدعوة إلى ICollection<T>.CopyTo (النسخ إلى الصفيف المؤقت) لا يحدث فورًا بعد الدعوة إلى EnsureCapacity. إذا تم نقله إلى هذا الموقع ، ثم بعد أي استثناء متزامن ستبقى القائمة دون تغيير. كما هو ، هذا الشرط يحمل فقط في حالة حدوث الإدراج في نهاية القائمة. المنطق هنا هو:

• يحدث كل التخصيص اللازم قبل تغيير عناصر القائمة.
• الدعوات إلى Array.Copy لا يمكن أن تفشل لأن
  • تم تخصيص الذاكرة بالفعل
  • تم فحص الحدود بالفعل
  • تتطابق أنواع العناصر من صفائف المصدر والوجهة
  • لا يوجد "منشئ نسخ" يستخدم كما في C ++ - إنه مجرد memcpy
• العناصر الوحيدة التي يمكن أن ترمي استثناء هي الدعوة الخارجية إلى ICollection.CopyTo والمخصصات اللازمة لتغيير حجم القائمة وتخصيص الصفيف المؤقت. إذا حدثت هذه الثلاثة قبل نقل العناصر للإدراج ، فإن المعاملة لتغيير القائمة لا يمكن أن ترمي استثناء متزامن.
• ملاحظة أخيرة: هذا العنوان سلوك استثنائي تمامًا - الأساس المنطقي أعلاه ليس أضف سلامة الموضوع.

تحرير 2 (الرد على تحرير البروتوكول الاختياري): هل حددت هذا؟ أنت تقدم بعض الادعاءات الجريئة بأنه كان ينبغي على Microsoft اختيار واجهة برمجة تطبيقات أكثر تعقيدًا ، لذلك يجب عليك التأكد من أنك على صحة في التأكيدات على أن الطريقة الحالية بطيئة. لم أواجه مشكلة في أداء InsertRange, ، وأنا متأكد تمامًا من أن أي مشاكل في الأداء يواجهها شخص ما سيتم حلها بشكل أفضل مع إعادة تصميم الخوارزمية من خلال إعادة تنفيذ القائمة الديناميكية. فقط حتى لا تأخذني كأنك قاسي بطريقة سلبية ، ضع ما يلي في الاعتبار:

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

Answer 2

إنه سؤال جيد ، أنا أكافح من أجل التوصل إلى سبب. لا يوجد تلميح في المصدر المرجعي. أحد الاحتمالات هو أنهم يحاولون تجنب مشكلة عندما يكون الفئة التي تنفذ كائنات طريقة iCollection <>. لا ينبغي أن يكون الوصول إليها.

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

هذه ليست تفسيرات كبيرة.

Answer 3

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

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

في جوهرها ، ستعزز تنفيذ فئة القائمة ، على الرغم من أن البرمجة الموجهة للكائنات تخبرنا أن التنفيذ الداخلي لبنية البيانات يجب أن يكون شيئًا يمكن تغييره دون كسر التعليمات البرمجية الأخرى.