Visual Studio 2010 - Proste struktury danych i profiler Udostępnij na: Facebook

Autor: Michał Sobieraj

Implementacja przykładowych struktur danych w C#

Celem tego artykułu jest przedstawienie programistom podstawowych struktur danych i pokazanie, jak zaimplementować je w C#. Mimo że język ten zawiera dużą liczbę różnego rodzaju kontenerów, które dostarczają podstawowe struktury danych i te bardziej zaawansowane, każdy programista powinien potrafić zaimplementować je na własną rękę, aby samodzielnie rozwiązywać szeroką gamę problemów algorytmicznych. Od wyboru odpowiedniej struktury danych często zależy szybkość działania naszego programu, zużycie pamięci, a także łatwość, z jaką później możemy zmodyfikować ten program. W ramach niniejszego artykułu omówimy takie struktury jak lista jednokierunkowa, stos i drzewa.

Jako pierwszą omówimy listę jednokierunkową, ponieważ to chyba najbardziej podstawowa struktura danych, jednocześnie bardzo często wykorzystywana. Listy są oszczędne, jeśli chodzi o wykorzystanie pamięci, i pozwalają na grupowanie dowolnej liczby elementów. Dynamiczny przydział pamięci powoduje, że w odróżnieniu od tablic wielkość listy nie jest z góry określona i może się dowolnie rozszerzać.

Zamieszczony wyżej rysunek pokazuje schematycznie zasadę działania listy. Każdy kolejny element wskazuje na następny, aż do końca listy, który jest oznaczony za pomocą wartości null. Operacje dodawania elementów do listy mają złożoność O(1), natomiast uzyskanie elementu z listy oraz jej proste przeglądanie − O(n). A oto struktura pojedynczego elementu listy:

class Element
{
    public int wartosc;
    public Element next;
    public Element(int w)
    {
        wartosc = w;
        next = null;
    }
}

Jak widać, nasza klasa odpowiada dokładnie elementowi ze schematu. Ma też konstruktor, który inicjuje element. Zbudujemy teraz klasę Lista, która będzie miała dwa pola typu Element, oznaczające wskaźnik początku i końca listy. Możliwa jest także implementacja z jednym wskaźnikiem pokazującym początek listy. W takim wypadku dodawanie do końca listy będzie miało złożoność O(n), zamiast O(1).

class Lista
{
    public Element glowa;
    public Element ogon;
    public Lista()
    {
        glowa = null;
        ogon = null;
    }
}

Gdy mamy już zdefiniowaną strukturę listy, czas napisać podstawowe metody, dzięki którym będziemy przeprowadzać operacje na liście. Mowa tu o funkcjach: dodającej element do listy, odejmującej i takiej, która pozwoli nam przejrzeć zawartość listy.

public void dodaj(int wart)
{
    Element q = new Element(wart);
    if (glowa == null)
    {
        glowa = ogon = q;
    }
    else
    {
        ogon.next=q;
        ogon = q;
    }
}

Funkcja dodająca jest bardzo prosta. Najpierw tworzymy nowy element, następnie − jeśli lista jest pusta − ustawiamy wskaźnik początku i końca listy na tym elemencie. W przeciwnym wypadku dodajemy element do końca listy.

public bool usun(int wart)
{
    if (glowa == null)
    {
        return false;
    }
    else
    {
        Element cur = glowa;
        Element przed = null;
        while (cur != null && cur.wartosc != wart)
        {
            przed = cur;
            cur = cur.next;
        }
        if (cur == null)
            return false;
        if (cur == glowa)
        {
            glowa = cur.next;
            return true;
        }
        else
        {
            if (cur.next == null)
            {
                ogon = przed;
                przed.next = null;
                return true;
            }
            else
            {
                przed.next = cur.next;
                return true;
            }
        }
    }
}

Usuwanie elementów z listy jest już nieco bardziej skomplikowane. Najpierw musimy znaleźć pozycję, na której znajduje się usuwany element. Następnie, zależnie od tego czy znajduje się na początku, w środku, czy na końcu listy, odpowiednio usuwamy go.

public void show()
{
    Element cur = glowa;
    while(cur != null)
    {
        Console.Write(cur.wartosc + " ");
        cur= cur.next;
    }
}

Ostatnia ze wspomnianych funkcji jest najprostsza. W pętli while przeglądamy elementy, aż dojdziemy do końca listy. Implementacja listy jednokierunkowej nie należy do skomplikowanych, natomiast warto się zastanowić, czy opłaca się pisać własną klasę, gdy mamy do dyspozycji gotowy kontener List. Aby rozstrzygnąć ten problem, sprawdzimy obie klasy pod względem wydajności. Wykorzystamy do tego profiler w VS 2010.

Wynik ukazuje nam przeszło dwukrotną przewagę w tym zakresie listy ze standardowej biblioteki nad naszą listą. Fakt ten nie pozostawia nam złudzeń co do sensu implementowania struktury na własną rękę. Jak można było się spodziewać, wbudowany kontener oferuje wyższą wydajność.

Kolejną strukturą, którą się zajmiemy, jest stos. To struktura, do której mamy dostęp tylko od strony wierzchołka, inaczej mówiąc: typu LIFO (Last in First Out). Stos jest szeroko wykorzystywany przez system operacyjny. Każdy program odkłada na nim zmienne lokalne, argumenty funkcji i adresy powrotu z funkcji. Dostęp do struktury jest możliwy jedynie za pomocą dwóch funkcji: push, która odkłada elementy na stosie, i pop, która pobiera te elementy z wierzchołka stosu. Nasz stos zbudujemy na podstawie tablicy, której rozmiar ustalamy podczas tworzenia obiektu klasy. Tablica będzie wykorzystywać nowy typ dynamic pozwalający wrzucać na stos elementy dowolnego typu, pomijający przy tym wszelkie rzutowanie. Powoduje to jednak niewielki spadek wydajności, ponieważ kod jest obsługiwany przez DLR podczas uruchamiania aplikacji.

class Stos
{
    private int szczyt;
    private int rozmiar;
    private dynamic[] s;
    public Stos(int r)
    {
        szczyt = 0;
        rozmiar = r;
        s = new dynamic[r];
    }
    public bool push(dynamic n)
    {
        if (szczyt < rozmiar)
        {
            s[szczyt++] = n;
            return true;
        }
        else return false;
    }
    public bool pop(ref dynamic v)
    {
        if (szczyt > 0)
        {
            v = s[--szczyt];
            return true;
        }
        else return false;
    }
}

Gdy przyjrzymy się bliżej funkcjom obsługującym stos, zobaczymy, że zachowują idee LIFO. Elementy zawsze trafiają na szczyt stosu i stamtąd są zabierane. Dostęp do pozostałych składowych klasy powinien być zablokowany ze względu na bezpieczeństwo użytkowania.

Na koniec porównamy nasz stos z klasą generyczną Stack<>. Ponieważ przyjmuje elementy dowolnego typu, klasę Stack sprecyzujemy jako typ object.

Okazuje się, że nasza klasa jest przeszło dwukrotnie szybsza od generycznej. Dopiero gdy zadeklarujemy ową klasę, aby przechowywała typ prosty, np. int czy char, klasa standardowa będzie szybsza od naszej własnej implementacji.

Następną strukturą, z którą każdy programista powinien być zaznajomiony, jest drzewo. Nasze rozważania skupimy na drzewach binarnych, a dokładnie − na szczególnym przypadku drzewa binarnego: binarnym drzewie poszukiwań, w skrócie BST. Struktura węzła w drzewie binarnym ma budowę podobną do elementu listy, z tą różnicą, że zamiast zmiennej wskazującej na następny element ma dwie zmienne wskazujące na prawe i lewe poddrzewo.

class wezel
{
    public int wartosc;
    public wezel lewy;
    public wezel prawy;
    public wezel(int w)
    {
        wartosc = w;
        lewy = prawy = null;
    }
}

BST ma strukturę drzewa binarnego, a poszczególne węzły są w nim tak rozłożone, że znajdujące się na lewo od rodzica mają mniejszą wartość, a na prawo od rodzica − większą. Dzięki temu drzewo automatycznie sortuje ciąg liczb, który w nim umieszczamy.

Drzewa mają szerokie zastosowanie w informatyce, wykorzystywane są między innymi w takich dziedzinach jak algorytmika, kryptografia oraz we wszelkich analizach semantycznych wyrażeń. Operacje na drzewie mają złożoność O(logn), jeśli więc często wyciągamy informacje z naszej struktury, drzewo jest lepszym rozwiązaniem od listy, w której złożoność wynosi O(n). Klasa implementująca nasze drzewo będzie miała jedną zmienną typu wezel, odpowiadającą korzeniowi drzewa. Zaimplementujemy teraz funkcję, która będzie tworzyła drzewo BST.

public void dodaj(int w)
{
    wezel nowy = new wezel(w);
    wezel x = root;
    wezel y = null;
    while (x != null)
    {
        y = x;
        if (nowy.wartosc < x.wartosc) x = x.lewy;
        else x = x.prawy;
    }
    if (y == null) root = nowy;
    else
    {
        if (nowy.wartosc < y.wartosc) y.lewy = nowy;
        else y.prawy = nowy;
    }
}

Funkcja na początku tworzy nowy węzeł i ustawia dwie zmienne wskaźnikowe na węzeł, w którym się znajdujemy, i poprzedni. Następnie szukamy odpowiedniego miejsca dla naszego elementu, przechodząc po drzewie odpowiednio w lewo − jeśli wartość nowego węzła jest mniejsza od wartości węzła x, i w prawo − jeśli jest większa. Gdy znajdziemy miejsce, w którym nasz węzeł powinien się znaleźć, dopisujemy go.

Kiedy mamy już stworzone drzewo, musimy zaimplementować funkcję, za pośrednictwem której będziemy je przeglądać. Drzewo można przeglądać na trzy sposoby, w kolejności: preorder, inorder i postorder. Wybierzemy inorder, ponieważ, wyświetlając najpierw lewą gałąź, następnie prawą, otrzymujemy automatycznie posortowany ciąg wartości.

public void inorder(wezel r)
{
    if (r != null)
    {
        inorder(r.lewy);
        Console.Write(r.wartosc + " ");
        inorder(r.prawy);
    }
}

Najłatwiej stworzyć taką funkcję za pomocą rekurencyjnych wywołań. W naszym przypadku najpierw będzie wyświetlana lewa strona drzewa, następnie korzeń, a na końcu prawa strona, co da nam posortowany ciąg.

Ostatnią strukturą, z którą się zapoznamy, są grafy. Ponieważ można o nich napisać książkę, w tym artykule podamy tylko wprowadzenie do teorii grafów. Bez tej struktury nie byłoby można rozwiązać wielu problemów algorytmicznych Dzięki swojemu szerokiemu zastosowaniu teoria grafów stała się osobnym działem matematyki, której rozwój ma duży wpływ na wiele rozwiązań informatycznych. Grafy sprawdzają się szczególnie w przypadku wszelkich problemów z odnajdywaniem optymalnych ścieżek, np. wskazywaniem drogi przez GPS czy przyspieszeniem transmisji danych w rozbudowanych sieciach komputerowych. Wiele problemów modeluje się w postaci grafów, dzięki czemu możemy rozwiązać je w prostszy i często optymalny sposób.

Graf składa się z zbiorów wierzchołków oraz krawędzi, którymi wierzchołki mogą być połączone. Wierzchołki są ponumerowane i mogą stanowić reprezentację jakiś obiektów, natomiast krawędzie przedstawiają relacje między nimi. Grafy w większości przypadków implementuje się na dwa sposoby. Pierwszym jest macierz sąsiedztwa, w której i-ty wiersz i j-ta kolumna reprezentują liczbę krawędzi między wierzchołkami i oraz j. W przypadków grafów prostych, czyli takich, które mają nie więcej niż jedno połączenie między wierzchołkami, będą to wartości boolowskie. Macierz możemy przedstawić za pomocą tablicy dwuwymiarowej:

int[ , ] Graf= new int[nmax, nmax];

Teraz tylko w odpowiednich kolumnach i wierszach zaznaczamy istnienie krawędzi między tymi wierzchołkami. Implementacja za pomocą macierzy sąsiedztwa jest niewątpliwie najszybszą implementacją grafów, ponieważ wykonujemy tu jedynie operacje na tablicy, która zapewnia wysoką wydajność. Wadą tego rozwiązania jest fakt, że musimy z góry znać liczbę wierzchołków, które będzie zawierać graf.

Drugim sposobem przechowywania grafów jest lista sąsiedztwa: każdy wierzchołek ma przypisaną listę wierzchołków, z którymi łączy go krawędź. Do implementacji można wykorzystać listę dwuwymiarową lub tablicę list. Do naszej implementacji wybierzemy tablicę list, gdyż to rozwiązanie szybsze, a jednocześnie kod będzie prostszy i czytelniejszy. Do implementacji grafu zastosujemy strukturę Element, którą uprzednio zbudowaliśmy przy tworzeniu listy:

class Graf
{
    public const int n_max = 100;
    public Element[] G;

    public Graf()
    {
        G = new Element[n_max];
    }
}

Kolejnym krokiem będzie stworzenie funkcji dodawania krawędzi między wierzchołkami:

public void dodaj(int x, int y)
{
    Element w = new Element();
    w.next = G[x - 1];
    w.wartosc = y;
    G[x - 1] = w;

    w = new Element();
    w.next = G[y - 1];
    w.wartosc = x;
    G[y - 1] = w;
}

Ponieważ tworzony przez nas graf jest nieskierowany, najpierw dodajemy element do listy sąsiedztwa wierzchołka x, a następnie do listy sąsiedztwa wierzchołka y. Teraz porównamy obydwa rozwiązania za pomocą profilera. Wynik testów jest następujący:

Procedura Grafy.Graf.dodaj() reprezentuje funkcje dodawania krawędzi do listy sąsiedztwa, natomiast funkcja Grafy.Graf2.dodaj() reprezentuje dodawanie krawędzi do macierzy. Jak widzimy, implementacja oparta na tablicy dwuwymiarowej jest cztery razy szybsza od rozwiązania z tablicą list. Gdybyśmy wykorzystali listę list, wydajność spadłaby jeszcze bardziej, ponieważ przeglądanie listy ma złożoność O(n).

Podsumowując: implementacja podstawowych struktur danych w C# ze względu na jego wysoką abstrakcję jest dość prosta, bo nie musimy się martwić wskaźnikami, np. w C++. Niemniej struktury mogą stracić trochę na wydajności z powodu używania bezpiecznych typów danych. Jak pokazuje przykład, stworzenie własnej struktury, która może wydawać się lżejsza od kontenera dostępnego w bibliotece standardowej, nie zawsze jest dobrym pomysłem. W praktyce bowiem nasza struktura okazuje się wolniejsza z powodu optymalizacji klas generycznych. Nie zrażając się tym faktem, każdy programista powinien poznać metodę implementowania takich struktur na własną rękę, aby dobrze zrozumieć mechanizmy, jakimi się rządzą, i być niezależnym od gotowych rozwiązań.