Qual è la differenza tra SortedList e SortedDictionary?

Question

Esiste una reale differenza pratica tra uno SortedList<TKey,TValue> e uno SortedDictionary<TKey,TValue>? Ci sono circostanze in cui si utilizzerebbe specificatamente l'una e non l'altra?

Answer 1

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

Consultare i documenti MSDN per ognuno di essi (SortedList, SortedDictionary) per i dettagli delle prestazioni per diverse operazioni in diversi situtations. Ecco un bel riassunto (dalle SortedDictionary docs):

Il SortedDictionary<TKey, TValue> generica classe è un albero binario di ricerca con O (log n) di recupero, dove n è il numero di elementi nel dizionario. In questo è simile alla classe generica . Le due classi hanno modelli di oggetti simili ed entrambi hanno il recupero di O (log n) . Dove i due classi differiscono è in uso la memoria e la velocità di inserimento e la rimozione:

• SortedList<TKey, TValue> utilizza meno memoria di SortedDictionary<TKey, TValue>.

• SortedDictionary<TKey, TValue> ha inserimento rapido e rimozione operazioni per dati non ordinati, O (log n) al contrario di O (n) per SortedList<TKey, TValue>.

• Se l'elenco è popolato tutto in una volta dai dati ordinati, SortedList<TKey, TValue> è più veloce di SortedDictionary<TKey, TValue>.

(SortedList mantiene in realtà un array ordinato, piuttosto che utilizzare un albero Esso utilizza ancora la ricerca binaria per trovare gli elementi..)

Answer 2

Scopri i MSDN page for SortedList:

Da sezione Osservazioni:

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

• SortedList<(Of <(TKey, TValue>)>) utilizza meno memoria SortedDictionary<(Of <(TKey, TValue>)>).

• SortedDictionary<(Of <(TKey, TValue>)>) ha operazioni di inserimento e rimozione più rapide per dati non ordinati, O(log n) in confronto a O(n) per SortedList<(Of <(TKey, TValue>)>).

• Se l'elenco viene popolato tutto in una volta da dati ordinati, SortedList<(Of <(TKey, TValue>)>) è più veloce di SortedDictionary<(Of <(TKey, TValue>)>).

Answer 3

ho incrinato Reflector aperto a dare un'occhiata a questo come sembra che ci sia 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 ordinata in sincronia con le coppie chiave-valore e utilizzata per la ricerca binaria.

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

membri privati ​​

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

Answer 4

Qui è una vista tabellare 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). 

Dal punto di implementazione prospettiva:

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

A a circa parafrasi, se si richiede prestazioni raw SortedDictionary potrebbe essere una scelta migliore. Se si richiede un sovraccarico di memoria e un recupero indicizzati minori, SortedList si adatta meglio. See this question for more on when to use which.

Si può leggere di più here, here, here, here e here.

Answer 5

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

Answer 6

accesso Index (citato 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).

Answer 7

Già si dice già sull'argomento, tuttavia per semplificare, ecco la mia opinione.

dizionario Ordinati dovrebbe essere usato quando- sono tenuti

• Più inserti e le operazioni di eliminazione.
• Dati non ordinati.
• L'accesso chiave è sufficiente e non è richiesto l'accesso all'indice.
• La memoria non è un collo di bottiglia.

Sull'altro lato, elenco ordinato deve essere utilizzato quando- sono richiesti

• Altre ricerche e meno inserti e operazioni di eliminazione.
• I dati sono già ordinati (se non tutti, la maggior parte).
• È necessario l'accesso all'indice.
• La memoria è un sovraccarico.

Spero che questo aiuti !!