Quelle est la différence entre SortedList et SortedDictionary?

Question

Y at-il une réelle différence pratique entre un SortedList<TKey,TValue> et SortedDictionary<TKey,TValue> ? Y a-t-il des circonstances où vous spécifiquement l'une et pas l'autre?

Answer 1

Oui - leurs caractéristiques de performance diffèrent sensiblement. Il serait sans doute préférable de les appeler SortedList et SortedTree comme qui reflète la mise en œuvre de plus près.

Regardez les docs MSDN pour chacun d'entre eux ( SortedList , SortedDictionary ) pour plus de détails sur les performances des différentes opérations dans différentes situtations. Voici un résumé agréable (des docs SortedDictionary):

  

Le SortedDictionary<TKey, TValue> générique   classe est un arbre de recherche binaire avec   O récupération (log n), où n est le   nombre d'éléments dans le dictionnaire.   En cela, il est similaire à la   SortedList<TKey, TValue> générique   classe. Les deux classes ont la même   objet modèles, et les deux ont O (log n)   récupération. Lorsque les deux classes   différer est en cours d'utilisation de la mémoire et de la vitesse de   insertion et le retrait:

     

  

• SortedList<TKey, TValue> utilise moins   La mémoire de SortedDictionary<TKey, TValue>.

  

• SortedDictionary<TKey, TValue> a   plus rapide insertion et le retrait   opérations de données non triés, O (log n)   par opposition à O (n) pour   SortedList<TKey, TValue>.

  

• Si la liste est peuplée à la fois   à partir des données triées, SortedList<TKey, TValue> est plus rapide que   SortedDictionary<TKey, TValue>.

  

(SortedList maintient en fait un tableau trié, plutôt que d'utiliser un arbre. Il utilise encore la recherche binaire pour trouver des éléments.)

Answer 2

Voici une vue tabulaire si elle aide ...

D'un performances perspective:

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

D'un mise en œuvre perspective:

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

à peu près paraphraser, si vous avez besoin SortedDictionary de performances brutes pourrait être un meilleur choix. Si vous avez besoin moindre frais généraux de mémoire et de récupération SortedList indexée est mieux adaptée. Voir cette question pour plus quand utiliser qui.

Vous pouvez en savoir plus ici , , ici , ici et ici .

Answer 3

Je craqué ouvert réflecteur pour jeter un oeil à ce que il semble y avoir un peu de confusion au sujet SortedList. Il est en fait pas un arbre de recherche binaire, est un tableau trié (par clé) de paires clé-valeur . Il y a aussi une variable TKey[] keys qui est triée en phase avec les paires clé-valeur et utilisée pour la recherche binaire.

Voici une source (cible 4.5 .NET) pour sauvegarder mes demandes.

membres privés

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

Consultez la la page MSDN pour SortedList :

De section Remarques:

  

La classe générique SortedList<(Of <(TKey, TValue>)>) est un arbre de recherche binaire avec la récupération de O(log n), où n est le nombre d'éléments dans le dictionnaire. En cela, il est similaire à la classe générique SortedDictionary<(Of <(TKey, TValue>)>). Les deux classes ont des modèles d'objets similaires, et les deux ont la récupération de O(log n). Lorsque les deux classes diffèrent est en cours d'utilisation de la mémoire et la vitesse d'insertion et de retrait:

     

  
• SortedList<(Of <(TKey, TValue>)>) utilise moins de mémoire que SortedDictionary<(Of <(TKey, TValue>)>).
  

• SortedDictionary<(Of <(TKey, TValue>)>) a plus rapides les opérations d'insertion et de suppression de données non triées, O(log n) par opposition à O(n) pour SortedList<(Of <(TKey, TValue>)>).

  

• Si la liste est peuplée à la fois des données triées, SortedList<(Of <(TKey, TValue>)>) est plus rapide que SortedDictionary<(Of <(TKey, TValue>)>).

  

Answer 5

Ceci est une représentation visuelle de la façon dont les performances se comparent les uns aux autres.

Answer 6

Assez dit déjà sur le sujet, mais pour le garder simple, voici mon.

dictionnaire Triés doit être utilisé lorsque -

• Plus d'insertions et des suppressions sont nécessaires.
• données dans un ordonnée.
• clé d'accès est suffisant et accès à l'index n'est pas nécessaire.
• mémoire n'est pas un goulot d'étranglement.

De l'autre côté, Liste triée doit être utilisé lorsque -

• Plus et moins inserts recherches et de suppression sont nécessaires.
• Les données sont déjà triées (sinon la totalité, la plupart).
• accès à l'index est nécessaire.
• La mémoire est une surcharge.

Hope this helps !!

Answer 7

accès à l'index (mentionné ici) est la différence pratique. Si vous avez besoin pour accéder au successeur ou prédécesseur, vous avez besoin SortedList. SortedDictionary ne peut le faire que si vous êtes assez limité avec la façon dont vous pouvez utiliser le tri (premier / foreach).