Was ist effizienter: Dictionary TryGetValue oder ContainsKey + Item?

Aus dem Eintrag von MSDN in der Dictionary.TryGetValue-Methode :

Diese Methode kombiniert die Funktionalität der ContainsKey-Methode und der Item-Eigenschaft.

Wird der Schlüssel nicht gefunden, erhält der Wertparameter den entsprechenden Standardwert für den Werttyp TValue. Beispiel: 0 (Null) für Ganzzahltypen, Falsch für Boolesche Typen und Null für Referenztypen.

Verwenden Sie die TryGetValue-Methode, wenn Ihr Code häufig versucht, auf Schlüssel zuzugreifen, die nicht im Wörterbuch enthalten sind. Die Verwendung dieser Methode ist effizienter als das Abfangen der von der Item-Eigenschaft ausgelösten KeyNotFoundException.

Diese Methode nähert sich einer O (1) -Operation.

Aus der Beschreibung geht nicht hervor, ob es effizienter oder nur bequemer ist, als ContainsKey aufzurufen und dann die Suche durchzuführen. Tut die Implementierung vonTryGetValue nur ContainsKey und dann Item auf oder ist sie tatsächlich effizienter, wenn nur eine einzige Suche durchgeführt wird?

Mit anderen Worten, was ist effizienter (dh welches führt weniger Suchvorgänge durch):

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

oder

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

Hinweis: Ich suche keinen Benchmark!

TryGetValue wird schneller sein.

ContainsKeyverwendet die gleiche Prüfung wie TryGetValue, die sich intern auf den tatsächlichen Eintragsort bezieht. Die ItemEigenschaft hat tatsächlich fast die gleiche Codefunktionalität wieTryGetValue , außer dass eine Ausnahme ausgelöst wird, anstatt false zurückzugeben.

Mit ContainsKeygefolgt von den ItemDuplikaten wird die Suchfunktion dupliziert, die in diesem Fall den größten Teil der Berechnung ausmacht.

Ein schneller Benchmark zeigt, dass er TryGetValueeine leichte Kante hat:

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

Dies erzeugt

00:00:00.7600000
00:00:01.0610000

Der ContainsKey + ItemZugriff wird um etwa 40% langsamer, wenn eine gleichmäßige Mischung aus Treffern und Fehlschlägen angenommen wird.

Wenn ich das Programm so ändere, dass es immer fehlt (dh immer nach oben schaut "b"), werden die beiden Versionen außerdem gleich schnell:

00:00:00.2850000
00:00:00.2720000

Wenn ich es aber "alle Treffer" mache, TryGetValuebleibt das ein klarer Gewinner:

00:00:00.4930000
00:00:00.8110000

Da bisher keine der Antworten die Frage tatsächlich beantwortet, ist hier eine akzeptable Antwort, die ich nach einigen Recherchen gefunden habe:

Wenn Sie TryGetValue dekompilieren, sehen Sie, dass es dies tut:

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

Die ContainsKey-Methode lautet:

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

TryGetValue ist also nur ContainsKey plus eine Array-Suche, wenn das Element vorhanden ist.

Quelle

Es scheint, dass TryGetValue fast doppelt so schnell ist wie die ContainsKey + Item-Kombination.

Wen interessiert das :-)

Sie fragen wahrscheinlich, weil TryGetValuees schmerzhaft ist, es zu verwenden - kapseln Sie es also so mit einer Erweiterungsmethode.

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

Dann rufen Sie einfach an:

dict.GetValueOrDefault("keyname")

oder

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

Warum testest du es nicht?

Aber ich bin mir ziemlich sicher, dass TryGetValuedas schneller geht, weil es nur eine Suche macht. Dies ist natürlich nicht garantiert, dh unterschiedliche Implementierungen können unterschiedliche Leistungsmerkmale aufweisen.

Ich würde ein Wörterbuch implementieren, indem ich eine interne FindFunktion erstelle , die den Steckplatz für ein Element findet, und dann den Rest darauf aufbaue.

Alle bisherigen Antworten sind zwar gut, verfehlen jedoch einen wichtigen Punkt.

Methoden in die Klassen einer API (z. B. das .NET Framework) sind Teil einer Schnittstellendefinition (keine C # - oder VB-Schnittstelle, sondern eine Schnittstelle im Sinne der Informatik).

Daher ist es normalerweise falsch zu fragen, ob das Aufrufen einer solchen Methode schneller ist, es sei denn, Geschwindigkeit ist Teil der formalen Schnittstellendefinition (was in diesem Fall nicht der Fall ist).

Traditionell ist diese Art von Verknüpfung (Kombination von Suchen und Abrufen) effizienter, unabhängig von Sprache, Infrastruktur, Betriebssystem, Plattform oder Maschinenarchitektur. Es ist auch besser lesbar, da es Ihre Absicht explizit ausdrückt, anstatt sie zu implizieren (aus der Struktur Ihres Codes).

Die Antwort (von einem alten Hack mit Grizzles) lautet also definitiv "Ja" (TryGetValue ist einer Kombination aus ContainsKey und Item [Get] vorzuziehen, um einen Wert aus einem Wörterbuch abzurufen).

Wenn Sie der Meinung sind, dass dies seltsam klingt, stellen Sie sich Folgendes vor: Auch wenn aktuelle Implementierungen von TryGetValue, ContainsKey und Item [Get] keinen Geschwindigkeitsunterschied ergeben, können Sie davon ausgehen, dass eine zukünftige Implementierung (z. B. .NET v5) wahrscheinlich ist. wird tun (TryGetValue wird schneller sein). Denken Sie an die Lebensdauer Ihrer Software.

Abgesehen davon ist es interessant festzustellen, dass typische moderne Schnittstellendefinitionstechnologien immer noch selten ein Mittel zur formalen Definition von Zeitbeschränkungen bieten. Vielleicht .NET v5?

Wenn Sie ein schnelles Testprogramm erstellen, gibt es mit TryGetValue mit 1 Million Elementen in einem Wörterbuch definitiv eine Verbesserung.

Ergebnisse:

Enthält Schlüssel + Gegenstand für 1000000 Treffer: 45 ms

TryGetValue für 1000000 Treffer: 26 ms

Hier ist die Test-App:

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

}

Wenn auf meinem Computer mit viel RAM im RELEASE-Modus (nicht DEBUG) ausgeführt wird, ContainsKeyentspricht TryGetValue/, try-catchwenn alle Einträge in Dictionary<>gefunden wurden.

ContainsKeyübertrifft sie alle bei weitem, wenn nur wenige Wörterbucheinträge nicht gefunden wurden (in meinem Beispiel unten MAXVALauf etwas Größeres eingestellt, als ENTRIESdass einige Einträge übersehen werden):

Ergebnisse:

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

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

Neben dem Entwerfen eines Mikrobenchmarks, das in einer praktischen Umgebung genaue Ergebnisse liefert, können Sie auch die Referenzquelle von .NET Framework überprüfen.

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

Alle rufen die FindEntry(TKey)Methode auf, die den größten Teil der Arbeit erledigt und das Ergebnis nicht speichert, sodass der Aufruf TryGetValuefast doppelt so schnell ist wie ContainsKey+Item .

Die unbequeme Schnittstelle von TryGetValuekann unter Verwendung einer Erweiterungsmethode angepasst werden :

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

^{Seit C # 7.1 können Sie durch default(TValue)plain ersetzen default. Der Typ wird abgeleitet.}

Verwendung:

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

Es wird nullfür Referenztypen zurückgegeben, deren Suche fehlschlägt, sofern kein expliziter Standardwert angegeben ist.

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

Wenn Sie versuchen, den Wert aus dem Wörterbuch zu entfernen, ist TryGetValue (Schlüssel, Aus-Wert) die beste Option. Wenn Sie jedoch prüfen, ob der Schlüssel vorhanden ist, suchen Sie nach einer neuen Einfügung, ohne alte Schlüssel zu überschreiben. und nur mit diesem Umfang ist ContainsKey (Schlüssel) die beste Option, Benchmark kann dies bestätigen:

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

Dies ist ein echtes Beispiel. Ich habe einen Dienst, der für jeden erstellten "Artikel" eine progressive Nummer verknüpft. Diese Nummer muss jedes Mal, wenn Sie einen neuen Artikel erstellen, frei gefunden werden. Wenn Sie einen Artikel löschen, wird die kostenlose Nummer kostenlos, dies ist natürlich nicht optimiert, da ich eine statische Variable habe, die die aktuelle Nummer zwischenspeichert, aber falls Sie alle Nummern beenden, können Sie von 0 bis UInt32.MaxValue neu beginnen

Test ausgeführt:
Hinzufügen von Elementen zur Hashtabelle ...
Fertig in 0,5908 - Pause ....
Hinzufügen von Elementen zum Wörterbuch ...
Fertig in 0,2679 - Pause ....
Finden der ersten freien Nummer zum Einfügen
Erste Methode : Enthält den
Schlüssel Fertig in 0,0561 - Mehrwert 1000000 im Wörterbuch - Pause ....
Zweite Methode: TryGetValue
Fertig in 0,0643 - Mehrwert 1000001 im Wörterbuch - Pause ....
Test-Hashtabelle
Fertig in 0, 3015 - Mehrwert 1000000 in Hashtabelle - Pause ....
Drücken Sie eine beliebige Taste, um fortzufahren. .

Wenn einige von Ihnen fragen, ob die ContainsKeys einen Vorteil haben könnten, habe ich sogar versucht, den TryGetValue mit dem Contains-Schlüssel zu invertieren. Das Ergebnis ist das gleiche.

Für mich hängt abschließend alles davon ab, wie sich das Programm verhält.