ما الفرق بين فرز القائمة و SortedCtionary؟

Question

هل هناك أي فرق عملي حقيقي بين SortedList<TKey,TValue> و SortedDictionary<TKey,TValue>ب هل هناك أي ظرف من الظروف التي تستخدمها على وجه التحديد وليس الآخر؟

Answer 1

نعم - تختلف خصائص أدائها بشكل كبير. من المحتمل أن يكون من الأفضل الاتصال بهم SortedList و SortedTree كما يعكس هذا التنفيذ عن كثب.

انظر إلى مستندات MSDN لكل منها (SortedList, SortedDictionary) للحصول على تفاصيل الأداء لعمليات مختلفة في أشكال مختلفة. إليك ملخص جميل (من SortedDictionary مستندات):

ال SortedDictionary<TKey, TValue> فئة عامة هي شجرة بحث ثنائية مع استرجاع O (سجل ن)، حيث n هو عدد العناصر في القاموس. في هذا، يشبه SortedList<TKey, TValue> فئة عامة. تحتوي الفئتين على نماذج كائن مماثلة، واسترجاع كلاهما (سجل ن). حيث تختلف الطبقتين في استخدام الذاكرة وسرعة الإدراج وإزالة:

• SortedList<TKey, TValue> يستخدم ذاكرة أقل من SortedDictionary<TKey, TValue>.

• SortedDictionary<TKey, TValue> لديه عمليات أسرع لإدراج وإزالة البيانات غير المستهلكة، O (سجل N) بدلا من O (ن) ل SortedList<TKey, TValue>.

• إذا كانت القائمة قديمة كل مرة واحدة من البيانات الفرز، SortedList<TKey, TValue> أسرع من ذلك SortedDictionary<TKey, TValue>.

(SortedList في الواقع يحافظ على صفيف مرتبة، بدلا من استخدام شجرة. لا يزال يستخدم البحث الثنائي للعثور على العناصر.)

Answer 2

إليك طريقة عرض مجدولة إذا كان ذلك يساعد ...

من أداء إنطباع:

+------------------+---------+----------+--------+----------+----------+---------+
| Collection       | Indexed | Keyed    | Value  | Addition |  Removal | Memory  |
|                  | lookup  | lookup   | lookup |          |          |         |
+------------------+---------+----------+--------+----------+----------+---------+
| SortedList       | O(1)    | O(log n) | O(n)   | O(n)*    | O(n)     | Lesser  |
| SortedDictionary | n/a     | O(log n) | O(n)   | O(log n) | O(log n) | Greater |
+------------------+---------+----------+--------+----------+----------+---------+

* Insertion is O(1) for data that are already in sort order, so that each 
  element is added to the end of the list (assuming no resize is required).

من أ تطبيق إنطباع:

+------------+---------------+----------+------------+------------+------------------+
| Underlying | Lookup        | Ordering | Contiguous | Data       | Exposes Key &    |
| structure  | strategy      |          | storage    | access     | Value collection |
+------------+---------------+----------+------------+------------+------------------+
| 2 arrays   | Binary search | Sorted   | Yes        | Key, Index | Yes              |
| BST        | Binary search | Sorted   | No         | Key        | Yes              |
+------------+---------------+----------+------------+------------+------------------+

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

يمكنك قراءة المزيد هنا, هنا, هنا, هنا و هنا.

Answer 3

أنا متصدع العاكس المفتوح لإلقاء نظرة على هذا كما يبدو أن هناك قليلا من الارتباك حول SortedList. وبعد في الواقع ليست شجرة البحث الثنائية، إنه مجموعة فرز (حسب المفتاح) من أزواج القيمة الرئيسية. وبعد هنالك أيضا TKey[] keys المتغير الذي يتم فرزه بمزامنة مع أزواج القيمة الرئيسية وتستخدم للبحث الثنائي.

هنا بعض المصدر (استهداف .NET 4.5) النسخ الاحتياطي لمطالبي.

أعضاء القطاع الخاص

// Fields
private const int _defaultCapacity = 4;
private int _size;
[NonSerialized]
private object _syncRoot;
private IComparer<TKey> comparer;
private static TKey[] emptyKeys;
private static TValue[] emptyValues;
private KeyList<TKey, TValue> keyList;
private TKey[] keys;
private const int MaxArrayLength = 0x7fefffff;
private ValueList<TKey, TValue> valueList;
private TValue[] values;
private int version;

sortedlist.ctor (التصدي، Icomparer)

public SortedList(IDictionary<TKey, TValue> dictionary, IComparer<TKey> comparer) : this((dictionary != null) ? dictionary.Count : 0, comparer)
{
    if (dictionary == null)
    {
        ThrowHelper.ThrowArgumentNullException(ExceptionArgument.dictionary);
    }
    dictionary.Keys.CopyTo(this.keys, 0);
    dictionary.Values.CopyTo(this.values, 0);
    Array.Sort<TKey, TValue>(this.keys, this.values, comparer);
    this._size = dictionary.Count;
}

sortedlist.add (tkey، tvalue): باطلة

public void Add(TKey key, TValue value)
{
    if (key == null)
    {
        ThrowHelper.ThrowArgumentNullException(ExceptionArgument.key);
    }
    int num = Array.BinarySearch<TKey>(this.keys, 0, this._size, key, this.comparer);
    if (num >= 0)
    {
        ThrowHelper.ThrowArgumentException(ExceptionResource.Argument_AddingDuplicate);
    }
    this.Insert(~num, key, value);
}

sortedlist.removeat (int): باطلة

public void RemoveAt(int index)
{
    if ((index < 0) || (index >= this._size))
    {
        ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.index, ExceptionResource.ArgumentOutOfRange_Index);
    }
    this._size--;
    if (index < this._size)
    {
        Array.Copy(this.keys, index + 1, this.keys, index, this._size - index);
        Array.Copy(this.values, index + 1, this.values, index, this._size - index);
    }
    this.keys[this._size] = default(TKey);
    this.values[this._size] = default(TValue);
    this.version++;
}

Answer 4

تفحص ال صفحة MSDN للنشاط:

من قسم الملاحظات:

ال SortedList<(Of <(TKey, TValue>)>) الطبقة العامة هي شجرة بحث ثنائية مع O(log n) استرجاع، حيث n هو عدد العناصر في القاموس. في هذا، يشبه SortedDictionary<(Of <(TKey, TValue>)>) فئة عامة. الفصولتين لها نماذج كائن مماثلة، وكلاهما O(log n) استرجاع. حيث تختلف الطبقتين في استخدام الذاكرة وسرعة الإدراج وإزالة:

• SortedList<(Of <(TKey, TValue>)>) يستخدم ذاكرة أقل من SortedDictionary<(Of <(TKey, TValue>)>).

• SortedDictionary<(Of <(TKey, TValue>)>) لديه عمليات إدراج واستبدال أسرع للبيانات غير الممثلة، O(log n) في مقابل O(n) بالنسبة SortedList<(Of <(TKey, TValue>)>).

• إذا كانت القائمة قديمة كل مرة واحدة من البيانات الفرز، SortedList<(Of <(TKey, TValue>)>) أسرع من ذلك SortedDictionary<(Of <(TKey, TValue>)>).

Answer 5

هذا هو التمثيل البصري لكيفية مقارنة العروض مع بعضها البعض.

Answer 6

يقال ما يكفي بالفعل في الموضوع، ولكن للحفاظ على الأمر بسيط، وهنا تأخذ بلدي.

قاموس مرتبة يجب أن تستخدم عندما-

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

على الجانب الآخر، قائمة فرزها يجب أن تستخدم عندما-

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

أتمنى أن يساعدك هذا!!

Answer 7

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