Qu’est-ce qui est le plus efficace: Dictionary TryGetValue ou ContainsKey + Item?

De l’entrée MSDN sur Dictionary.TryGetValue, méthode :

Cette méthode combine les fonctionnalités de la méthode ContainsKey et de la propriété Item.

Si la clé est introuvable, le paramètre value obtient la valeur par défaut appropriée pour le type de valeur TValue; par exemple, 0 (zéro) pour les types entiers, faux pour les types booléens et null pour les types de référence.

Utilisez la méthode TryGetValue si votre code tente fréquemment d’accéder aux clés qui ne figurent pas dans le dictionnaire. L’utilisation de cette méthode est plus efficace que la capture de KeyNotFoundException lancée par la propriété Item.

Cette méthode approche une opération O (1).

D’après la description, il n’est pas clair si c’est plus efficace ou juste plus pratique que d’appeler ContainsKey et de faire la recherche. L’implémentation de TryGetValue appelle-t- TryGetValue simplement ContainsKey et ensuite Item ou est-elle réellement plus efficace que cela en effectuant une seule recherche?

En d’autres termes, qu’est-ce qui est le plus efficace (c’est-à-dire qui effectue moins de recherches):

 Dictionary dict; //...// int ival; if(dict.ContainsKey(ikey)) { ival = dict[ikey]; } else { ival = default(int); } 

ou

 Dictionary dict; //...// int ival; dict.TryGetValue(ikey, out ival); 

Note: Je ne cherche pas un benchmark!

TryGetValue sera plus rapide.

ContainsKey utilise la même vérification que TryGetValue , qui fait référence en interne à l’emplacement d’entrée réel. La propriété Item a en fait une fonctionnalité de code presque identique à celle de TryGetValue , sauf qu’elle lancera une exception au lieu de retourner false.

L’utilisation de ContainsKey suivie de l’élément, duplique essentiellement la fonctionnalité de recherche, qui constitue l’essentiel du calcul dans ce cas.

Un TryGetValue rapide montre que TryGetValue a un léger avantage:

  static void Main() { var d = new Dictionary {{"a", "b"}}; var start = DateTime.Now; for (int i = 0; i != 10000000; i++) { ssortingng x; if (!d.TryGetValue("a", out x)) throw new ApplicationException("Oops"); if (d.TryGetValue("b", out x)) throw new ApplicationException("Oops"); } Console.WriteLine(DateTime.Now-start); start = DateTime.Now; for (int i = 0; i != 10000000; i++) { ssortingng x; if (d.ContainsKey("a")) { x = d["a"]; } else { x = default(ssortingng); } if (d.ContainsKey("b")) { x = d["b"]; } else { x = default(ssortingng); } } } 

Cela produit

 00:00:00.7600000 00:00:01.0610000 

rendre l’access à ContainsKey + Item plus lent d’environ 40% en supposant un mélange homogène de hits et de misses.

De plus, lorsque je change le programme pour toujours manquer (c’est-à-dire toujours rechercher "b" ), les deux versions deviennent tout aussi rapides:

 00:00:00.2850000 00:00:00.2720000 

Quand je le fais “tous les hits”, le TryGetValue rest un gagnant clair:

 00:00:00.4930000 00:00:00.8110000 

Comme aucune des réponses ne répond à la question, voici une réponse acceptable que j’ai trouvée après quelques recherches:

Si vous décomstackz TryGetValue, vous voyez que c’est ce que vous faites:

 public bool TryGetValue(TKey key, out TValue value) { int index = this.FindEntry(key); if (index >= 0) { value = this.ensortinges[index].value; return true; } value = default(TValue); return false; } 

alors que la méthode ContainsKey est:

 public bool ContainsKey(TKey key) { return (this.FindEntry(key) >= 0); } 

donc TryGetValue est juste ContainsKey plus une recherche de tableau si l’élément est présent.

La source

Il semble que TryGetValue soit presque deux fois plus rapide que la combinaison ContainsKey + Item.

On s’en fout 🙂

Vous demandez probablement parce que TryGetValue est difficile à utiliser – alors encapsulez-le comme cela avec une méthode d’extension.

 public static class CollectionUtils { // my original method // public static V GetValueOrDefault(this Dictionary dic, K key) // { // V ret; // bool found = dic.TryGetValue(key, out ret); // if (found) // { // return ret; // } // return default(V); // } // EDIT: one of many possible improved versions public static TValue GetValueOrDefault(this IDictionary dictionary, K key) { // initialized to default value (such as 0 or null depending upon type of TValue) TValue value; // attempt to get the value of the key from the dictionary dictionary.TryGetValue(key, out value); return value; } 

Alors appelez simplement:

 dict.GetValueOrDefault("keyname") 

ou

 (dict.GetValueOrDefault("keyname") ?? fallbackValue) 

Pourquoi ne pas le tester?

Mais je suis presque sûr que TryGetValue est plus rapide, car il ne fait qu’une recherche. Bien sûr, cela n’est pas garanti, c’est-à-dire que différentes implémentations peuvent avoir des caractéristiques de performances différentes.

La façon dont j’implémenterais un dictionnaire consiste à créer une fonction interne de Find qui trouve l’emplacement pour un élément, puis à construire le rest en plus.

Toutes les réponses, même si elles sont bonnes, manquent un point essentiel.

Les méthodes dans les classes d’une API (par exemple, le framework .NET) font partie d’une définition d’interface (pas une interface C # ou VB, mais une interface dans le sens de l’informatique).

En tant que tel, il est généralement incorrect de demander si l’appel d’une telle méthode est plus rapide, à moins que la vitesse fasse partie de la définition de l’interface formelle (ce qui n’est pas le cas dans ce cas).

Traditionnellement, ce type de raccourci (combinant recherche et récupération) est plus efficace indépendamment de la langue, de l’infrastructure, du système d’exploitation, de la plate-forme ou de l’architecture de la machine. Il est également plus lisible, car il exprime explicitement votre intention plutôt que de l’impliquer (à partir de la structure de votre code).

Donc, la réponse (d’un vieux hack grisonnant) est définitivement “Yes” (TryGetValue est préférable à une combinaison de ContainsKey et Item [Get] pour récupérer une valeur dans un Dictionnaire).

Si vous pensez que cela semble étrange, pensez à ceci: Même si les implémentations actuelles de TryGetValue, ContainsKey et Item [Get] ne génèrent aucune différence de vitesse, vous pouvez supposer qu’une future implémentation (par exemple .NET v5) fera (TryGetValue sera plus rapide). Pensez à la durée de vie de votre logiciel.

En passant, il est intéressant de noter que les technologies de définition d’interfaces modernes typiques offrent rarement des moyens de définir formellement les contraintes temporelles. Peut-être .NET v5?

Faire un programme de test rapide, il y a définitivement une amélioration en utilisant TryGetValue avec 1 million d’éléments dans un dictionnaire.

Résultats:

ContainsKey + Item pour 1000000 hits: 45ms

TryGetValue pour 1000000 hits: 26ms

Voici l’application de test:

 static void Main(ssortingng[] args) { const int size = 1000000; var dict = new Dictionary(); for (int i = 0; i < size; i++) { dict.Add(i, i.ToString()); } var sw = new Stopwatch(); string result; sw.Start(); for (int i = 0; i < size; i++) { if (dict.ContainsKey(i)) result = dict[i]; } sw.Stop(); Console.WriteLine("ContainsKey + Item for {0} hits: {1}ms", size, sw.ElapsedMilliseconds); sw.Reset(); sw.Start(); for (int i = 0; i < size; i++) { dict.TryGetValue(i, out result); } sw.Stop(); Console.WriteLine("TryGetValue for {0} hits: {1}ms", size, sw.ElapsedMilliseconds); } 

Sur ma machine, avec des charges de RAM, lorsqu’il est exécuté en mode RELEASE (pas DEBUG), ContainsKey est égal à TryGetValue / try-catch si toutes les entrées du Dictionary<> sont trouvées.

ContainsKey surpasse tous de loin quand il n’y a que quelques entrées de dictionnaire non trouvées (dans mon exemple ci-dessous, définissez MAXVAL sur n’importe quelle taille supérieure à ENTRIES pour avoir des entrées manquées):

Résultats:

 Finished evaluation .... Time dissortingbution: Size: 000010: TryGetValue: 53,24%, ContainsKey: 1,74%, try-catch: 45,01% - Total: 2.006,00 Size: 000020: TryGetValue: 37,66%, ContainsKey: 0,53%, try-catch: 61,81% - Total: 2.443,00 Size: 000040: TryGetValue: 22,02%, ContainsKey: 0,73%, try-catch: 77,25% - Total: 7.147,00 Size: 000080: TryGetValue: 31,46%, ContainsKey: 0,42%, try-catch: 68,12% - Total: 17.793,00 Size: 000160: TryGetValue: 33,66%, ContainsKey: 0,37%, try-catch: 65,97% - Total: 36.840,00 Size: 000320: TryGetValue: 34,53%, ContainsKey: 0,39%, try-catch: 65,09% - Total: 71.059,00 Size: 000640: TryGetValue: 32,91%, ContainsKey: 0,32%, try-catch: 66,77% - Total: 141.789,00 Size: 001280: TryGetValue: 39,02%, ContainsKey: 0,35%, try-catch: 60,64% - Total: 244.657,00 Size: 002560: TryGetValue: 35,48%, ContainsKey: 0,19%, try-catch: 64,33% - Total: 420.121,00 Size: 005120: TryGetValue: 43,41%, ContainsKey: 0,24%, try-catch: 56,34% - Total: 625.969,00 Size: 010240: TryGetValue: 29,64%, ContainsKey: 0,61%, try-catch: 69,75% - Total: 1.197.242,00 Size: 020480: TryGetValue: 35,14%, ContainsKey: 0,53%, try-catch: 64,33% - Total: 2.405.821,00 Size: 040960: TryGetValue: 37,28%, ContainsKey: 0,24%, try-catch: 62,48% - Total: 4.200.839,00 Size: 081920: TryGetValue: 29,68%, ContainsKey: 0,54%, try-catch: 69,77% - Total: 8.980.230,00 

Voici mon code:

  using System; using System.Collections.Generic; using System.Diagnostics; namespace ConsoleApplication1 { class Program { static void Main(ssortingng[] args) { const int ENTRIES = 10000, MAXVAL = 15000, TRIALS = 100000, MULTIPLIER = 2; Dictionary values = new Dictionary(); Random r = new Random(); int[] lookups = new int[TRIALS]; int val; List> durations = new List>(8); for (int i = 0;i < ENTRIES;++i) try { values.Add(r.Next(MAXVAL), r.Next()); } catch { --i; } for (int i = 0;i < TRIALS;++i) lookups[i] = r.Next(MAXVAL); Stopwatch sw = new Stopwatch(); ConsoleColor bu = Console.ForegroundColor; for (int size = 10;size <= TRIALS;size *= MULTIPLIER) { long a, b, c; Console.ForegroundColor = ConsoleColor.Yellow; Console.WriteLine("Loop size: {0}", size); Console.ForegroundColor = bu; // --------------------------------------------------------------------- sw.Start(); for (int i = 0;i < size;++i) values.TryGetValue(lookups[i], out val); sw.Stop(); Console.WriteLine("TryGetValue: {0}", a = sw.ElapsedTicks); // --------------------------------------------------------------------- sw.Restart(); for (int i = 0;i < size;++i) val = values.ContainsKey(lookups[i]) ? values[lookups[i]] : default(int); sw.Stop(); Console.WriteLine("ContainsKey: {0}", b = sw.ElapsedTicks); // --------------------------------------------------------------------- sw.Restart(); for (int i = 0;i < size;++i) try { val = values[lookups[i]]; } catch { } sw.Stop(); Console.WriteLine("try-catch: {0}", c = sw.ElapsedTicks); // --------------------------------------------------------------------- Console.WriteLine(); durations.Add(new Tuple(a, b, c)); } Console.ForegroundColor = ConsoleColor.Yellow; Console.WriteLine("Finished evaluation .... Time dissortingbution:"); Console.ForegroundColor = bu; val = 10; foreach (Tuple d in durations) { long sum = d.Item1 + d.Item2 + d.Item3; Console.WriteLine("Size: {0:D6}:", val); Console.WriteLine("TryGetValue: {0:P2}, ContainsKey: {1:P2}, try-catch: {2:P2} - Total: {3:N}", (decimal)d.Item1 / sum, (decimal)d.Item2 / sum, (decimal)d.Item3 / sum, sum); val *= MULTIPLIER; } Console.WriteLine(); } } } 

Si vous essayez d’extraire la valeur du dictionnaire, TryGetValue (clé, valeur de sortie) est la meilleure option, mais si vous vérifiez la présence de la clé, pour une nouvelle insertion, sans remplacer les anciennes clés, et seulement avec cette scope, ContainsKey (key) est la meilleure option, le benchmark peut le confirmer:

 using System; using System.Threading; using System.Diagnostics; using System.Collections.Generic; using System.Collections; namespace benchmark { class Program { public static Random m_Rand = new Random(); public static Dictionary testdict = new Dictionary(); public static Hashtable testhash = new Hashtable(); public static void Main(ssortingng[] args) { Console.WriteLine("Adding elements into hashtable..."); Stopwatch watch = Stopwatch.StartNew(); for(int i=0; i<1000000; i++) testhash[i]=m_Rand.Next(); watch.Stop(); Console.WriteLine("Done in {0:F4} -- pause....", watch.Elapsed.TotalSeconds); Thread.Sleep(4000); Console.WriteLine("Adding elements into dictionary..."); watch = Stopwatch.StartNew(); for(int i=0; i<1000000; i++) testdict[i]=m_Rand.Next(); watch.Stop(); Console.WriteLine("Done in {0:F4} -- pause....", watch.Elapsed.TotalSeconds); Thread.Sleep(4000); Console.WriteLine("Finding the first free number for insertion"); Console.WriteLine("First method: ContainsKey"); watch = Stopwatch.StartNew(); int intero=0; while (testdict.ContainsKey(intero)) { intero++; } testdict.Add(intero, m_Rand.Next()); watch.Stop(); Console.WriteLine("Done in {0:F4} -- added value {1} in dictionary -- pause....", watch.Elapsed.TotalSeconds, intero); Thread.Sleep(4000); Console.WriteLine("Second method: TryGetValue"); watch = Stopwatch.StartNew(); intero=0; int result=0; while(testdict.TryGetValue(intero, out result)) { intero++; } testdict.Add(intero, m_Rand.Next()); watch.Stop(); Console.WriteLine("Done in {0:F4} -- added value {1} in dictionary -- pause....", watch.Elapsed.TotalSeconds, intero); Thread.Sleep(4000); Console.WriteLine("Test hashtable"); watch = Stopwatch.StartNew(); intero=0; while(testhash.Contains(intero)) { intero++; } testhash.Add(intero, m_Rand.Next()); watch.Stop(); Console.WriteLine("Done in {0:F4} -- added value {1} into hashtable -- pause....", watch.Elapsed.TotalSeconds, intero); Console.Write("Press any key to continue . . . "); Console.ReadKey(true); } } } 

C'est un vrai exemple, j'ai un service qui, pour chaque "Article" créé, associe un numéro progressif, ce numéro, chaque fois que vous créez un nouvel article, doit être trouvé gratuitement, si vous supprimez un Article, le numéro gratuit devient gratuit, bien sûr, ce n'est pas optimisé, car j'ai un var statique qui met en cache le numéro actuel, mais si vous terminez tous les nombres, vous pouvez recommencer de 0 à UInt32.MaxValue

Test exécuté:
Ajouter des éléments dans la table de hachage ...
Fait à 0,5908 - pause ....
Ajouter des éléments dans un dictionnaire ...
Fait en 0,2679 - pause ....
Trouver le premier numéro gratuit pour l'insertion
Première méthode: ContainsKey
Fait en 0,0561 - valeur ajoutée 1000000 dans le dictionnaire - pause ....
Deuxième méthode: TryGetValue
Fait à 0,0643 - valeur ajoutée 1000001 dans le dictionnaire - pause ....
Test de la hashtable
Fait en 0,3015 - valeur ajoutée 1000000 dans la hashtable - pause ....
Appuyez sur n'importe quelle touche pour continuer . .

Si certains d’entre vous demandent si le ContainsKeys pourrait avoir un avantage, j’ai même essayé d’inverser le paramètre TryGetValue avec la clé Contains, le résultat est le même.

Donc, pour moi, avec une dernière considération, tout dépend de la façon dont le programme se comporte.

Outre la conception d’un microbenchmark qui donnera des résultats précis dans un paramètre pratique, vous pouvez inspecter la source de référence de .NET Framework.

  • System.Collections.Generic.Dictionary.TryGetValue(TKey, out TValue)
  • System.Collections.Generic.Dictionary.ContainsKey(TKey)
  • System.Collections.Generic.Dictionary.Item(TKey)

Ils appellent tous la FindEntry(TKey) qui effectue la majeure partie du travail et ne mémorisent pas son résultat. Par conséquent, appeler TryGetValue est presque deux fois plus rapide que ContainsKey + Item .


L’interface peu pratique de TryGetValue peut être adaptée en utilisant une méthode d’extension :

 using System.Collections.Generic; namespace Project.Common.Extensions { public static class DictionaryExtensions { public static TValue GetValueOrDefault( this IDictionary dictionary, TKey key, TValue defaultValue = default(TValue)) { if (dictionary.TryGetValue(key, out TValue value)) { return value; } return defaultValue; } } } 

Depuis C # 7.1, vous pouvez remplacer la default(TValue) par default . Le type est inféré.

Usage:

 var dict = new Dictionary(); ssortingng val = dict.GetValueOrDefault("theKey", "value used if theKey is not found in dict"); 

Il renvoie null pour les types de référence dont la recherche échoue, sauf si une valeur par défaut explicite est spécifiée.

 var dictObj = new Dictionary(); object valObj = dictObj.GetValueOrDefault("nonexistent"); Debug.Assert(valObj == null); val dictInt = new Dictionary(); int valInt = dictInt.GetValueOrDefault("nonexistent"); Debug.Assert(valInt == 0);