Co jest bardziej wydajne: Słownik TryGetValue lub ContainsKey + Item?

Z pozycji MSDN w Dictionary.TryGetValue Metoda :

Ta metoda łączy funkcjonalność metody ContainsKey i właściwości Item.

Jeśli klucz nie zostanie znaleziony, wówczas parametr value otrzymuje odpowiednią wartość domyślną dla typu wartości TValue; na przykład 0 (zero) dla typów całkowitych, false dla typów boolowskich, a null dla typów referencyjnych.

Użyj metody TryGetValue, jeśli kod często próbuje uzyskać dostęp do kluczy, których nie ma w słowniku. Użycie tej metody jest bardziej wydajne niż wyłapanie wyjątku KeyNotFoundException zgłaszanego przez właściwość Item.

Ta metoda zbliża się do operacji O (1).

Z opisu nie jest jasne, czy jest bardziej wydajne czy po prostu wygodniejsze niż wywołanie ContainsKey, a następnie wykonanie wyszukiwania. Czy implementacja TryGetValuewywołania ContainsKey, a następnie Item, czy też jest faktycznie bardziej wydajna, wykonując jedno wyszukiwanie?

Innymi słowy, co jest bardziej wydajne (tj. Który wykonuje mniej wyszukiwań):

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

lub

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

Uwaga: nie szukam punktu odniesienia!

TryGetValue będzie szybciej.

ContainsKeyużywa tej samej kontroli co TryGetValue, która wewnętrznie odnosi się do faktycznej lokalizacji wejścia. ItemNieruchomość faktycznie ma prawie identyczną funkcjonalność jak kodTryGetValue , oprócz tego, że będzie to wyjątek zamiast wrócić fałszywe.

Użycie funkcji „ ContainsKeynastępuje po” Itemzasadniczo powiela funkcję wyszukiwania, która w tym przypadku stanowi większość obliczeń.

Szybki test porównawczy pokazuje, że TryGetValuema niewielką przewagę:

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

To produkuje

00:00:00.7600000
00:00:01.0610000

dzięki czemu ContainsKey + Itemdostęp do około 40% wolniej zakładając nawet mieszanka trafień i tęskni.

Ponadto, gdy zmieniam program tak, aby zawsze tęsknił (tj. Zawsze patrzył w górę "b"), dwie wersje stały się równie szybkie:

00:00:00.2850000
00:00:00.2720000

Kiedy jednak robię to „wszystkie hity”, TryGetValuepozostaje wyraźnym zwycięzcą:

00:00:00.4930000
00:00:00.8110000

Ponieważ żadna z dotychczasowych odpowiedzi nie odpowiada na pytanie, oto akceptowalna odpowiedź, którą znalazłem po kilku badaniach:

Jeśli dekompilujesz TryGetValue, zobaczysz, że robi to:

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

podczas gdy metoda ContainsKey to:

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

więc TryGetValue to tylko ContainsKey plus wyszukiwanie tablicy, jeśli element jest obecny.

Źródło

Wygląda na to, że TryGetValue będzie prawie dwa razy szybszy niż kombinacja ContainsKey + Item.

Kogo to obchodzi :-)

Prawdopodobnie pytasz, ponieważ TryGetValuejest to trudny w użyciu - więc obuduj go w ten sposób metodą rozszerzenia.

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

Następnie wystarczy zadzwonić:

dict.GetValueOrDefault("keyname")

lub

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

Dlaczego tego nie przetestujesz?

Ale jestem pewien, że TryGetValuejest to szybsze, ponieważ wykonuje tylko jedno wyszukiwanie. Oczywiście nie jest to gwarantowane, tzn. Różne implementacje mogą mieć różne charakterystyki wydajności.

Zaimplementowałbym słownik, tworząc wewnętrzną Findfunkcję, która wyszukuje miejsce dla przedmiotu, a następnie buduję resztę na nim.

Wszystkie dotychczasowe odpowiedzi, choć dobre, nie mają istotnego znaczenia.

Metody do klas API (np. .NET Framework) stanowią część definicji interfejsu (nie interfejsu C # lub VB, ale interfejs w znaczeniu informatyki).

W związku z tym zwykle niewłaściwe jest pytanie, czy wywołanie takiej metody jest szybsze, chyba że prędkość jest częścią formalnej definicji interfejsu (czego nie ma w tym przypadku).

Tradycyjnie ten rodzaj skrótu (łączący wyszukiwanie i pobieranie) jest bardziej wydajny bez względu na język, infrastrukturę, system operacyjny, platformę lub architekturę maszyny. Jest także bardziej czytelny, ponieważ wyraźnie wyraża twoją intencję, a nie sugeruje (ze struktury twojego kodu).

Tak więc odpowiedź (ze starego, posiwiałego hacka) jest zdecydowanie „Tak” (TryGetValue jest lepsza niż kombinacja ContainsKey i Item [Get], aby pobrać wartość ze słownika).

Jeśli uważasz, że to brzmi dziwnie, pomyśl o tym w ten sposób: Nawet jeśli obecne implementacje TryGetValue, ContainsKey i Item [Get] nie dają żadnej różnicy prędkości, możesz założyć, że prawdopodobne jest, że przyszła implementacja (np. .NET v5) zrobi (TryGetValue będzie szybszy). Pomyśl o żywotności swojego oprogramowania.

Nawiasem mówiąc, warto zauważyć, że typowe nowoczesne technologie definiowania interfejsów nadal rzadko zapewniają jakiekolwiek formalne określenie ograniczeń czasowych. Może .NET v5?

Dzięki szybkiemu programowi testowemu zdecydowanie poprawiono użycie TryGetValue z 1 milionem pozycji w słowniku.

Wyniki:

Zawiera klucz + przedmiot za 1000000 trafień: 45ms

TryGetValue dla 1000000 odsłon: 26ms

Oto aplikacja testowa:

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 mojej maszynie, z dużą ilością pamięci RAM, gdy jest uruchomiony w trybie RELEASE (nie DEBUG), ContainsKeyjest równy TryGetValue/ try-catchjeśli wszystkie wpisy w Dictionary<>są znalezione.

ContainsKeyzdecydowanie przewyższa je wszystkie, gdy nie znaleziono tylko kilku pozycji słownika (w moim przykładzie poniżej, ustaw MAXVALna wartość większą niż brak ENTRIESniektórych pozycji):

Wyniki:

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

Oto mój kod:

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

Oprócz zaprojektowania znaku mikrodruku, który da dokładne wyniki w praktycznych warunkach, możesz sprawdzić źródło odniesienia .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)

Wszyscy nazywają FindEntry(TKey)metodę, która wykonuje większość pracy i nie zapamiętuje jej wyniku, więc wywołanie TryGetValuejest prawie dwa razy szybsze niż ContainsKey+Item .

Niewygodny interfejs TryGetValuemożna dostosować za pomocą metody rozszerzenia :

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

^{Od wersji C # 7.1 możesz zastąpić default(TValue)zwykłym default. Rodzaj jest wywnioskowany.}

Stosowanie:

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

Zwraca nulltypy referencji, których wyszukiwanie kończy się niepowodzeniem, chyba że określono jawną wartość domyślną.

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

Jeśli próbujesz wyciągnąć wartość ze słownika, TryGetValue (klucz, wartość wyjściowa) jest najlepszą opcją, ale jeśli sprawdzasz obecność klucza, czy chcesz go wstawić bez nadpisywania starych kluczy, i tylko w tym zakresie ContainsKey (klucz) jest najlepszą opcją, test porównawczy może to potwierdzić:

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

To jest prawdziwy przykład. Mam usługę, która dla każdego utworzonego „elementu” przypisuje numer progresywny. Numer ten, za każdym razem, gdy tworzysz nowy element, musi być znaleziony wolny, jeśli usuniesz element, bezpłatny numer stanie się za darmo, oczywiście nie jest to zoptymalizowane, ponieważ mam statyczny var, który buforuje bieżącą liczbę, ale w przypadku zakończenia wszystkich liczb, możesz ponownie rozpocząć od 0 do UInt32.MaxValue

Wykonano test:
Dodawanie elementów do
tablicy mieszającej ... Gotowe za 0,5908 - pauza ....
Dodawanie elementów do słownika ...
Gotowe za 0,2679 - pauza ....
Znajdowanie pierwszego wolnego numeru do wstawienia
Pierwsza metoda : Zawiera
klucz Gotowe w 0,0561 - wartość dodana 1000000 w słowniku - pauza ....
Druga metoda: TryGetValue
Gotowe w 0,0643 - wartość dodana 1000001 w słowniku - pauza ....
Test hashtable
Gotowe w 0, 3015 - wartość dodana 1000000 do tablicy mieszającej - pauza ....
Naciśnij dowolny klawisz, aby kontynuować. .

Jeśli niektórzy z was mogą pytać, czy klucze ContainsKeys mogą mieć przewagę, próbowałem nawet odwrócić klucz TryGetValue z kluczem Contains, wynik jest taki sam.

Więc, dla mnie, z ostatecznym rozważeniem, wszystko zależy od tego, jak program się zachowuje.