Quelle est la différence entre SortedList et SortedDictionary?

Y a-t-il une différence réelle entre une SortedList et un SortedDictionary ? Y a-t-il des circonstances dans lesquelles vous utiliseriez spécifiquement l’une et pas l’autre?

    Oui, leurs performances sont très différentes. Il serait probablement préférable de les appeler SortedList et SortedTree car cela reflète plus étroitement l’implémentation.

    Regardez les documents MSDN pour chacun d’eux ( SortedList , SortedDictionary ) pour plus de détails sur les performances des différentes opérations dans différentes situations. Voici un bon résumé (de la documentation de SortedDictionary ):

    La classe générique SortedDictionary est un arbre de recherche binary avec récupération O (log n), où n est le nombre d’éléments du dictionnaire. En cela, il est similaire à la classe générique SortedList . Les deux classes ont des modèles d’object similaires, et les deux ont une récupération O (log n). Lorsque les deux classes diffèrent, l’utilisation de la mémoire et la vitesse d’insertion et de retrait sont les suivantes:

    • SortedList utilise moins de mémoire que SortedDictionary .

    • SortedDictionary a des opérations d’insertion et de suppression plus rapides pour les données non sortingées, O (log n) par opposition à O (n) pour SortedList .

    • Si la liste est remplie à la fois par des données sortingées, SortedList est plus rapide que SortedDictionary .

    ( SortedList maintient en fait un tableau sortingé, plutôt que d’utiliser un arbre. Il utilise toujours la recherche binary pour trouver des éléments.)

    Voici une vue tabulaire si cela aide …

    Du sharepoint vue de la performance :

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

    Du sharepoint vue de la mise en œuvre :

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

    Pour résumer, si vous avez besoin d’une performance brute, SortedDictionary pourrait être un meilleur choix. Si vous avez besoin d’une mémoire plus SortedList et d’une récupération indexée, SortedList s’adapte mieux. Voir cette question pour plus d’informations sur quand utiliser qui.

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

    J’ai craqué en ouvrant Reflector pour regarder cela car il semble y avoir un peu de confusion sur SortedList . Il ne s’agit en fait pas d’un arbre de recherche binary, c’est un tableau sortingé (par clé) de paires clé-valeur . Il existe également une variable de TKey[] keys qui est sortingée en synchronisation avec les paires clé-valeur et utilisée pour la recherche binary.

    Voici une source (ciblant .NET 4.5) pour sauvegarder mes revendications.

    Membres privés

     // Fields private const int _defaultCapacity = 4; private int _size; [NonSerialized] private object _syncRoot; private IComparer comparer; private static TKey[] emptyKeys; private static TValue[] emptyValues; private KeyList keyList; private TKey[] keys; private const int MaxArrayLength = 0x7fefffff; private ValueList valueList; private TValue[] values; private int version; 

    SortedList.ctor (IDictionary, IComparer)

     public SortedList(IDictionary dictionary, IComparer 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(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(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++; } 

    Consultez la page MSDN pour SortedList :

    De la section Remarques:

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

    • SortedList<(Of <(TKey, TValue>)>) utilise moins de mémoire que SortedDictionary<(Of <(TKey, TValue>)>) .
    • SortedDictionary<(Of <(TKey, TValue>)>) a des opérations d’insertion et de suppression plus rapides pour les données non sortingées, O(log n) par opposition à O(n) pour SortedList<(Of <(TKey, TValue>)>) .

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

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

    Assez est déjà dit sur le sujet, mais pour restr simple, voici ma prise.

    Le dictionnaire sortingé doit être utilisé lorsque-

    • Plus d’insertions et d’opérations de suppression sont nécessaires.
    • Données non commandées.
    • L’access aux clés est suffisant et l’access à l’index n’est pas requirejs.
    • La mémoire n’est pas un goulot d’étranglement.

    De l’autre côté, la liste sortingée doit être utilisée lorsque-

    • Plus de recherches et moins d’insertions et d’opérations de suppression sont nécessaires.
    • Les données sont déjà sortingées (sinon toutes, la plupart).
    • L’access à l’index est requirejs.
    • La mémoire est une surcharge.

    J’espère que cela t’aides!!

    L’access à l’index (mentionné ici) est la différence pratique. Si vous devez accéder au successeur ou au prédécesseur, vous devez disposer de SortedList. SortedDictionary ne peut pas faire cela, vous êtes donc assez limité dans la manière d’utiliser le sorting (first / foreach).