Quelle est la différence entre SortedList et SortedDictionary?

261

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

Shaul Behr
la source
13
Je suis confus. Pourquoi SortedList a-t-il deux paramètres de type SortedList<TKey,TValue>plutôt qu'un SortedList<T>? Pourquoi ne met-il pas en œuvre IList<T>?
Colonel Panic
3
@ColonelPanic car Functionally SortedList est une carte, pas une collection linéaire. Ne laissez pas le nom vous tromper. Tout comme un dictionnaire, vous passez une clé, vous récupérez une valeur. Bien que le dictionnaire ne soit pas ordonné, SortedList est ordonné dans son ordre de tri naturel.
nawfal le

Réponses:

294

Oui - leurs performances diffèrent considérablement. Il serait probablement préférable de les appeler SortedListet SortedTreecela reflète la mise en œuvre de plus près.

Consultez les documents MSDN pour chacun d'eux ( SortedList, SortedDictionary) pour plus de détails sur les performances de différentes opérations dans différentes situations. Voici un joli résumé (à partir des SortedDictionarydocuments):

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

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

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

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

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

Jon Skeet
la source
Merci beaucoup à tous pour les pointeurs. Je suppose que je suis juste trop paresseux pour RTFM ... beaucoup plus facile de demander aux gens sympas sur SO ...;) Je vous ai voté tous les deux pour les réponses; Jon obtient un crédit de réponse pour avoir été le premier sur la détente. :)
Shaul Behr
2
Je pense que la définition de SortedList devrait être corrigée car je ne crois pas que ce soit un arbre de recherche binaire ...?
nchaud
1
J'ai regardé en utilisant le réflecteur et j'ai découvert qu'il n'utilisait pas d'arbre de recherche binaire.
Daniel Imms
Je pense que le Sorteddictionary est un arbre AVL ou Red-Blacktree (toutes les opérations coûtent O (logn). Et le SortedList est une recherche binaire (cela coûte o (n) temps dans le pire des cas) l
Ghoster
105

Voici une vue tabulaire si cela peut vous aider ...

Du point de vue des performances :

+------------------+---------+----------+--------+----------+----------+---------+
| 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 point de 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 paraphraser grossièrement , si vous avez besoin de performances brutes, cela SortedDictionarypourrait être un meilleur choix. Si vous avez besoin d'une surcharge de mémoire moindre et que la récupération indexée SortedListconvient mieux. Consultez cette question pour en savoir plus sur le moment de l'utiliser.

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

nawfal
la source
Notez que si vous voulez de bonnes performances et une utilisation de mémoire relativement faible et une récupération indexée, pensez BDictionary<Key,Value>à LoycCore au lieu de SortedDictionary.
Qwertie
1
Oui, regardez la partie inférieure de cet article . Il s'avère BDictionarygénéralement plus lent que SortedDictionarypour les très grandes tailles, mais il est plus rapide que SortedLists'il y a plus de 700 articles. L'utilisation de la mémoire ne devrait être que légèrement supérieure à SortedList(très inférieure à SortedDictionary), en raison de l'utilisation de tableaux dans les feuilles de l'arbre.
Qwertie
22

J'ai ouvert le réflecteur pour y jeter un œil, car il semble y avoir un peu de confusion SortedList. Ce n'est en fait pas un arbre de recherche binaire, c'est un tableau trié (par clé) de paires clé-valeur . Il existe également une TKey[] keysvariable qui est triée en synchronisation avec les paires clé-valeur et utilisée pour la recherche binaire.

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<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++;
}
Daniel Imms
la source
13

Consultez la page MSDN pour SortedList :

De la section Remarques:

La SortedList<(Of <(TKey, TValue>)>)classe générique est un arbre de recherche binaire avec O(log n)récupération, où nest le nombre d'éléments dans le dictionnaire. En cela, elle est similaire à la SortedDictionary<(Of <(TKey, TValue>)>)classe générique. Les deux classes ont des modèles d'objets similaires et les deux ont une O(log n)récupération. La différence entre les deux classes réside dans l'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 des opérations d'insertion et de suppression plus rapides pour les données non triées, O(log n)par opposition à O(n)pour SortedList<(Of <(TKey, TValue>)>).

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

Stephan
la source
9
Le texte cité est incorrect (et a été mis à jour sur MSDN): SortedList n'est pas un "arbre de recherche binaire", c'est un "tableau de paires clé / valeur".
Eldritch Conundrum
12

Il s'agit d'une représentation visuelle de la façon dont les performances se comparent.

Lev
la source
D'où avez-vous pris cette information? De ce schéma, nous pouvons voir que Dictinary est meilleur de quelque façon que ce soit, il n'y a donc aucune raison pour que d'autres existent.
alex kostin
9

On en dit déjà assez sur le sujet, mais pour faire simple, voici mon point de vue.

Un dictionnaire trié doit être utilisé lorsque

  • D'autres opérations d'insertion et de suppression sont nécessaires.
  • Données non commandées.
  • L'accès aux clés est suffisant et l'accès aux index n'est pas requis.
  • La mémoire n'est pas un goulot d'étranglement.

De l'autre côté, la liste trié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à triées (sinon toutes, la plupart).
  • L'accès à l'index est requis.
  • La mémoire est une surcharge.

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

Prakash Tripathi
la source
1

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

Gars
la source