Qual è la differenza tra SortedList e insieme sorteddictionary?

Question

C'è qualche reale differenza pratica tra un SortedList<TKey,TValue> e un SortedDictionary<TKey,TValue>?Vi sono circostanze in cui si sarebbe in particolare l'uso di uno e non l'altro?

Answer 1

Sì - le loro caratteristiche prestazionali differiscono in modo significativo. Probabilmente sarebbe meglio chiamarli SortedList e SortedTree come che riflette l'implementazione più da vicino.

Guarda la documentazione MSDN per ciascuno di essi ( SortedList , SortedDictionary ) per dettagli delle prestazioni per le diverse operazioni in diverse situazioni specifiche. Ecco un bel riassunto (dalla documentazione SortedDictionary):

  

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 al   SortedList<TKey, TValue> generici   classe. Le due classi hanno simile   opporsi modelli, ed entrambi hanno O (log n)   recupero. Dove le due classi   differiscono è in uso la memoria e la velocità di   inserimento e rimozione:

     

  

• SortedList<TKey, TValue> consuma meno   memoria rispetto SortedDictionary<TKey, TValue>.

  

• SortedDictionary<TKey, TValue> ha   veloce inserimento 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   da dati ordinati, SortedList<TKey, TValue> è più veloce di   SortedDictionary<TKey, TValue>.

  

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

Answer 2

Ecco una vista tabellare se aiuta ...

Da un prestazioni prospettiva:

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

Per circa parafrasare, se si richiedono prestazioni SortedDictionary grezzo potrebbe essere una scelta migliore. Se avete bisogno di minor sovraccarico della memoria e indicizzati SortedList recupero si adatta meglio. Vedere questa domanda per maggiori informazioni su quando usare quale.

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

Answer 3

Ho aperto il Riflettore di avere uno sguardo a questo come vi sembra di essere un po ' di confusione circa SortedList.Esso, infatti, non è un albero di ricerca binaria, si tratta di un ordinato (con chiave) array di coppie chiave-valore.C'è anche un TKey[] keys variabile che viene ordinata in sincronia con le coppie chiave-valore e utilizzato per la ricerca binaria.

Ecco qualche fonte (targeting .NET 4.5) per il backup delle mie affermazioni.

I 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.Aggiungere(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

Controlla la pagina MSDN per SortedList :

Da sezione Osservazioni:

  

La classe generica SortedList<(Of <(TKey, TValue>)>) è un albero binario di ricerca con O(log n) recupero, 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 recupero 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 rispetto SortedDictionary<(Of <(TKey, TValue>)>).
  

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

  

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

  

Answer 5

Questa è la rappresentazione visiva di come prestazioni confrontano gli uni agli altri.

Answer 6

Basta è detto già sul tema, ma di mantenerlo semplice, ecco il mio prendere.

dizionario Ordinato deve essere utilizzato quando -

sono tenuti
• Più inserti e le operazioni di eliminazione.
• Dati a un-ordinato.
• Chiave di accesso è sufficiente e l'accesso indice non è richiesto.
• La memoria non è un collo di bottiglia.

D'altra parte, Ordinati List deve essere utilizzato quando -

• Ulteriori ricerche e meno inserti e cancellazione sono richieste operazioni.
• I dati vengono già ordinato (se non tutti, la maggior parte).
• è richiesto l'accesso indice.
• La memoria è un overhead.

Spero che questo aiuti !!

Answer 7

accesso Index (citato qui) è la differenza pratica. Se è necessario accedere al successore o precedente, è necessario SortedList. SortedDictionary non può fare che così si è piuttosto limitato con come è possibile utilizzare l'ordinamento (prima / foreach).