Trwałe struktury danych

07.06.2010 - Filip Sieczkowski
TrudnośćTrudnośćTrudnośćTrudność

W tym artykule opowiem nieco o zupełnie odmiennym od standardowego podejściu do tworzenia struktur danych ─ strukturach trwałych, a także przedstawię implementacje kilku najpopularniejszych struktur ─ stosów, drzew wyszukiwań binarnych i kolejek ─ w wersji trwałej. Struktury takie mają szerokie zastosowanie w językach programowania funkcyjnego, w których zmiana stanu danych jest silnie odradzana lub nawet w ogóle niemożliwa, a także w problemach, w których niezbędne jest zachowanie poprzednich wersji struktury.

Zazwyczaj implementując struktury danych, potrzebne do rozwiązania problemów algorytmicznych nie interesuje nas, jak zmieni się ich wewnętrzny stan (oczywiście pod warunkiem że nie zostaną zaburzone odpowiednie niezmienniki i ─ jeśli piszemy w C/C++ ─ zwolnimy odpowiednią część pamięci). Czasem jednak pojawiają się problemy, w których nie możemy struktur danych traktować tak dowolnie. Najczęściej pojawiającym się ograniczeniem jest konieczność zachowania w trakcie zmiany struktury również jej poprzedniej wersji. Struktury danych, które mają taką własność nazywamy stałymi (ang. persistent). Jak się okazuje, wiele technik, które doskonale działają dla standardowych ─ ulotnych ─ struktur danych, w przypadku trwałym zawodzi, warto zatem zapoznać się ze sposobami na rozwiązanie tych problemów, szczególnie że same metody są dość często ciekawe.

"Jak to w ogóle wygląda?", czyli stos

Pierwszą z przedstawionych tu struktur będzie stos, zaimplementowany w postaci jednokierunkowej listy łączonej. Listy takie są chyba najważniejszą trwałą strukturą danych, jak zobaczymy, większość innych struktur również będzie z nich korzystać. Poniżej przedstawiona jest trwała implementacja takich jednokierunkowych list.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Empty{};
typedef int Elem;
class List {
private:
  List() : hd(0), tl(NULL) {}
  Elem hd;
  List* tl;
public:
  List(Elem _head, List* _tail) : hd(_head), tl(_tail) {}
  Elem head(){
    return hd;
  }
  List * tail(){
    return tl;
  }
};

Jak widać, zarówno w przypadku tworzenia listy publicznym konstruktorem ─ czyli dołączania do niej elementu ─ jak i przy ``usuwaniu'' pierwszego elementu listy (w funkcji tail), stara struktura danych pozostaje niezmieniona. Dobrze widać to na następującym przykładzie.

1
2
3
4
5
6
List * a,b,c,d,e;
a = new List(3, NULL);
b = new List(4, a);
c = new List(7, a);
d = new List(5, c);
e = d->tail();

Po jego wykonaniu struktura w pamięci będzie następująca.

Teraz pozostaje nam już tylko użyć listy jako stosu, czyli zaimplementować odpowiednie funkcje:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
typedef List * Stack;
 
Stack empty = NULL;
Stack push(Elem hd, Stack tl){
  return new List(hd, tl)
}
Elem top(Stack lst){
  if(lst == empty) throw Empty();
  return lst->head();
}
Stack pop(Stack lst){
  if(lst == empty) throw Empty();
  return lst->tail()
}

Zarządzanie pamięcią

Jak widać na rysunku, dzięki temu, że nie zmieniamy struktury wewnętrznej naszej listy, nie musimy kopiować jej, kiedy w różnych miejscach programu potrzebujemy jej kopii w różnym stanie ─ znaczna część struktury może być współdzielona. Nastręcza to jednak duże trudności kiedy struktura nie jest już potrzebna ─ być może inne kopie wciąż jeszcze jej używają. Rozwiązania są dwa: można użyć języka, który ─ jak Java ─ sam usuwa niepotrzebne obiekty albo rozszerzyć listę tak, żeby sama wiedziała, kiedy nie jest już potrzebna i mogła się usunąć.

W tym celu wystarczy dodać do klasy dodatkowe pole typu int, które przechowywać będzie ilość odwołań do obiektu. Gdy zapamiętujemy gdzieś wskaźnik do naszego obiektu, inkrementujemy wartość odpowiedniego pola, a gdy obiekt przestaje być potrzebny ─ dekrementujemy ją. Jeśli kiedykolwiek wartość osiągnie 0, wiemy że nikt już takiego obiektu nie potrzebuje i możemy go bezpiecznie usunąć. Jeśli piszemy w C++, możemy użyć specjalnych wskaźników współdzielonych z biblioteki boost, implementujących taką właśnie technikę zarządzania pamięcią, o tym jak ich używać można przeczytać tu.

Nie możesz wysyłać i oglądać rozwiązań tego zadania ponieważ nie jesteś zalogowany. Zaloguj się lub załóż konto.
0
Twoja ocena: Brak

Copyright © 2008-2010 Wrocławski Portal Informatyczny

design: rafalpolito.com