Quando utilizzare un SortedList <TKey, TValue> su un SortedDictionary <TKey, TValue>?

Question

Questo potrebbe sembrare un duplicato di questo question, che chiede "Qual è la differenza tra SortedList e SortedDictionary?" Sfortunatamente, le risposte non fanno altro che citare la documentazione MSDN (che afferma chiaramente che ci sono delle prestazioni e le differenze nell'uso della memoria tra i due) ma in realtà non rispondono alla domanda.

In realtà (e quindi a questa domanda non ottiene le stesse risposte), in base a MSDN:

Il SortedList<TKey, TValue> generica classe è un albero binario di ricerca con O (log n) il recupero, in cui 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>.

Quindi, chiaramente questo sarebbe indicato che SortedList<TKey, TValue> è la scelta migliore a meno che non si inserisce bisogno di più velocemente e rimuovere le operazioni della non ordinati dati.

La domanda rimane ancora, date le informazioni sopra quali sono le ragioni pratiche (mondo reale, business case, ecc.) Per l'utilizzo di SortedDictionary<TKey, TValue>? In base alle informazioni sul rendimento, ciò implicherebbe che non è affatto necessario avere SortedDictionary<TKey, TValue>.

Answer 1

Questo è tutto quello che c'è da fare. Il recupero delle chiavi è paragonabile, ma l'aggiunta è molto più veloce con i dizionari.

Cerco di usare SortedList il più possibile perché mi permette di scorrere le chiavi e le collezioni di valori. Questo non è possibile con SortedDictionary per quanto ne so.

Non ne sono sicuro, ma per quanto ne so i Dizionari archiviano i dati nelle strutture Tree, mentre i List memorizzano i dati in array lineari. Questo spiega perché l'inserimento e la rimozione sono molto più veloci con i dizionari, poiché è necessario spostare meno memoria. Spiega anche perché è possibile eseguire iterazioni su SortedList ma non SortedDictionary.

Answer 2

Non sono sicuro di quanto accurata sia la documentazione MSDN su SortedList e SortedDictionary. Sembra stia dicendo che entrambi sono implementati usando un albero di ricerca binario.Ma se SortedList utilizza un albero di ricerca binario, perché sarebbe più lento su aggiunte rispetto a SortedDictionary?

In ogni caso, ecco alcuni risultati dei test delle prestazioni.

Ogni test funziona su un SortedList/SortedDictionary contenente 10.000 chiavi int32. Ogni test viene ripetuto 1.000 volte (Release build, Start without Debugging).

Il primo gruppo di test aggiunge chiavi in ​​sequenza da 0 a 9.999. Il secondo gruppo di test aggiunge chiavi casuali mescolate tra 0 e 9.999 (ogni numero viene aggiunto esattamente una volta).

***** Tests.PerformanceTests.SortedTest 

SortedDictionary Add sorted: 4411 ms 
SortedDictionary Get sorted: 2374 ms 


SortedList Add sorted: 1422 ms 
SortedList Get sorted: 1843 ms 

***** Tests.PerformanceTests.UnsortedTest 

SortedDictionary Add unsorted: 4640 ms 
SortedDictionary Get unsorted: 2903 ms 


SortedList Add unsorted: 36559 ms 
SortedList Get unsorted: 2243 ms 

Come per qualsiasi profilo, l'importante è la prestazione relativa, non i numeri effettivi.

Come si può vedere, nei dati ordinati l'elenco ordinato è più veloce dello SortedDictionary. Su dati non ordinati il ​​numero SortedList è leggermente più veloce nel recupero, ma circa 9 volte più lento all'aggiunta.

Se entrambi utilizzano internamente alberi binari, è piuttosto sorprendente che l'operazione Aggiungi su dati non ordinati sia molto più lenta per SortedList. È possibile che la lista ordinata possa anche aggiungere elementi a una struttura di dati lineare ordinata allo stesso tempo, il che lo rallenterebbe.

Tuttavia, ci si aspetta che l'utilizzo della memoria di un SortedList sia uguale o superiore o almeno uguale a SortedDictionary. Ma questo contraddice ciò che dice la documentazione MSDN.

Answer 3

Non so perché MSDN dice che SortedList<TKey, TValue> utilizza un albero binario per la sua implementazione, perché se si guarda il codice con un decompilatore come Reflector si realizza che non è vero.

SortedList<TKey, TValue> è semplicemente una matrice che cresce nel tempo.

Ogni volta che si inserisce un elemento, in primo luogo verificare se l'array ha capacità sufficiente, in caso contrario, una matrice più grande viene ricreata e vecchi elementi vengono copiati in esso (come List<T>)

Dopo di che, esso cerca dove inserire l'elemento, utilizzando una ricerca binaria (ciò è possibile poiché l'array è indicizzabile e già ordinato).

Per mantenere ordinato l'array, sposta (o spinge) tutti gli elementi situati dopo la posizione dell'elemento da inserire di una posizione (utilizzando Array.Copy()).

Esempio:

// we want to insert "3" 

2 
4 <= 3 
5 
8 
9 
.  
.  
. 

// we have to move some elements first 

2 
. <= 3 
4 
5 | 
8 v 
9 
. 
. 

che spiega il motivo per cui le prestazioni di SortedList è così male quando si inserisce elementi non ordinati. Deve ricalcare alcuni elementi quasi ogni inserimento. L'unico caso che non deve essere fatto è quando l'elemento deve essere inserito alla fine dell'array.

SortedDictionary<TKey, TValue> è diverso e utilizza un albero binario per inserire e recuperare elementi. Ha anche un costo di inserimento perché a volte l'albero deve essere riequilibrato (ma non ogni inserimento).

Le prestazioni sono abbastanza simili durante la ricerca di un elemento con SortedList o SortedDictionary perché entrambi utilizzano una ricerca binaria.

---

A mio parere, si dovrebbe mai uso SortedList per ordinare solo un array. A meno che tu non abbia pochi elementi, sarà sempre più veloce inserire valori in una lista (o array) e quindi chiamare il metodo Sort().

SortedList è particolarmente utile quando si dispone di un elenco di valori già ordinati (ad esempio: dal database), si vuole mantenere allineati ed eseguire alcune operazioni che potrebbero trarre vantaggio è ordinato (ad esempio: Contains() metodo SortedList esegue un ricerca binaria anziché ricerca lineare)

SortedDictionary offre gli stessi vantaggi di SortedList ma offre prestazioni migliori se i valori da inserire non sono già ordinati.

---

EDIT: Se si utilizza .NET Framework 4.5, in alternativa al SortedDictionary<TKey, TValue> è SortedSet<T>. Funziona allo stesso modo di SortedDictionary, usando un albero binario, ma le chiavi e i valori sono gli stessi qui.

Answer 4

Sono destinati a due scopi diversi?

Non c'è molta differenza semantica in questi due tipi di raccolta in .NET. Entrambi offrono una ricerca con chiave e mantengono le voci in ordine di chiavi. Nella maggior parte dei casi starai bene con entrambi. Forse l'unico elemento di differenziazione sarebbe il permesso di recupero indicizzato SortedList.

Ma prestazioni?

Tuttavia c'è una differenza di prestazioni che potrebbe essere essere un fattore più forte per scegliere tra di loro. Ecco una vista tabellare della loro complessità asintotica.

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

Sommario

a circa riassumere, si desidera un SortedList<K, V> quando:

1. si richiede indicizzati look-up.
2. è preferibile avere un sovraccarico di memoria minore.
3. i dati di input sono già ordinati (diciamo che è già stato ordinato da db).

Si potrebbe invece voler preferire un SortedDictionary<K, V> quando:

1. relativi complessivi questioni prestazioni (rispetto al ridimensionamento).
2. i dati di input non sono ordinati.

La scrittura di codice

Sia SortedList<K, V> e SortedDictionary<K, V> implementare IDictionary<K, V>, quindi nel codice è possibile restituire IDictionary<K, V> dal metodo o dichiarare variabile come IDictionary<K, V>. In pratica nascondi i dettagli dell'implementazione e il codice contro l'interfaccia.

IDictionary<K, V> x = new SortedDictionary<K, V>(); //for eg. 

In futuro, è più facile passare da entrambi nel caso in cui non si è soddisfatti delle prestazioni caratteristiche di una raccolta.

---

Per maggiori informazioni sui due tipi di raccolta vedere l'originale question collegato.

Answer 5

Rappresentazione visiva delle differenze di prestazioni.