¿Qué es más eficiente: Diccionario TryGetValue o ContainsKey + Item?

Desde la entrada de MSDN en el método Dictionary.TryGetValue :

Este método combina la funcionalidad del método ContainsKey y la propiedad Item.

Si no se encuentra la clave, el parámetro value obtiene el valor predeterminado apropiado para el tipo de valor TValue; por ejemplo, 0 (cero) para tipos enteros, falso para tipos booleanos y nulo para tipos de referencia.

Utilice el método TryGetValue si su código intenta acceder frecuentemente a claves que no están en el diccionario. Usar este método es más eficiente que atrapar la KeyNotFoundException lanzada por la propiedad Item.

Este método aborda una operación O (1).

De la descripción, no está claro si es más eficiente o simplemente más conveniente que llamar a ContainsKey y luego hacer la búsqueda. ¿La implementación de TryGetValue solo llama a ContainsKey y luego a Item o en realidad es más eficiente al hacer una única búsqueda?

En otras palabras, ¿qué es más eficiente (es decir, cuál realiza menos búsquedas)?

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

o

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

Nota: ¡No estoy buscando un punto de referencia!

TryGetValue será más rápido.

ContainsKey utiliza el mismo control que TryGetValue , que se refiere internamente a la ubicación de entrada real. La propiedad Item realidad tiene una funcionalidad de código casi idéntica a TryGetValue , excepto que lanzará una excepción en lugar de devolver false.

El uso de ContainsKey seguido del ítem básicamente duplica la funcionalidad de búsqueda, que es la mayor parte del cálculo en este caso.

Un punto de referencia rápido muestra que TryGetValue tiene una ligera ventaja:

  static void Main() { var d = new Dictionary {{"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); } } } 

Esto produce

 00:00:00.7600000 00:00:01.0610000 

haciendo que el acceso de ContainsKey + Item un 40% más lento suponiendo una combinación uniforme de éxitos y errores.

Además, cuando cambio el progtwig para que siempre falle (es decir, siempre buscando "b" ), las dos versiones se vuelven igual de rápidas:

 00:00:00.2850000 00:00:00.2720000 

Sin embargo, cuando TryGetValue “todos los éxitos”, TryGetValue sigue siendo un claro ganador:

 00:00:00.4930000 00:00:00.8110000 

Dado que ninguna de las respuestas hasta ahora realmente responde la pregunta, aquí hay una respuesta aceptable que encontré después de algunas investigaciones:

Si descomstacks TryGetValue, ves que está haciendo esto:

 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; } 

mientras que el método ContainsKey es:

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

así que TryGetValue es solo ContainsKey más una búsqueda de matriz si el artículo está presente.

Fuente

Parece que TryGetValue será casi dos veces más rápido que la combinación de ContainsKey + Item.

A quien le importa 🙂

Probablemente estés preguntando porque TryGetValue es TryGetValue de usar, así que TryGetValue así con un método de extensión.

 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; } 

Entonces solo llame:

 dict.GetValueOrDefault("keyname") 

o

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

¿Por qué no lo pruebas?

Pero estoy bastante seguro de que TryGetValue es más rápido, ya que solo hace una búsqueda. Por supuesto, esto no está garantizado, es decir, diferentes implementaciones pueden tener diferentes características de rendimiento.

La forma en que implementaría un diccionario es mediante la creación de una función de Find interna que encuentre la ranura para un elemento y luego construya el rest encima de eso.

Todas las respuestas hasta ahora, aunque buenas, pierden un punto vital.

Los métodos en las clases de una API (por ejemplo, el marco .NET) forman parte de una definición de interfaz (no una interfaz C # o VB, sino una interfaz en el significado de la informática).

Como tal, generalmente es incorrecto preguntar si llamar a dicho método es más rápido, a menos que la velocidad sea una parte de la definición formal de la interfaz (que no es en este caso).

Tradicionalmente, este tipo de atajo (combinación de búsqueda y recuperación) es más eficiente independientemente del idioma, la infraestructura, el sistema operativo, la plataforma o la architecture de la máquina. También es más legible, porque expresa su intención explícitamente, en lugar de implicarla (a partir de la estructura de su código).

Así que la respuesta (de un viejo truco entrecano) es definitivamente ‘Sí’ (TryGetValue es preferible a una combinación de ContainsKey y Item [Get] para recuperar un valor de un Dictionary).

Si cree que esto suena extraño, piénselo de esta manera: incluso si las implementaciones actuales de TryGetValue, ContainsKey y Item [Get] no producen ninguna diferencia de velocidad, puede suponer que es probable que una implementación futura (por ejemplo, .NET v5) lo hará (TryGetValue será más rápido). Piensa en la vida útil de tu software.

Por otro lado, es interesante observar que las tecnologías modernas típicas de definición de interfaz aún rara vez proporcionan algún medio para definir formalmente las restricciones de tiempo. Tal vez .NET v5?

Hacer un progtwig de prueba rápido, definitivamente es una mejora usando TryGetValue con 1 millón de elementos en un diccionario.

Resultados:

ContainsKey + Item para 1000000 hits: 45ms

TryGetValue para 1000000 visitas: 26ms

Aquí está la aplicación de prueba:

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

En mi máquina, con mucha RAM, cuando se ejecuta en modo RELEASE (no DEBUG), ContainsKey es igual a TryGetValue / try-catch si se encuentran todas las entradas en el Dictionary<> .

ContainsKey supera a todos de lejos cuando solo hay unas pocas entradas en el diccionario que no se encuentran (en mi ejemplo a continuación, establezca MAXVAL en cualquier cantidad mayor que ENTRIES para que se MAXVAL algunas entradas):

Resultados:

 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 

Aquí está mi código:

  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 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 distribution:"); 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 intenta obtener el valor del diccionario, TryGetValue (clave, valor de salida) es la mejor opción, pero si está comprobando la presencia de la clave, para una nueva inserción, sin sobreescribir claves antiguas, y solo con ese scope, ContainsKey (clave) es la mejor opción, el punto de referencia puede confirmar esto:

 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(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); } } } 

Este es un verdadero Ejemplo, tengo un servicio que para cada "Artículo" creado, asocia un número progresivo, este número, cada vez que crea un nuevo elemento, debe encontrarse libre, si elimina un Artículo, el número libre se convierte en gratis, por supuesto, esto no está optimizado, ya que tengo una var estática que almacena en caché el número actual, pero en caso de que finalice todos los números, puede volver a comenzar de 0 a UInt32.MaxValue

Prueba ejecutada:
Agregar elementos a hashtable ...
Hecho en 0,5908 - pausa ....
Agregar elementos al diccionario ...
Hecho en 0,2679 - pausa ....
Encontrar el primer número gratuito para inserción
Primer método: ContainsKey
Hecho en 0,0561 - valor agregado 1000000 en el diccionario - pausa ....
Segundo método: TryGetValue
Hecho en 0,0643 - valor agregado 1000001 en diccionario - pausa ....
Prueba hashtable
Hecho en 0,3015 - valor agregado 1000000 en hashtable - pause ....
Pulse cualquier tecla para continuar . .

Si algunos de ustedes pueden estar preguntando si ContainsKeys podría tener una ventaja, incluso he tratado de invertir la clave TryGetValue con Contiene, el resultado es el mismo.

Entonces, para mí, con una consideración final, todo depende de la forma en que se comporte el progtwig.

Además de diseñar una microbenchmark que dará resultados precisos en un entorno práctico, puede inspeccionar la fuente de referencia de .NET Framework.

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

Todos ellos llaman al FindEntry(TKey) que hace la mayor parte del trabajo y no memoriza su resultado, por lo que llamar a TryGetValue es casi dos veces más rápido que ContainsKey + Item .


La interfaz inconveniente de TryGetValue se puede adaptar utilizando un método de extensión :

 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; } } } 

Desde C # 7.1, puede reemplazar el default(TValue) con el default simple. El tipo se infiere.

Uso:

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

Devuelve null para los tipos de referencia cuya búsqueda falla, a menos que se especifique un valor predeterminado explícito.

 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);