Apa perbedaan antara SortedList dan SortedDictionary?

Apakah ada perbedaan praktis yang nyata antara a SortedList<TKey,TValue>dan a SortedDictionary<TKey,TValue>? Apakah ada keadaan di mana Anda secara khusus akan menggunakan satu dan bukan yang lain?

Ya - karakteristik kinerjanya berbeda secara signifikan. Mungkin akan lebih baik untuk memanggil mereka SortedListdan SortedTreekarena itu mencerminkan implementasi lebih dekat.

Lihatlah dokumen MSDN untuk masing-masing ( SortedList, SortedDictionary) untuk detail kinerja untuk operasi yang berbeda di berbagai situasi. Berikut ringkasan yang bagus (dari SortedDictionarydokumen):

Kelas SortedDictionary<TKey, TValue>generik adalah pohon pencarian biner dengan pengambilan O (log n), di mana n adalah jumlah elemen dalam kamus. Dalam hal ini, mirip dengan SortedList<TKey, TValue>kelas generik. Kedua kelas memiliki model objek yang sama, dan keduanya memiliki pengambilan O (log n). Perbedaan kedua kelas dalam penggunaan memori dan kecepatan penyisipan dan penghapusan:

• SortedList<TKey, TValue>menggunakan lebih sedikit memori daripada SortedDictionary<TKey, TValue>.

• SortedDictionary<TKey, TValue>memiliki operasi penyisipan dan penghapusan yang lebih cepat untuk data yang tidak disortir, O (log n) dibandingkan dengan O (n) untuk SortedList<TKey, TValue>.

• Jika daftar dihuni sekaligus dari data yang diurutkan, SortedList<TKey, TValue>lebih cepat dari SortedDictionary<TKey, TValue>.

( SortedListsebenarnya mempertahankan array yang diurutkan, daripada menggunakan pohon. Ia masih menggunakan pencarian biner untuk menemukan elemen.)

Berikut ini adalah tampilan tabular jika ini membantu ...

Dari perspektif kinerja :

+------------------+---------+----------+--------+----------+----------+---------+
| 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).

Dari perspektif implementasi :

+------------+---------------+----------+------------+------------+------------------+
| 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              |
+------------+---------------+----------+------------+------------+------------------+

Untuk kira-kira parafrase, jika Anda membutuhkan kinerja baku SortedDictionarybisa menjadi pilihan yang lebih baik. Jika Anda membutuhkan overhead memori yang lebih rendah dan pengambilan diindeks SortedListlebih cocok. Lihat pertanyaan ini untuk lebih lanjut tentang kapan menggunakan yang mana.

Anda dapat membaca lebih lanjut di sini , di sini , di sini , di sini dan di sini .

Saya membuka Reflector untuk melihat ini karena sepertinya ada sedikit kebingungan SortedList. Ini sebenarnya bukan pohon pencarian biner, itu adalah array yang diurutkan (dengan kunci) dari pasangan nilai kunci . Ada juga TKey[] keysvariabel yang disortir dalam sinkronisasi dengan pasangan kunci-nilai dan digunakan untuk pencarian biner.

Berikut adalah beberapa sumber (penargetan .NET 4.5) untuk mencadangkan klaim saya.

Anggota pribadi

// 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 (IDictionary, 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): void

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): void

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++;
}

Lihatlah halaman MSDN untuk SortedList :

Dari bagian Keterangan:

Kelas SortedList<(Of <(TKey, TValue>)>)generik adalah pohon pencarian biner dengan O(log n)pengambilan, di mana njumlah elemen dalam kamus. Dalam hal ini, mirip dengan SortedDictionary<(Of <(TKey, TValue>)>)kelas generik. Kedua kelas memiliki model objek yang sama, dan keduanya memiliki O(log n)pengambilan. Perbedaan kedua kelas dalam penggunaan memori dan kecepatan penyisipan dan penghapusan:

• SortedList<(Of <(TKey, TValue>)>)menggunakan lebih sedikit memori daripada SortedDictionary<(Of <(TKey, TValue>)>).

• SortedDictionary<(Of <(TKey, TValue>)>)memiliki operasi penyisipan dan penghapusan yang lebih cepat untuk data yang tidak disortir, O(log n)berbeda dengan O(n)untuk SortedList<(Of <(TKey, TValue>)>).

• Jika daftar dihuni sekaligus dari data yang diurutkan, SortedList<(Of <(TKey, TValue>)>)lebih cepat dari SortedDictionary<(Of <(TKey, TValue>)>).

Ini adalah representasi visual tentang bagaimana pertunjukan dibandingkan satu sama lain.

Cukup sudah dikatakan pada topik, namun untuk membuatnya tetap sederhana, inilah pendapat saya.

Kamus yang disortir harus digunakan saat-

• Diperlukan lebih banyak sisipan dan operasi penghapusan.
• Data dalam tidak terurut.
• Akses kunci sudah cukup dan akses indeks tidak diperlukan.
• Memori bukan hambatan.

Di sisi lain, Daftar Diurutkan harus digunakan ketika-

• Diperlukan lebih banyak pencarian dan lebih sedikit sisipan dan operasi penghapusan.
• Data sudah diurutkan (jika tidak semua, sebagian besar).
• Diperlukan akses indeks.
• Memori adalah overhead.

Semoga ini membantu!!

Akses indeks (disebutkan di sini) adalah perbedaan praktis. Jika Anda perlu mengakses penerus atau pendahulunya, Anda perlu SortedList. SortedDictionary tidak dapat melakukannya sehingga Anda cukup terbatas dengan bagaimana Anda dapat menggunakan penyortiran (pertama / foreach).