Qual è la differenza tra SortedList e SortedDictionary?

C’è una vera differenza pratica tra una SortedList e SortedDictionary ? Ci sono circostanze in cui si utilizzerebbe specificatamente l’una e non l’altra?

Sì, le loro caratteristiche di prestazione differiscono in modo significativo. Probabilmente sarebbe meglio chiamarli SortedList e SortedList quanto ciò rispecchia l’implementazione più da vicino.

Esaminare i documenti MSDN per ciascuno di essi ( SortedList , SortedDictionary ) per i dettagli delle prestazioni per diverse operazioni in diversi situtations. Ecco un bel riassunto (dai documenti SortedDictionary ):

La class generica SortedDictionary è un albero di ricerca binario con O (log n) retrieval, dove n è il numero di elementi nel dizionario. In questo, è simile alla class generica SortedList . Le due classi hanno modelli di oggetti simili ed entrambi hanno il recupero di O (log n). Dove le due classi differiscono è nell’uso della memoria e nella velocità di inserimento e rimozione:

  • SortedList utilizza meno memoria di SortedDictionary .

  • SortedDictionary ha operazioni di inserimento e rimozione più veloci per i dati non ordinati, O (log n) in contrapposizione a O (n) per SortedList .

  • Se l’elenco viene popolato tutto in una volta dai dati ordinati, SortedList è più veloce di SortedDictionary .

( SortedList mantiene in realtà una matrice ordinata, anziché utilizzare un albero, ma utilizza ancora la ricerca binaria per trovare gli elementi.)

Ecco una vista tabulare se aiuta …

Dal punto di vista delle prestazioni :

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

Da una prospettiva di implementazione :

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

Per approssimativamente parafrasare, se hai bisogno di prestazioni SortedDictionary , SortedDictionary potrebbe essere una scelta migliore. Se si richiede un minore sovraccarico di memoria e il recupero indicizzato, SortedList adatta meglio. Vedi questa domanda per maggiori informazioni su quando usare quale.

Puoi leggere di più qui , qui , qui , qui e qui .

Ho aperto crack Reflector per dare un’occhiata a questo dato che sembra esserci un po ‘di confusione su SortedList . In realtà non è un albero di ricerca binario, è una matrice ordinata (per chiave) di coppie chiave-valore . Esiste anche una variabile TKey[] keys che viene ordinata in sincronia con le coppie chiave-valore e utilizzata per la ricerca binaria.

Ecco alcune fonti (con targeting per .NET 4.5) per il backup delle mie affermazioni.

Membri privati

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

SortedList.ctor (IDictionary, IComparer)

 public SortedList(IDictionary dictionary, IComparer 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(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(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++; } 

Controlla la pagina MSDN per SortedList :

Dalla sezione Note:

La class generica SortedList<(Of <(TKey, TValue>)>) è un albero di ricerca binario con O(log n) retrieval, dove n è il numero di elementi nel dizionario. In questo, è simile alla class generica SortedDictionary<(Of <(TKey, TValue>)>) . Le due classi hanno modelli di oggetti simili ed entrambi hanno il recupero di O(log n) . Dove le due classi differiscono è nell’uso della memoria e nella velocità di inserimento e rimozione:

  • SortedList<(Of <(TKey, TValue>)>) utilizza meno memoria di SortedDictionary<(Of <(TKey, TValue>)>) .
  • SortedDictionary<(Of <(TKey, TValue>)>) ha operazioni di inserimento e rimozione più veloci per i dati non ordinati, O(log n) in contrapposizione a O(n) per SortedList<(Of <(TKey, TValue>)>) .

  • Se l’elenco viene popolato contemporaneamente da dati ordinati, SortedList<(Of <(TKey, TValue>)>) è più veloce di SortedDictionary<(Of <(TKey, TValue>)>) .

Questa è la rappresentazione visiva di come le prestazioni si confrontano tra loro.

Si dice già abbastanza sull’argomento, tuttavia per semplificare, ecco la mia opinione.

Il dizionario ordinato dovrebbe essere usato quando-

  • Sono necessari più inserimenti e operazioni di cancellazione.
  • Dati non ordinati.
  • L’accesso chiave è sufficiente e l’accesso all’indice non è richiesto.
  • La memoria non è un collo di bottiglia.

D’altra parte, l’ elenco ordinato dovrebbe essere usato quando-

  • Sono richieste più ricerche e meno inserimenti e operazioni di cancellazione.
  • I dati sono già ordinati (se non tutti, la maggior parte).
  • È richiesto l’accesso all’Indice.
  • La memoria è un sovraccarico.

Spero che questo ti aiuti!!

L’accesso all’Indice (menzionato qui) è la differenza pratica. Se è necessario accedere al successore o al predecessore, è necessario SortedList. SortedDictionary non può farlo, quindi sei abbastanza limitato da come puoi usare l’ordinamento (first / foreach).