Programisto, nie zapominaj o algorytmach! #3

Dzisiaj przed Wami kolejny wpis z algorytmiki. Dowiecie się czym są struktury danych i abstrakcyjne typy danych oraz poznacie podstawowe rodzaje ADT. Jesteś tutaj pierwszy raz? Zacznij od wprowadzenia do algorytmów oraz złożoności obliczeniowej.

Podczas tworzenia programów napotykamy na problem: jak mamy zapisać dane w pamięci? Bardzo często od dobrego lub złego wyboru zależy wydajność i sprawność naszego kodu.

Abstrakcyjne typy danych i struktury danych

Na początku musimy rozróżnić dwa pojęcia:

  • Abstrakcyjne typy danych (najczęściej nazywane ADT, czyli Abstract Data Types)
  • Struktury danych

Abstrakcyjne typy danych to pewnego rodzaju model matematyczny, opisujący pewną klasę już konkretnych struktur danych, które mają wspólne operacje. Abstrakcyjny typ danych definiujemy właśnie przez operacje, które możemy na nim wykonywać i pewne ograniczenia dla nich (na przykład czas operacji musi być liniowy) czy aksjomaty (warunki poprawności). Nie interesuje nas natomiast konkretna implementacja.

Z kolei struktura danych to już bardzo konkretna implementacja, która pomaga nam przechowywać dane w pamięci komputera. Co ciekawe, struktura danych może (ale nie musi) implementować jeden lub więcej ADT.

Idealnym przykładem są Javowe interfejsy i konkretne klasy. Spójrzmy na przykład interfejsu List. Jako że jest to interfejs, jest on abstrakcyjny, więc nie możemy utworzyć obiektu List.

Natomiast istnieją klasy, które faktycznie go implementują: AbstractList, AbstractSequentialList, Array List, Attribute List, CopyOnWriteArrayList, LinkedList, RoleList, RoleUnresolvedList, Stack, Vector.  Są to (prawie wszystkie) już konkretne struktury danych implementujące abstrakcyjny typ danych – listę, definiowany przez pewne konkretne operacje.

Zwykle, wybierając struktury danych najpierw wybieramy ADT, wiedząc jakich operacji będziemy potrzebować. Następnie decydujemy się na konkretną implementację optymalizując wydajność.

Podstawowe ADT

Tablica (Array)

Najprostszym przykładem struktury danych wbudowanej w przytłaczającą większość języków programowania jest stara, dobra tablica. Implementuje ona abstrakcyjny typ danych tablicy, który definiuje dwie operacje:

get(A,I) # pobranie elementu w tablicy A, pod indeksem I
set(A, I, V) # zapisanie elementu V w tablicy A, pod indeksem I

Operacje te, muszą spełniać dwa aksjomaty:

get(set(A, I, V), I) == V
get(set(A, I, V), J) == get(A, J) if I ≠ J

gdzie A to dowolna tablica, V dowolna wartość i I, J to indeksy tablicy. Wytłumaczmy je sobie.

Pierwszy z nich mówi tylko tyle, że gdy zapiszemy element pod dowolnym indeksem I, a potem pobierzemy zawartość spod tego indeksu – nie może ona ulec zmianie. Dosyć oczywiste.
Tłumacząc to na język programowania (tutaj akurat Ruby):

a = []
a[0] = 10
a[0] == 10 # to musi być prawdą!

Drugi natomiast mówi, że elementy o różnych indeksach są od siebie niezależnie i nie wpływają na siebie wzajemnie. Tłumacząc to na język programowania:

a = [1, 2, 3, 4]
element = a[1]
a[0] = 10
a[1] == element # to musi być prawdą!

Na bazie tablic zwykle budujemy kolejne, bardziej skomplikowane, własne struktury danych.

Kolejka (Queue)

Kolejka to kolejna abstrakcyjna struktura danych spełniająca warunek FIFO (first-in-first-out, czyli pierwszy na wejściu, pierwszy na wyjściu). Jako że kolejka daje nam tylko dwie operacje:

enqueue(q, e) # dodaje element e do kolejki q
dequeue(q) # pobiera element z kolejki q

zawsze pobierany jest z kolejki element dodany do niej najwcześniej. Ideę tę w jasny sposób przedstawia ilustracja:

alogrytmy3-01

Lista (list)

Wspomniana już wcześniej lista to ADT, która reprezentuje jakieś uporządkowane i skończone dane (z możliwymi powtórzeniami). Można to porównać do skończonego ciągu. W przeciwieństwie do tablic, listy mogą zmieniać dynamicznie swoją wielkość.

Lista musi implementować operacje:

cons(l, e) # dodaje element e na początku listy l
first(l) # zwraca pierwszy element z listy l
rest(l) # zwraca listę l bez pierwszego elementu

Wymagamy również spełnienia aksjomatów:

first(cons(e, l)) == e
rest(cons(e, l)) == l

Jako ćwiczenie – warto przemyśleć czy rozumiemy te aksjomaty i sprawdzić czy implementacje list w naszym ulubionym języku programowania je spełniają.

Drzewo (tree)

Drzewo to bardzo ważny ADT, który symuluje hierarchiczną strukturę. Wyobraźmy sobie firmę, gdzie każdy pracownik ma dokładnie jednego szefa i wszyscy mają szefów oprócz prezesa. Posługując się tym przykładem elementy nadrzędne (szef) nazywamy rodzicem, a podrzędne – dzieckiem. Najlepiej wyjaśnia to ilustracja:

binary_tree-01

Jako ADT najprościej zdefiniować drzewo w postaci struktury, gdzie każdy węzeł ma wartość i może mieć powiązane ze sobą dzieci (znające rodzica), które też są drzewami. Każdą strukturę, która spełnia taką definicję nazwiemy drzewem. Zatem lista też będzie drzewem – tylko dosyć trywialnym.

Zbiór drzew nazywamy często lasem.

Do drzew wrócimy przy strukturach danych – wtedy okazują się być dużo ciekawsze. Ale o tym dowiecie się w jednej z następnych części 😉

Stos (stack)

Stos to ADT, który jest bardzo podobny do listy. Jednak jest mały wyjątek – jest to struktura typu LIFO (last-in, first out, czyli ostatni wchodzi, pierwszy wychodzi). Możemy dodawać do niego elementy, ale pobieramy z niego zawsze element najnowszy.

Stos udostępnia nam dwie operacje:

push(s, e) # dodaje element na górę stosu
pop(s) # pobiera element z góry stosu

spełniające aksjomat:

pop(s, push(s, e)) == e # czyli pobieramy zawsze najnowszy element 

W języku programowania, na przykład JavaScript, zapisalibyśmy ten warunek stosu (na bazie zwykłej tablicy) w następujący sposób:

var stack=new Array();
element = "A";
stack.push(element);
stack.pop() === element // true

Warto wspomnieć, że stos jest niesamowicie ważny w kontekście wewnętrznych implementacji języków programowania – jako narzędzie do alokowania pamięci i dostępu do niej.

Jeżeli chcesz dowiedzieć się więcej o stosie, koniecznie przeczytaj artykuł.

Podsumowanie

Przedstawiłem dzisiaj listę (oczywiście mocno niewyczerpującą) ciekawszych do omówienia abstrakcyjnych typów danych. W dalszym odcinkach przedstawimy sobie już konkretne struktury danych, zbudujemy część z nich i przyjrzymy się ich wydajności w typowych zastosowaniach.

Site Footer

Sliding Sidebar