O que é mais eficiente: Dicionário TryGetValue ou ContainsKey + Item?

Da entrada do MSDN no método Dictionary.TryGetValue :

Este método combina a funcionalidade do método ContainsKey e a propriedade Item.

Se a chave não for encontrada, o parâmetro value obterá o valor padrão apropriado para o tipo de valor TValue; por exemplo, 0 (zero) para tipos inteiros, falso para tipos booleanos e nulo para tipos de referência.

Use o método TryGetValue se o seu código tentar acessar frequentemente chaves que não estão no dicionário. O uso desse método é mais eficiente do que capturar a KeyNotFoundException lançada pela propriedade Item.

Este método aborda uma operação O (1).

Na descrição, não está claro se é mais eficiente ou apenas mais conveniente do que chamar ContainsKey e, em seguida, fazer a pesquisa. A implementação deTryGetValue apenas chama ContainsKey e, em seguida, Item ou é realmente mais eficiente do que isso, fazendo uma única pesquisa?

Em outras palavras, o que é mais eficiente (ou seja, qual deles realiza menos pesquisas):

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

Nota: Não estou procurando uma referência!

TryGetValue será mais rápido.

ContainsKeyusa a mesma verificação que TryGetValue, que internamente se refere ao local de entrada real. A Itempropriedade realmente possui funcionalidade de código quase idêntica àTryGetValue , exceto que lançará uma exceção em vez de retornar false.

O uso ContainsKeyseguido pelo Itembasicamente duplica a funcionalidade de pesquisa, que é a maior parte da computação nesse caso.

Uma referência rápida mostra que TryGetValuetem uma ligeira vantagem:

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

Isso produz

00:00:00.7600000
00:00:01.0610000

tornando o ContainsKey + Itemacesso cerca de 40% mais lento, assumindo uma mistura uniforme de acertos e erros.

Além disso, quando mudo o programa para sempre errar (ou seja, sempre olhando para cima "b"), as duas versões se tornam igualmente rápidas:

00:00:00.2850000
00:00:00.2720000

Quando eu faço "todos os hits", no entanto, TryGetValuecontinua sendo um vencedor claro:

00:00:00.4930000
00:00:00.8110000

Como nenhuma das respostas até agora realmente responde à pergunta, aqui está uma resposta aceitável que encontrei após algumas pesquisas:

Se você descompilar o TryGetValue, verá que está fazendo o seguinte:

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

enquanto o método ContainsKey é:

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

portanto, TryGetValue é apenas ContainsKey mais uma pesquisa de matriz se o item estiver presente.

Fonte

Parece que TryGetValue será quase duas vezes mais rápido que a combinação ContainsKey + Item.

Quem se importa :-)

Você provavelmente está perguntando porque TryGetValueé um problema usar - então encapsule-o assim com um método de extensão.

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

Em seguida, basta ligar para:

dict.GetValueOrDefault("keyname")

ou

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

Por que você não testa?

Mas tenho certeza de que TryGetValueé mais rápido, porque faz apenas uma pesquisa. Obviamente, isso não é garantido, ou seja, implementações diferentes podem ter características de desempenho diferentes.

A maneira como eu implementaria um dicionário é criando uma Findfunção interna que encontre o espaço para um item e depois construa o restante.

Todas as respostas até agora, apesar de boas, perdem um ponto vital.

Os métodos nas classes de uma API (por exemplo, a estrutura .NET) fazem parte de uma definição de interface (não uma interface C # ou VB, mas uma interface no significado de ciência da computação).

Como tal, geralmente é incorreto perguntar se a chamada de um método desse tipo é mais rápida, a menos que a velocidade faça parte da definição formal da interface (o que não ocorre nesse caso).

Tradicionalmente, esse tipo de atalho (combinando pesquisa e recuperação) é mais eficiente, independentemente do idioma, infraestrutura, sistema operacional, plataforma ou arquitetura da máquina. Também é mais legível, porque expressa sua intenção explicitamente, em vez de implicar (a partir da estrutura do seu código).

Portanto, a resposta (de um hack antigo mal-humorado) é definitivamente 'Sim' (TryGetValue é preferível a uma combinação de ContainsKey e Item [Get] para recuperar um valor de um Dicionário).

Se você acha isso estranho, pense assim: Mesmo que as implementações atuais de TryGetValue, ContainsKey e Item [Get] não produzam nenhuma diferença de velocidade, você pode assumir que é provável que uma implementação futura (por exemplo, .NET v5) fará (TryGetValue será mais rápido). Pense na vida útil do seu software.

Como um aparte, é interessante notar que as tecnologias de definição de interface modernas típicas ainda raramente fornecem meios de definir formalmente as restrições de tempo. Talvez .NET v5?

Fazendo um programa de teste rápido, há definitivamente uma melhoria usando o TryGetValue com 1 milhão de itens em um dicionário.

Resultados:

ContainsKey + Item for 1000000 hits: 45ms

TryGetValue para 1000000 hits: 26ms

Aqui está o aplicativo de teste:

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

}

Na minha máquina, com cargas de RAM, quando executado no modo RELEASE (não DEBUG), ContainsKeyé igual a TryGetValue/ try-catchse todas as entradas no Dictionary<>forem encontradas.

ContainsKeysupera todos eles de longe quando há apenas algumas entradas de dicionário não encontradas (no meu exemplo abaixo, defina MAXVALcomo algo maior do ENTRIESque ter algumas entradas perdidas):

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

Aqui está o meu 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<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();
            }
        }
    }

Além de projetar uma marca de microbench que fornecerá resultados precisos em uma configuração prática, você pode inspecionar a fonte de referência do .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)

Todos eles chamam o FindEntry(TKey)método que faz a maior parte do trabalho e não memoriza seu resultado, portanto, a chamada TryGetValueé quase duas vezes mais rápida que ContainsKey+Item .

A interface inconveniente de TryGetValuepode ser adaptada usando um método de extensão :

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

^{Desde o C # 7.1, você pode substituir default(TValue) por simples default. O tipo é inferido.}

Uso:

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

Ele retorna nullpara tipos de referência cuja pesquisa falha, a menos que um valor padrão explícito seja especificado.

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

Se você estiver tentando obter o valor do dicionário, o TryGetValue (valor da chave, saída) é a melhor opção, mas se você estiver verificando a presença da chave, uma nova inserção, sem substituir as chaves antigas, e somente com esse escopo, ContainsKey (key) é a melhor opção, o benchmark pode confirmar isso:

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

Este é um exemplo verdadeiro. Eu tenho um serviço que, para cada "Item" criado, associa um número progressivo, esse número, toda vez que você cria um novo item, deve ser encontrado gratuitamente. Se você excluir um Item, o número gratuito se tornará grátis, é claro que isso não é otimizado, pois eu tenho uma var estática que armazena em cache o número atual, mas, se você terminar todos os números, poderá reiniciar de 0 a UInt32.MaxValue

Teste executado:
Adicionando elementos
na tabela de hash ... Feito em 0,5908 - pausa ....
Adicionando elementos no dicionário ...
Feito em 0,2679 - pausa ....
Encontrando o primeiro número livre para inserção
Primeiro método : ContainsKey
Concluído em 0,0561 - valor adicionado 1000000 no dicionário - pausa ....
Segundo método: TryGetValue
Concluído em 0,0643 - valor adicionado 1000001 no dicionário - pausa ...
Teste de hashtable
Concluído em 0, 3015 - valor adicionado 1000000 na hashtable - pausa ....
Pressione qualquer tecla para continuar. .

Se alguns de vocês perguntarem se as ContainsKeys podem ter uma vantagem, tentei inverter a chave TryGetValue com Contains, o resultado é o mesmo.

Então, para mim, com uma consideração final, tudo depende da maneira como o programa se comporta.