2011-12-25 00:00:00

Świąteczne małpki

W ostatnim czasie w pracy spotkałem się z problemem który w uproszczeniu wygląda następująco:

Mamy listę obiektów typu Dział zawierających kolekcje obiektów typu Wydział zawierających kolekcję obiektów typu pracownik. Problemem do rozwiązania jest policzenie średniej Wieku wszystkich pracowników. Zakładamy dodatkowo że baza nie jest tuż za płotem tylko znajduje się za WebServicem do którego dokładanie metod jest z jakiś przyczyn problematyczne, więc nie możemy po prostu złożyć składnego selecta.

Problem wydaje się być banalny wystarczy zmontować coś takiego:

int ilosc = 0;
            int suma = 0;

            foreach (Dzial dzial in dzialy)
            {
                foreach (Wydzial wydzial in dzial.Wydzialy)
                {
                    foreach (Pracownik pracownik in wydzial.Pracownicy)
                    {
                        ilosc++;
                        suma += pracownik.Wiek;
                    }
                }
            }

            double wynik = ((float)suma) / ilosc;

Jest to jednak kod mało czytelny. A jeżeli operacja byłaby bardziej złożona niż średnia robi się jeszcze mniej ciekawie.

Rozwiązaniem jakie narzuca się bardziej doświadczonym programistom .Net jest użycie LINQ. Rozwiązanie to ma jednak wadę: nie chodzi na kolekcjach kolekcji tylko na jednowarstwowych kolekcjach. Można ten problem rozwiązać przez wyliczenie sobie pomocniczej kolekcji i na niej wykonania działania:

           List<Pracownik> pracownicy = new List<Pracownik>();

            foreach (Dzial dzial in dzialy)
            {
                foreach (Wydzial wydzial in dzial.Wydzialy)
                {
                    foreach (Pracownik pracownik in wydzial.Pracownicy)
                    {
                        pracownicy.Add(pracownik);
                    }
                }
            }

            double wynik = pracownicy.Average(p => p.Wiek);

Jest to rozwiązanie dobre jednak tworzenie i napełnianie listy w przypadku dużych kolekcji może okazać się zasobożerne.

Dlatego też postanowiłem zrobić świąteczny prezent sobie i innym programistom i stworzyć małpkę która za nas będzie biegała po drzewach i strukturach drzewo-podobnych. W ten sposób powstało rozszerzenie ExtractSubCollection biblioteki Szogun1987.Monkey. Po wykorzystaniu tej metody powyższy kod zostaje skrócony do 4 w miarę czytelnych linijek:

double result = 
                dzialy.ExtractSubCollection(d => d.Wydzialy)
                .ExtractSubCollection(w => w.Pracownicy)
                .Average(p => p.Wiek);

W bibliotece znajdują się dodatkowo rozszerzenia GetAllSubNodes, GetLeafs i GetRoot ułatwiające przeglądanie zwykłych (tj. składających się z węzłów spójnych pod względem typu) Drzew.

Najprostszą z nich jest GetRoot która jako parametr pobiera obiekt - węzeł drzewa i Funkcję zwracającą element nadrzędny węzła. Jako korzeń uznawany jest element dla którego powyższa funkcja zwróci null.

Kolejną metodą jest GetAllSubNodes pozwala ona na przeiterowanie po wszystkich węzłach znajdujących się poniżej węzła na którym wywoływane jest rozszerzenie (łącznie z nim samym). Jako drugi parametr przyjmowana jest funkcja zwracająca kolekcję elementów podrzędnych.

Ostatnią metodą w bibliotece jest GetLeafs pozwalająca przeiterować się po liściach drzewa z niego się wywodzących.

Dodatkowo w bibliotece znajduje się interfejs ITreeNode którego zaimplementowanie sprawia że do funkcji GetAllSubNodes, GetLeafs i GetRoot nie trzeba przekazywać funkcji wyciągających "najbliższych członków rodziny" danego elementu.

Dołożyłem starań aby biblioteka była napisana w sposób powodujący jak najniższe zużycie zasobów systemowych (pamięci i procesora). Podobnie jak w LINQ wszelkie funkcje i metody przekazywane do moich rozszerzeń są wywoływane w momencie iteracji.

Na koniec kwestie prawne, (Co by było wszystko na papierze znaczy się monitorze):

Zezwalam na nieodpłatne korzystanie ze skompilowanej wersji biblioteki. Biorę na siebie poprawki ewentualnie wykrytych błędów, przy czym nie naprawiam błędów wynikających ze współbieżnego dostępu do drzewa. Nie gwarantuję także wprowadzania ulepszeń.

Kodu źródłowego nie udostępnię w tym roku. Zakładam taką możliwość w pierwszym kwartale roku przyszłego (2012).

Biblioteki są do pobrania Tutaj

Tagi

C Sharp Programowanie

Komentarze:

2011-12-30 00:00:00

Tomek

Proponuje zapoznac sie z metoda LINQ o nazwie SelectMany(). Uzywajac jej kod moze wygladac np. tak (przy niewielkiej ilosci danych):

var pracownicy = dzialy.SelectMany(d => d.Wydzialy).SelectMany(w => w.pracownicy).ToArray();

var iloscPracownikow = pracownicy.Count();

var sredniWiek = pracownicy.Average(p => p.Wiek);

Jezeli pominales ja celowo to chetnie bym sie dowiedzial jakie sa zalety Twojej metody w stosunku do tej z LINQ :)

2011-12-30 00:00:00

th

Dlaczego nie możesz zrobić selecta jedynie po tabeli Pracownicy? Struktura drzewiasta do pisanego problemu nie jest potrzebna, skoro liczysz wszystkim pracownikom

2011-12-31 00:00:00

ttr

Dokładnie th, od pierwszego listingu kodu zachodzę w głowę "Ale po co ?". Select z tabeli Pracownicy powinien w zupełności wystarczyć

2011-12-31 00:00:00

td:)

Wytłumaczenie dlaczego select z tabeli pracownicy nie jest możliwy znajduje się na początku wpisu, ale od początku pomyślałem o tym, co napisał Tomek - co jest złego w SelectMany()?:)

2012-01-01 00:00:00

szogun1987

Select many jest jak najbardziej poprawny po prostu jakoś do nie znalazłem. Na szczęście pozostają jeszcze 3 pozostałe metody