Quoi de plus efficace: Dictionnaire TryGetValue ou ContainsKey + Item?

De l'entrée de MSDN sur la méthode Dictionary.TryGetValue :

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

Si la clé n'est pas trouvée, le paramètre de valeur obtient la valeur par défaut appropriée pour le type de valeur TValue; par exemple, 0 (zéro) pour les types entiers, false 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 à des clés qui ne figurent pas dans le dictionnaire. L'utilisation de cette méthode est plus efficace que la capture de l'exception KeyNotFoundException levé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 tout simplement plus pratique que d'appeler ContainsKey et de faire la recherche. La mise en œuvre deTryGetValue simplement appeler ContainsKey puis Item ou est en fait plus efficace que cela en faisant une seule recherche?

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

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

ou

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

Remarque: je ne recherche pas de référence!

TryGetValue sera plus rapide.

ContainsKeyutilise la même vérification que TryGetValue, qui se réfère en interne à l'emplacement d'entrée réel. La Itempropriété a en fait une fonctionnalité de code presque identique àTryGetValue , sauf qu'elle lèvera une exception au lieu de renvoyer false.

L'utilisation ContainsKeysuivie de la Itemduplique essentiellement la fonctionnalité de recherche, qui représente la majeure partie du calcul dans ce cas.

Un benchmark rapide montre qui TryGetValuea un léger avantage:

    static void Main() {
        var d = new Dictionary<string, string> {{"a", "b"}};
        var start = DateTime.Now;
        for (int i = 0; i != 10000000; i++) {
            string 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++) {
            string x;
            if (d.ContainsKey("a")) {
                x = d["a"];
            } else {
                x = default(string);
            }
            if (d.ContainsKey("b")) {
                x = d["b"];
            } else {
                x = default(string);
            }
        }
   }

Cela produit

00:00:00.7600000
00:00:01.0610000

rendant l' ContainsKey + Itemaccès environ 40% plus lent en supposant un mélange homogène de coups sûrs et manqués.

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

00:00:00.2850000
00:00:00.2720000

Quand je le fais "tous les hits", cependant, le TryGetValuereste clairement gagnant:

00:00:00.4930000
00:00:00.8110000

Puisqu'aucune des réponses jusqu'à présent ne répond à la question, voici une réponse acceptable que j'ai trouvée après quelques recherches:

Si vous décompilez TryGetValue, vous voyez que c'est le cas:

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

tandis 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 sera presque deux fois plus rapide que la combinaison ContainsKey + Item.

On s'en fout :-)

Vous demandez probablement parce que TryGetValuec'est pénible à utiliser - alors encapsulez-le comme ceci avec une méthode d'extension.

public static class CollectionUtils
{
    // my original method
    // public static V GetValueOrDefault<K, V>(this Dictionary<K, V> 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<K, V>(this IDictionary<K, V> 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;
    }

Ensuite, appelez simplement:

dict.GetValueOrDefault("keyname")

ou

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

Pourquoi ne le testes-tu pas?

Mais je suis sûr que TryGetValuec'est plus rapide, car il ne fait qu'une seule 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 Findfonction interne qui trouve l'emplacement pour un élément, puis à créer le reste par-dessus.

Jusqu'à présent, toutes les réponses, bien que 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 au sens 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 ne fasse partie de la définition d'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 quels que soient le langage, l'infrastructure, le système d'exploitation, la plate-forme ou l'architecture de la machine. Il est également plus lisible, car il exprime votre intention de manière explicite, 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 «Oui» (TryGetValue est préférable à une combinaison de ContainsKey et Item [Get] pour récupérer une valeur à partir d'un dictionnaire).

Si vous pensez que cela semble étrange, pensez-y comme ceci: même si les implémentations actuelles de TryGetValue, ContainsKey et Item [Get] ne produisent aucune différence de vitesse, vous pouvez supposer qu'il est probable qu'une implémentation future (par exemple .NET v5) fera (TryGetValue sera plus rapide). Pensez à la durée de vie de votre logiciel.

Soit dit en passant, il est intéressant de noter que les technologies de définition d'interface modernes typiques fournissent encore rarement un moyen de définir formellement les contraintes de synchronisation. Peut-être .NET v5?

En faisant un programme de test rapide, il y a certainement une amélioration en utilisant TryGetValue avec 1 million d'éléments dans un dictionnaire.

Résultats:

Contient une clé + un élément pour 1000000 hits: 45 ms

TryGetValue pour 1000000 hits: 26ms

Voici l'application de test:

static void Main(string[] args)
{
    const int size = 1000000;

    var dict = new Dictionary<int, string>();

    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 beaucoup de RAM, lorsqu'elle est exécutée en mode RELEASE (pas DEBUG), ContainsKeyest égal à TryGetValue/ try-catchsi toutes les entrées du Dictionary<>sont trouvées.

ContainsKeyles surpasse tous de loin quand il n'y a que quelques entrées de dictionnaire introuvables (dans mon exemple ci-dessous, réglé MAXVALsur quelque chose de plus grand que ENTRIESd'avoir certaines entrées manquées):

Résultats:

Finished evaluation .... Time distribution:
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(string[] args)
            {
                const int ENTRIES = 10000, MAXVAL = 15000, TRIALS = 100000, MULTIPLIER = 2;
                Dictionary<int, int> values = new Dictionary<int, int>();
                Random r = new Random();
                int[] lookups = new int[TRIALS];
                int val;
                List<Tuple<long, long, long>> durations = new List<Tuple<long, long, long>>(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<long, long, long>(a, b, c));
                }

                Console.ForegroundColor = ConsoleColor.Yellow;
                Console.WriteLine("Finished evaluation .... Time distribution:");
                Console.ForegroundColor = bu;

                val = 10;
                foreach (Tuple<long, long, long> 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();
            }
        }
    }

Mis à part la conception d'une microbenchmark qui donnera des résultats précis dans un cadre pratique, vous pouvez inspecter la source de référence de .NET Framework.

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

Tous appellent la FindEntry(TKey)méthode qui fait la plupart du travail et ne mémorise pas son résultat, donc appeler TryGetValueest presque deux fois plus rapide que ContainsKey+Item .

L'interface peu pratique de TryGetValuepeut être adaptée à l'aide d'une méthode d'extension :

using System.Collections.Generic;

namespace Project.Common.Extensions
{
    public static class DictionaryExtensions
    {
        public static TValue GetValueOrDefault<TKey, TValue>(
            this IDictionary<TKey, TValue> 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 default(TValue)par plain default. Le type est déduit.}

Usage:

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

Il renvoie nullpour 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<string, object>();
object valObj = dictObj.GetValueOrDefault("nonexistent");
Debug.Assert(valObj == null);

val dictInt = new Dictionary<string, int>();
int valInt = dictInt.GetValueOrDefault("nonexistent");
Debug.Assert(valInt == 0);

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 écraser les anciennes clés, et seulement avec cette portée, ContainsKey (clé) 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<int, int> testdict = new Dictionary<int, int>();
    public static Hashtable testhash = new Hashtable();

    public static void Main(string[] 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);
    }
}
}

Ceci est un véritable exemple, j'ai un service qui pour chaque "article" créé, il associe un numéro progressif, ce numéro, chaque fois que vous créez un nouvel article, doit être trouvé gratuit, 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é:
Ajout d'éléments dans la table de hachage ...
Fait en 0,5908 - pause ....
Ajout d'éléments dans le dictionnaire ...
Fait en 0,2679 - pause ....
Recherche du premier numéro libre 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 en 0,0643 - valeur ajoutée 1000001 dans le dictionnaire - pause ....
Test de la table de hachage
Terminé en 0, 3015 - valeur ajoutée 1000000 dans la table de hachage - pause ....
Appuyez sur n'importe quelle touche pour continuer. .

Si certains d'entre vous demandent si les ContainsKeys pourraient avoir un avantage, j'ai même essayé d'inverser la clé TryGetValue avec 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.