Différence entre Lookup () et Dictionary (Of list ())

165

J'essaie de comprendre quelles structures de données sont les plus efficaces et quand / où utiliser lesquelles.

Maintenant, il se peut que je ne comprends tout simplement pas assez bien les structures, mais en quoi est-ce ILookup(of key, ...)différent d'un Dictionary(of key, list(of ...))?

Aussi où voudrais-je utiliser un ILookupet où serait-il plus efficace en termes de vitesse du programme / mémoire / accès aux données, etc.?

John Bustos
la source
1
on peut aussi vouloir voir quel-est-le-point-de-lookuptkey-telement
nawfal

Réponses:

255

Deux différences significatives:

  • Lookupest immuable. Yay :) (Au moins, je crois que la Lookupclasse concrète est immuable, et l' ILookupinterface ne fournit aucun membre en mutation. Il pourrait y avoir d'autres implémentations mutables, bien sûr.)
  • Lorsque vous recherchez une clé qui n'est pas présente dans une recherche, vous récupérez une séquence vide au lieu d'un KeyNotFoundException. (Par conséquent, il n'y a pas TryGetValue, AFAICR.)

Ils sont susceptibles d'être équivalents en efficacité - la recherche peut très bien utiliser Dictionary<TKey, GroupingImplementation<TValue>>les coulisses, par exemple. Choisissez entre eux en fonction de vos besoins. Personnellement, je trouve que la recherche est généralement un meilleur ajustement que a Dictionary<TKey, List<TValue>>, principalement en raison des deux premiers points ci-dessus.

Notez qu'en tant que détail d'implémentation, l'implémentation concrète IGrouping<,>est utilisée pour les implémentations de valeurs IList<TValue>, ce qui signifie qu'il est efficace à utiliser avec Count(), ElementAt()etc.

Jon Skeet
la source
Si une recherche de clé inexistante entraîne une séquence vide plutôt qu'une exception, alors elle ne peut pas être utilisée comme une collection à usage général imo. C'est un peu correct dans le cas d'une collection immuable qui est un sous-produit des requêtes linq.
nawfal
@nawfal - c'est exactement ce à quoi servent les recherches. De msdn : "Vous pouvez créer une instance d'un Lookup <TKey, TElement> en appelant ToLookup sur un objet qui implémente IEnumerable <T>."
Niall Connaughton
50

Intéressant que personne n'ait mentionné la plus grande différence réelle (prise directement de MSDN ):

Une recherche ressemble à un dictionnaire. La différence est qu'un dictionnaire mappe des clés à des valeurs uniques, tandis qu'une recherche mappe des clés à des collections de valeurs.

Mladen Mihajlovic
la source
51
Vérifiez la question: il s'agit de la différence entre un Lookup <TKey, TValue> et un Dictionary <TKey, List <TValue>>, donc cette différence est déjà assez explicite.
Martao
5
@Martao certaines personnes trouvent cette question en cherchant sur Google pour comprendre la différence entre les recherches et les dictionnaires. Cette réponse est vraiment utile.
jakubiszon le
34

A Dictionary<Key, List<Value>>et a Lookup<Key, Value>logiquement peuvent contenir des données organisées de manière similaire et les deux sont du même ordre d'efficacité. La principale différence est que Lookupc'est immuable: il n'a pas de Add()méthodes et pas de constructeur public (et comme Jon l'a mentionné, vous pouvez interroger une clé inexistante sans exception et avoir la clé dans le cadre du regroupement).

Quant à savoir lequel utilisez-vous, cela dépend vraiment de la façon dont vous souhaitez les utiliser. Si vous maintenez une carte de clés vers plusieurs valeurs qui est constamment modifiée, alors a Dictionary<Key, List<Value>>est probablement mieux car il est mutable.

Si, cependant, vous avez une séquence de données et que vous voulez juste une vue en lecture seule des données organisées par clé, une recherche est très facile à construire et vous donnera un instantané en lecture seule.

James Michael Hare
la source
11

La principale différence entre un ILookup<K,V>et un Dictionary<K, List<V>>est qu'un dictionnaire est modifiable; vous pouvez ajouter ou supprimer des clés, et également ajouter ou supprimer des éléments de la liste recherchée. Un ILookupest immuable et ne peut pas être modifié une fois créé.

L'implémentation sous-jacente des deux mécanismes sera identique ou similaire, de sorte que leur vitesse de recherche et leur empreinte mémoire seront approximativement les mêmes.

Servy
la source
1
@JohnBustos En termes de performances, non. C'est purement logique. Vous pouvez passer des références à la structure sans vous soucier que quelqu'un d'autre la modifie sous vous. Vous pouvez faire des hypothèses sur le fait qu'il est immuable que vous ne pourriez pas s'il était mutable.
Servy
Merci, Servy, c'est un très bon point lorsque vous passez souvent autant de variables ByRef - Au moins celle-ci, vous êtes sûr qu'elle ne peut pas être modifiée. Merci!
John Bustos
2
@JohnBustos Gardez à l'esprit que la méthode par défaut pour passer un paramètre de méthode est par valeur, vous devez ajouter explicitement byref, et c'est quelque chose qui devrait être fait assez rarement. Ces structures de données sont des classes, ce qui en fait des types de référence, donc la transmission de la valeur est la valeur de la référence, c'est pourquoi la transmettre à une autre méthode peut entraîner des modifications visibles pour l'appelant.
Servy
Merci, Servy, cela m'ouvre une toute nouvelle boîte de vers en termes de ce que j'ai fait :), mais je comprends ce que vous dites. Merci!!
John Bustos
Sous les couvertures, savez-vous si Lookup utilise des hashbuckets pour la clé?
paparazzo
10

Une autre différence non encore mentionnée est que Lookup () prend en charge les clés nulles :

La classe Lookup implémente l'interface ILookup. La recherche est très similaire à un dictionnaire, sauf que plusieurs valeurs sont autorisées à mapper sur la même clé et que les clés nulles sont prises en charge.

Noble_Bright_Life
la source
4

Lorsque l'exception n'est pas une option, optez pour la recherche

Si vous essayez d'obtenir une structure aussi efficace que a Dictionarymais que vous ne savez pas avec certitude qu'il n'y a pas de clé en double en entrée,Lookup c'est plus sûr.

Comme mentionné dans une autre réponse, il prend également en charge les clés nulles et renvoie toujours un résultat valide lorsqu'il est interrogé avec des données arbitraires, de sorte qu'il semble plus résilient aux entrées inconnues (moins enclin que Dictionary à déclencher des exceptions).

Et c'est particulièrement vrai si vous le comparez à la System.Linq.Enumerable.ToDictionaryfonction:

// won't throw
new[] { 1, 1 }.ToLookup(x => x); 

// System.ArgumentException: An item with the same key has already been added.
new[] { 1, 1 }.ToDictionary(x => x);

L'alternative serait d'écrire votre propre code de gestion de clé en double à l'intérieur d'une foreachboucle.

Considérations de performance, dictionnaire: un gagnant clair

Si vous n'avez pas besoin d'une liste et que vous allez gérer un grand nombre d'éléments Dictionary(ou même votre propre structure personnalisée), ce serait plus efficace:

        Stopwatch stopwatch = new Stopwatch();
        var list = new List<string>();
        for (int i = 0; i < 5000000; ++i)
        {
            list.Add(i.ToString());
        }
        stopwatch.Start();
        var lookup = list.ToLookup(x => x);
        stopwatch.Stop();
        Console.WriteLine("Creation: " + stopwatch.Elapsed);

        // ... Same but for ToDictionary
        var lookup = list.ToDictionary(x => x);
        // ...

Comme Lookupil faut maintenir une liste d'éléments pour chaque clé, il est plus lent que Dictionary (environ 3 fois plus lent pour un grand nombre d'éléments)

Vitesse de recherche: Création: 00: 00: 01.5760444

Vitesse du dictionnaire: Création: 00: 00: 00.4418833

Fabuleux
la source