Dlaczego szybciej jest sprawdzić, czy słownik zawiera klucz, zamiast wychwycić wyjątek na wypadek, gdyby nie był?

Question

Wyobraźmy sobie kod:

public class obj 
{ 
    // elided 
} 

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

Metoda 1

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

Method 2

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

Byłem ciekaw, czy istnieje różnica w wydajności tych 2 funkcje, ponieważ pierwszy powinien być WOLNY niż drugi - zważywszy, że musi sprawdź dwa razy, czy słownik zawiera wartość, podczas gdy druga funkcja musi uzyskać dostęp do słownika tylko jeden raz, ale WOW, to jest faktycznie odwrotnie:

Pętla dla 1 000 000 wartości (przy 100 000 istniejących i 900 000 nieistniejących):

pierwsza funkcja: 306 milisekund

Druga funkcja: 20483 milisekund

Dlaczego tak jest?

EDYCJA: Jak można zauważyć w komentarzach poniżej tego pytania, wydajność drugiej funkcji jest w rzeczywistości nieco lepsza niż pierwsza, w przypadku gdy istnieje 0 kluczy nie istniejących. Ale gdy istnieje co najmniej jeden nieistniejący klucz, wydajność drugiego szybko maleje.

Answer 1

Z jednej strony, throwing exceptions is inherently expensive, ponieważ stos musi być rozwijana itp
Z drugiej strony, dostęp do wartości w słowniku przez jego klucz jest tania, ponieważ jest to szybka, O (1) operacji.

BTW: Poprawny sposób to zrobić jest użycie TryGetValue

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

ten uzyskuje dostęp do słownika tylko raz, a nie dwa razy.
Jeśli naprawdę chcą tylko wrócić null jeśli klucz nie istnieje, powyższy kod można uprościć dalej:

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

To działa, ponieważ TryGetValue zestawy item do null jeśli żaden klawisz z name istnieje.

Answer 2

Słowniki zostały specjalnie zaprojektowane do wykonywania superszybkich wyszukiwań kluczowych. Są one implementowane jako hashtables, a im więcej wpisów, tym szybciej są one względem innych metod. Używanie mechanizmu wyjątku powinno być wykonywane tylko wtedy, gdy twoja metoda nie wykonała tego, co zaprojektowałeś, ponieważ jest to duży zestaw obiektów, który zapewnia wiele funkcji do obsługi błędów. Raz zbudowałem całą klasę biblioteki, a wszystko, co zostało otoczone przez wypróbowanie bloków catch, było przerażone, gdy zobaczyłem wynik debugowania, który zawierał osobną linię dla każdego z ponad 600 wyjątków!