لماذا قائمة<T>.نوع طريقة ترتيب متساوية IComparable<T> العناصر ؟

Question

لدي مشكلة مع ما نوع الأسلوب يتعامل مع الفرز.بالنظر إلى العنصر التالي:

class Element : IComparable<Element>
{
    public int Priority { get; set; }
    public string Description { get; set; }

    public int CompareTo(Element other)
    {
        return Priority.CompareTo(other.Priority);
    }
}

إذا كنت في محاولة لفرز هذه الطريقة:

List<Element> elements = new List<Element>()
                             {
                                 new Element()
                                     {
                                         Priority = 1,
                                         Description = "First"
                                     },
                                 new Element()
                                     {
                                         Priority = 1,
                                         Description = "Second"
                                     },
                                 new Element()
                                     {
                                         Priority = 2,
                                         Description = "Third"
                                     }
                             };
elements.Sort();

ثم العنصر الأول هو سابقا العنصر الثاني "الثاني".أو بعبارة أخرى هذا الزعم فشل:

Assert.AreEqual("First", elements[0].Description);

لماذا .صافي إعادة ترتيب قائمة عندما عناصر هي أساسا نفس الشيء ؟ أود فقط إعادة ترتيب قائمة إذا كانت المقارنة بإرجاع قيمة غير صفرية.

Answer 1

من الوثائق القائمة.نوع الأسلوب() من MSDN:

هذا الأسلوب يستخدم صفيف.النوع الذي يستخدم فرز سريع الخوارزمية.هذا التنفيذ ينفذ غير مستقرة النوع ؛ هذا إن اثنين من عناصر متساوية ، فإن النظام قد لا تكون محفوظة.في المقابل, مستقرة نوعا ما يحافظ على ترتيب العناصر التي هي على قدم المساواة.

وهنا الرابط:http://msdn.microsoft.com/en-us/library/b0zbh7b6.aspx

أساسا هذا النوع هو المنفذ كما تم تصميمها وتوثيقها.

Answer 2

هنا هو طريقة تمديد SortStable() ل List<T> where T : IComparable<T>:

public static void SortStable<T>(this List<T> list) where T : IComparable<T>
{
    var listStableOrdered = list.OrderBy(x => x, new ComparableComparer<T>()).ToList();
    list.Clear();
    list.AddRange(listStableOrdered);
}

private class ComparableComparer<T> : IComparer<T> where T : IComparable<T>
{
    public int Compare(T x, T y)
    {
        return x.CompareTo(y);
    }
}

الاختبار:

[Test]
public void SortStable()
{
    var list = new List<SortItem>
                    {
                        new SortItem{ SortOrder = 1, Name = "Name1"},
                        new SortItem{ SortOrder = 2, Name = "Name2"},
                        new SortItem{ SortOrder = 2, Name = "Name3"},
                    };

    list.SortStable();

    Assert.That(list.ElementAt(0).SortOrder, Is.EqualTo(1));
    Assert.That(list.ElementAt(0).Name, Is.EqualTo("Name1"));
    Assert.That(list.ElementAt(1).SortOrder, Is.EqualTo(2));
    Assert.That(list.ElementAt(1).Name, Is.EqualTo("Name2"));
    Assert.That(list.ElementAt(2).SortOrder, Is.EqualTo(2));
    Assert.That(list.ElementAt(2).Name, Is.EqualTo("Name3"));
}

private class SortItem : IComparable<SortItem>
{
    public int SortOrder { get; set; }
    public string Name { get; set; }

    public int CompareTo(SortItem other)
    {
        return SortOrder.CompareTo(other.SortOrder);
    }
}

في طريقة الاختبار, إذا كنت استدعاء نوع الأسلوب() بدلا من SortStable(), يمكنك أن ترى أن الاختبار سوف تفشل.

Answer 3

قلت كيف لمقارنة الأشياء و هذا ما فعلته.يجب أن لا تعتمد على تنفيذ الداخلي من نوع في التطبيق الخاص بك.هذا هو السبب في أنها تمكنك من تجاوز CompareTo.إذا كنت تريد أن يكون النوع الثانوي المعلمة ("الوصف" في هذه الحالة), رمز في CompareTo.تعتمد على كيفية فرز يحدث لمجرد أن العمل هو وسيلة رائعة رمز في الخلل الذي من الصعب جدا العثور على.

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

Answer 4

انظر الردود الأخرى لماذا قائمة.نوعا ما() غير مستقرة.إذا كنت بحاجة إلى مستقرة نوعا ما و تستخدم .NET framework 3.5 محاولة Enumerable.OrderBy() (LINQ).

Answer 5

يمكنك إصلاح هذا عن طريق إضافة "قيمة المؤشر" إلى الهيكل الخاص ، بما في ذلك في CompareTo الأسلوب عندما الأولوية.CompareTo بإرجاع 0.ثم كنت بحاجة إلى تهيئة "مؤشر" القيمة قبل القيام النوع.

على CompareTo الطريقة سوف تبدو مثل هذا:

public int CompareTo(Element other)
{
    var ret = Priority.CompareTo(other.Priority);
    if (ret == 0)
    {
        ret = Comparer<int>.Default.Compare(Index, other.Index);
    }
    return ret;
}

ثم بدلا من القيام elements.Sort(), ، كنت تفعل:

for(int i = 0; i < elements.Count; ++i)
{
    elements[i].Index = i;
}
elements.Sort();

Answer 6

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

نوع الأساليب التي سيتم استخدامها تحت أطر مثل جافا أو .صافي يمكن عمليا الاستفادة من أكثر التخزين المؤقت مما كان مقبول في ج qsort() الروتينية.ذاكرة مؤقتة شرط يساوي حجم المصفوفة يتم فرزها في معظم الحالات لا تشكل أي مشكلة معينة.ومع ذلك, منذ انها كانت التقليدية للمكتبات لتزويد فرز سريع التنفيذ ، التي يبدو أن نمط تليها .صافي.

Answer 7

إذا أردت الفرز على أساس اثنين من الحقول بدلا من واحدة يمكنك أن تفعل ذلك:

class Element : IComparable<Element>
{
    public int Priority { get; set; }
    public string Description { get; set; }

    public int CompareTo(Element other)
    {
        if (Priority.CompareTo(other.Priority) == 0)
        {
            return Description.CompareTo(other.Description);
        } else {
            return Priority.CompareTo(other.Priority);
        }
    }
}

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