Warum ist es schneller zu überprüfen, ob das Wörterbuch den Schlüssel enthält, als die Ausnahme abzufangen, falls dies nicht der Fall ist?

234

Stellen Sie sich den Code vor:

public class obj
{
    // elided
}

public static Dictionary<string, obj> dict = new Dictionary<string, obj>();

Methode 1

public static obj FromDict1(string name)
{
    if (dict.ContainsKey(name))
    {
        return dict[name];
    }
    return null;
}

Methode 2

public static obj FromDict2(string name)
{
    try
    {
        return dict[name];
    }
    catch (KeyNotFoundException)
    {
        return null;
    }
}

Ich war neugierig, ob es einen Unterschied in der Leistung dieser beiden Funktionen gibt, da die erste langsamer sein sollte als die zweite - da zweimal überprüft werden muss, ob das Wörterbuch einen Wert enthält, während die zweite Funktion nur auf das Wörterbuch zugreifen muss einmal aber WOW, es ist eigentlich umgekehrt:

Schleife für 1 000 000 Werte (mit 100 000 vorhandenen und 900 000 nicht vorhandenen):

erste Funktion: 306 Millisekunden

zweite Funktion: 20483 Millisekunden

Warum ist das so?

BEARBEITEN: Wie Sie in den Kommentaren unter dieser Frage sehen können, ist die Leistung der zweiten Funktion tatsächlich etwas besser als die der ersten, falls 0 nicht vorhandene Tasten vorhanden sind. Sobald jedoch mindestens ein oder mehrere nicht vorhandene Schlüssel vorhanden sind, nimmt die Leistung des zweiten Schlüssels schnell ab.

Petr
quelle
39
Warum der erste sollte langsamer sein? Eigentlich würde ich auf den ersten Blick sagen, es sollte schneller sein, ContainsKeywird erwartet O(1)...
Patryk Ćwiek
8
@Petr Das Auslösen von Ausnahmen beinhaltet viel mehr Anweisungen als das O(1)Nachschlagen im Wörterbuch ... Zumal das Ausführen von zwei O(1)Operationen immer noch asymptotisch ist O(1).
Patryk Ćwiek
9
Wie in der guten Antwort unten erwähnt, ist das Werfen von Ausnahmen teuer. Ihr Name deutet darauf hin: Sie sollen für außergewöhnliche Umstände reserviert sein . Wenn Sie eine Schleife ausführen, in der Sie ein Wörterbuch millionenfach nach nicht vorhandenen Schlüsseln abfragen, ist dies kein außergewöhnlicher Umstand mehr. Wenn Sie ein Wörterbuch nach Schlüsseln abfragen und es relativ häufig vorkommt, dass diese Schlüssel nicht vorhanden sind, ist es sinnvoll, zuerst zu prüfen.
Jason R
6
Vergessen Sie nicht, dass Sie nur die Kosten für die Überprüfung auf eine Million fehlender Werte verglichen haben, anstatt eine Million Ausnahmen auszulösen. Die beiden Methoden unterscheiden sich jedoch auch in den Kosten für den Zugriff auf einen vorhandenen Wert. Wenn fehlende Schlüssel selten genug sind, ist die Ausnahmemethode trotz der höheren Kosten bei fehlendem Schlüssel insgesamt schneller .
Alexis

Antworten:

404

Einerseits ist das Auslösen von Ausnahmen von Natur aus teuer , da der Stapel abgewickelt werden muss usw.
Andererseits ist der Zugriff auf einen Wert in einem Wörterbuch über seinen Schlüssel billig, da es sich um eine schnelle O (1) -Operation handelt.

Übrigens: Der richtige Weg, dies zu tun, ist zu verwenden TryGetValue

obj item;
if(!dict.TryGetValue(name, out item))
    return null;
return item;

Dadurch wird nur einmal statt zweimal auf das Wörterbuch zugegriffen.
Wenn Sie wirklich nur zurückkehren möchten, nullwenn der Schlüssel nicht vorhanden ist, kann der obige Code weiter vereinfacht werden:

obj item;
dict.TryGetValue(name, out item);
return item;

Dies funktioniert, weil TryGetValueSätze itemzu , nullwenn kein Schlüssel mit nameexistiert.

Daniel Hilgarth
quelle
4
Ich habe meinen Test entsprechend der Antwort aktualisiert und aus irgendeinem Grund ist er, obwohl die vorgeschlagene Funktion schneller ist, tatsächlich nicht sehr signifikant: 264 ms Original, 258 ms vorgeschlagen
Petr
52
@Petr: Ja, das ist nicht wichtig, da der Zugriff auf das Wörterbuch sehr schnell ist. Es spielt keine Rolle, ob Sie es ein- oder zweimal tun. Die meisten dieser 250 ms werden höchstwahrscheinlich in der Testschleife selbst verbracht.
Daniel Hilgarth
4
Dies ist gut zu wissen, da manchmal der Eindruck entsteht, dass das Auslösen von Ausnahmen eine bessere oder sauberere Methode ist, um mit Situationen wie nicht vorhandenen Dateien oder Nullzeigern umzugehen, unabhängig davon, ob diese Situationen häufig sind und ohne Berücksichtigung der Leistungskosten.
LarsH
4
@LarsH es kommt auch darauf an was du tust. Während einfache Mikrobenchmarks wie dieses wirklich große Strafen für Ausnahmen anzeigen, sobald Ihre Schleifen beginnen, einschließlich Datei- oder Datenbankaktivitäten, die bei jeder Iteration eine Ausnahme auslösen, ist dies für die Leistung sehr unwichtig. Vergleichen Sie die 1. und 2. Tabelle: codeproject.com/Articles/11265/…
Dan spielt am
8
@LarsH Beachten Sie auch, dass beim Versuch, auf eine Datei (oder eine andere externe Ressource) zuzugreifen, der Status zwischen der Überprüfung und dem tatsächlichen Zugriffsversuch geändert werden kann. In diesen Fällen ist die Verwendung von Ausnahmen der richtige Weg. Weitere Informationen finden Sie in der Antwort von Stephen C auf diese Frage .
YoniLavi
6

Wörterbücher wurden speziell für die superschnelle Suche nach Schlüsseln entwickelt. Sie werden als Hashtabellen implementiert und je mehr Einträge vorhanden sind, desto schneller sind sie im Vergleich zu anderen Methoden. Die Verwendung der Ausnahme-Engine sollte nur durchgeführt werden, wenn Ihre Methode nicht das getan hat, wofür Sie sie entworfen haben, da es sich um eine große Menge von Objekten handelt, die Ihnen viele Funktionen zur Behandlung von Fehlern bieten. Ich habe einmal eine ganze Bibliotheksklasse mit allem erstellt, was einmal von try catch-Blöcken umgeben war, und war entsetzt, als ich die Debug-Ausgabe sah, die für jede einzelne von über 600 Ausnahmen eine separate Zeile enthielt!

Ed Hermanson
quelle
1
Wenn Sprachimplementierer entscheiden, wo Optimierungsbemühungen aufgewendet werden sollen, erhalten Hash-Tabellen Vorrang, da sie häufig verwendet werden, häufig in inneren Schleifen, bei denen es sich möglicherweise um Engpässe handelt. Es wird erwartet, dass Ausnahmen nur in ungewöhnlichen (sozusagen "außergewöhnlichen") Fällen viel seltener verwendet werden, sodass sie normalerweise nicht als wichtig für die Leistung angesehen werden.
Barmar
"Sie werden als Hashtabellen implementiert und je mehr Einträge vorhanden sind, desto schneller sind sie im Vergleich zu anderen Methoden." das stimmt doch nicht, wenn sich die eimer füllen?!?!
Anthony Lambert
1
@AnthonyLambert Was er damit sagen will, ist, dass das Durchsuchen einer Hashtabelle eine zeitliche Komplexität von O (1) hat, während eine Suche im binären Suchbaum O (log (n)) haben würde; Der Baum wird langsamer, wenn die Anzahl der Elemente asymptotisch zunimmt, während die Hashtabelle dies nicht tut. Daher nimmt der Geschwindigkeitsvorteil der Hashtabelle mit der Anzahl der Elemente zu, obwohl dies langsam geschieht.
Doval
@AnthonyLambert Bei normaler Verwendung gibt es extrem wenige Kollisionen in der Hashtabelle eines Wörterbuchs. Wenn Sie eine Hashtabelle verwenden und Ihre Eimer voll sind, haben Sie möglicherweise zu viele Einträge (oder zu wenige Eimer). In diesem Fall ist es Zeit, eine benutzerdefinierte Hashtabelle zu verwenden.
AndrewS