Przykład przeglądu kodu i co z tego wynikło

Home

Jakiś czas temu robiłem przegląd kodu i zwróciłem uwagę na taki fragment implementacji:

public class SrvObject
{
   public int Id { get; set; }
   public string Code { get; set; }
   ...
}
...
private Dictionary<int, SrvObject> _cache = new Dictionary<int, SrvObject>();
...
if (_cache.Values.Any(x => x.Code == codeToFind))
{
   var obj = _cache.Values.FirstOrDefault(x => x.Code == codeToFind);
   ...
}
else
{
   var obj = ReadObject(codeToFind);
   _cache.Add(obj.Id, obj);
   ...
}

Zacznijmy od tego, że mamy klasę, która modeluje jakąś encję z bazy danych i ta encja posiada zarówno identyfikator (wewnętrzny dla systemu) oraz kod, który można na przykład wyświetlić użytkownikowi.

Programista użył słownika, z kluczem w postaci identyfikatora, aby buforować już odczytane z bazy danych encje. Pierwsza rzecz jaka rzuca się w oczy to fakt, że kluczem jest identyfikator, a my wyszukujemy na podstawie kodu co wymaga iterowania po wszystkich zgromadzonych w słowniku obiektach. Wynika to z tego, że w większości przypadków posługujemy się identyfikatorem, a tylko czasami kodem i wspomniany kod został dodany później.

Załóżmy przez chwilę, że jest to ok. Druga rzecz na jaką należy zwrócić uwagę to fakt użycia metody Any i zaraz potem użycie FirstOrDefault. Jest to zbyteczne, kod ten robi dwa razy to samo, wystarczy zastosować tylko FirstOrDefault.

Wróćmy teraz do przeszukiwania słownika na podstawie kodu. Przy pokazanej implementacji musimy w najgorszym wypadku sprawdzić wszystkie obiekty w słowniku co ma złożoność liniową. Przy dużej liczbie obiektów w słowniku i częstych odwołaniach do niego jest to nieefektywne. W takim wypadku należy wprowadzić drugi słownik, w którym kluczem będzie kod. W zależności od sytuacji będziemy używać jednego albo drugiego słownika. Jeśli nie znajdziemy w którymś słowniku szukanego obiektu to dodajemy go do OBU słówników.

Przeprowadziłem mały test obu rozwiązań. Najpierw napisałem trzy metody wyszukujące encje:

• Znajdź na podstawie identyfikatora
• Znajdź na podstawie kodu bez dodatkowego słownika
• Znajdź na podstawie kodu z dodatkowym słownikiem

Początkowo słowniki są puste i generuję pewną liczbę N losowych identyfikatorów i kodów. Następnie znajduję te identyfikatory i kody korzystając z jednego słownika (Znajdź na podstawie identyfikatora + Znajdź na podstawie kodu bez dodatkowego słownika) oraz z dwóch słowników (Znajdź na podstawie identyfikatora + Znajdź na podstawie kodu z dodatkowym słownikiem). Oto wyniki:

Liczba N	Liczba unikalnych identyfikatorów	Czas (ms) dla dwóch słowników	Czas (ms) dla jednego słownika
100	63	3	4
500	320	2	4
1000	639	2	6
5000	3169	2	96
10000	6326	4	370
50000	31579	14	9190

Czas mierzyłem dla trybu Release. Jak widać nawet dla małej liczby elementów dwa słowniki są szybsze i to pomimo konieczności zarządzania jednym słownikiem więcej. Dla dużej liczby elementów przewaga jest miażdżąca. Jest to kolejny przykład, jak ważne są dobrze dobrane struktury danych.

Na koniec zwrócę jeszcze uwagę, że dwa słowniki oznaczają większe zapotrzebowanie na pamięć. W moich eksperymentach dwa słowniki dla 10 tyś elementów zużyły ~0.5MB więcej pamięci niż 1 słownik, dla 50 tyś elementów ~1.3 MB więcej, a dla 100 tyś elementów ~3.3 MB więcej.