Quelle est la différence entre SortedList et SortedDictionary?

Question

Peut-être une question stupide, mais y a-t-il une différence pratique entre un et un ? Existe-t-il des circonstances où vous utiliseriez spécifiquement un et pas l’autre ?

Answer 1

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

Regardez la MSDN docs pour chacun d'eux (SortedList, SortedDictionary) pour les détails de la réalisation des différentes opérations dans vos milieux de vie différents. Voici un bon résumé (de l' SortedDictionary docs):

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

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

• SortedDictionary<TKey, TValue>a plus vite l'insertion et le retrait opérations pour des données non triées, O(log n) contrairement à O(n) pour SortedList<TKey, TValue>.

• Si la liste est remplie tout à la fois à partir de données triées, SortedList<TKey, TValue> est plus rapide que SortedDictionary<TKey, TValue>.

(SortedList maintient actuellement un tableau trié, plutôt que d'utiliser un arbre. Il utilise toujours les binaires de recherche pour trouver les éléments.

Answer 2

Voici une vue tabulaire si ça aide...

À partir d'une performance de point de vue:

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

De la mise en œuvre de la 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 de performances brutes SortedDictionary pourrait être un meilleur choix. Si vous avez besoin d'moindre surcharge de la mémoire et de récupération indexée SortedList convient le mieux. Voir cette question pour en savoir plus sur quand utiliser.

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

Answer 3

J'ai craqué ouvrir un Réflecteur pour avoir un coup d'oeil à ce qu'il semble y avoir un peu de confusion à propos de SortedList. Il est en fait pas un arbre de recherche binaire, c'est un triée (par clé) tableau de paires clé-valeur. Il y a aussi un TKey[] keys variable qui est triée en synchronisation avec les paires clé-valeur et utilisé pour la recherche binaire.

Certains, ici source (ciblage .NET 4.5) pour sauvegarder mes revendications.

Les 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.Ajouter(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

Découvrez la page MSDN pour SortedList:

Des commentaires de l'article:

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

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

• SortedDictionary<(Of <(TKey, TValue>)>) a plus rapide de l'insertion et de la suppression des opérations pour des données non triées, O(log n) plutôt O(n) pour SortedList<(Of <(TKey, TValue>)>).

• Si la liste est remplie tout à la fois à partir des données triées, SortedList<(Of <(TKey, TValue>)>) plus rapide que de l' SortedDictionary<(Of <(TKey, TValue>)>).

Answer 5

Il s’agit d’une représentation visuelle des spectacles comparent les uns aux autres.