Programisto, nie zapominaj o algorytmach! #4

Witajcie w kolejnym odcinku naszego cyklu algorytmicznego. Dzisiaj zobaczymy dlaczego stos jest taki ważny zaglądając do środka komputera. Przyjrzymy się bliżej konkretnym implementacjom struktury danych stosu i zobaczymy parę najprostszych przykładów zastosowań. Wreszcie, dowiemy się jaka jest złożoność obliczeniowa pewnych operacji w wybranych implementacjach. To do dzieła!

W ramach przypomnienia – stos to ADT które definiuje tylko dwie operacje:

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

Jak dokładnie będzie to zrealizowane? Jaka będzie wydajność tych operacji? To już szczegóły implementacji, o których dowiesz się na końcu artykułu.

A tymczasem porozmawiajmy o stosie wewnątrz komputera.

Stos wewnątrz komputera

Czy używaliście kiedykolwiek stosu w programowaniu? Na to pytanie pewnie część z was odpowie przecząco. Zapytam inaczej – czy kiedykolwiek wywoływaliście jakąś funkcję? Albo wręcz napisaliście dowolny program? Jeżeli odpowiedzieliście „tak” – gratulacje, używaliście stosu! Przyjrzyjmy się zatem dlaczego.

Gdy uruchamiamy dowolny program (pomijając bardzo rzadkie przypadki) system operacyjny rezerwuje pewną część pamięci na stos. Gdy wywołujemy jakąś funkcję, na stos trafiają jej argumenty, a system przenosi wskaźnik stosu w górę – rezerwując miejsce dla pracy tej funkcji. Gdy kończy swoje działanie, te elementy są zdejmowane ze stosu i wracamy do poprzedniej sytuacji. Jest to najczęstsze działanie dla języków wysokiego poziomu.

Z tym działaniem powiązany jest znany błąd stack overflow przy źle napisanej rekurencji – dodając kolejne elementy do stosu trafiamy w końcu na limit pamięci. Zaciekawieni tematem znajdą więcej informacji na ten temat na Wikipedii .

Zastosowanie stosu wyższego poziomu

Ale po co mi tak faktycznie ten stos? Najprościej możemy sobie to wyobrazić na przykładzie odwracania tablicy przy użyciu stosu (w JavaScript):

function reverseArr(array) {
  var reversed = [];
  var e;
  while((e = array.pop()) !== undefined) {
    reversed.push(e);
  }
  return reversed;
}

Zauważcie, że nigdzie nie używamy tutaj innych operacji na tablicach niż pop i push – czyli korzystamy tylko z ich funkcji jako stosu!

Innym przykładem jest obliczanie wyrażeń podanych w odwrotnej notacji polskiej. 

Odwrotna notacja polska

ONP to dosyć interesujący sposób zapisu wyrażeń arytmetycznych w których operator (czyli np. + czy –) umieszczamy po operandach (czyli np. liczbach). Przykładowe wyrażenia możecie zobaczyć w tabelce niżej.

Tradycyjny zapis algebraiczny

(notacja infiksowa)

Odwrotna notacja polska

(zapis postfiksowy)

2 + 3 2 3 +
(2+3)*5 2 3 + 5 *
(10+3)*(5-2) 10 3 + 5 2 – *

Wyliczenie wartości wyrażenia w notacji ONP tradycyjnie wykonuje się przy pomocy stosu, według następującego algorytmu:

  • Dla wszystkich symboli z wyrażenia ONP wykonuj:
    • jeśli i-ty symbol jest liczbą, to odłóż go na stos
    • jeśli i-ty symbol jest operatorem to:
      • zdejmij ze stosu jeden element (ozn. a)
      • zdejmij ze stosu kolejny element (ozn. b)
      • odłóż na stos wartość b operator a
    • jeśli i-ty symbol jest funkcją to:
      • zdejmij ze stosu oczekiwaną liczbę parametrów funkcji(ozn. a1an)
      • odłóż na stos wynik funkcji dla parametrów a1an
  • Zdejmij ze stosu wynik.

Mówiąc prościej – gdy wczytany element jest liczbą, to zapisujemy ją na stos. W przeciwnym wypadku należy wykonać działanie arytmetyczne na 2 ostatnich liczbach na stosie. Wartość wyrażenia znajduje się na stosie.

Przykład

Obliczymy po kolei wartość przykładowego wyrażenia z tabelki wyżej: 10 3 + 5 2 – * (na palcach możemy oczywiście policzyć, że powinno wyjść 39). Zatem:

Krok Wejście Operacja Pozostałe wyrażenie Po operacji
1 10 push(10) 3 + 5 2 – * 10
2 3 push(3) + 5 2 – * 10 3
3 + push(pop() + pop()) = push(10 + 3) 5 2 – * 13
4 5 push(5) 2 – * 13 5
5 2 push(2) – * 13 5 2
6 push(pop() – pop()) = push(5 – 2) * 13 3
7 * push(pop() * pop()) = push(13 * 3) 39

Krok po kroku obliczyliśmy wyrażenie. W dodatku, nie trzeba było stosować żadnych nawiasów do pełnej jednoznaczności. Jako pomocniczej struktury używaliśmy danych stosu, dzięki któremu całość była tak prosta. Nie musieliśmy się martwić indeksami elementów, alokacją pamięci etc. To wszystko robił za nas wewnętrznie stos – przerzuciliśmy część naszej pracy na gotową strukturę. Jest to jedna z kluczowych cech struktur danych. Dzięki ich wewnętrznej budowie późniejsza implementacja jest dużo prostsza.

Złożoność obliczeniowa operacji na stosie

Jak wiemy z poprzedniej części cyklu stos to ADT i możemy go implementować w różny sposób. Przyjrzyjmy się dwóm najbardziej popularnym sposobom implementacji.

Implementacja stosu za pomocą linked-listy

Linked lista to struktura danych o której możemy najprościej myśleć jak o zbiorze danych z kolejnością – dzięki faktowi, że każda komórka oprócz danych, zawiera również informację o następnym elemencie. Czyli w poniższym przykładzie widzimy listę [12, 99, 37].

Jest to jedna z implementacji używanych dla stosu. Dodawania i usuwanie elementów z wierzchu jest tutaj proste – wystarczy usunąć wskaźnik i powiedzieć, że lista zaczyna się w innym miejscu. Możemy też „doczepić” nowy element i przesunąć wskaźnik początku. Minusem jest fakt, że dodanie każdego elementu wymaga alokacji nowego kawałka pamięci, co może być nieco kosztowne.

Implementacja stosu za pomocą tablicy dynamicznej

Tablica dynamiczna (zwana czasem ArrayList) to struktura danych, która się powiększa, aby pomieścić kolejne elementy. Dzieje się to niezależnie od programisty, który korzysta z tablicy.

Dodawanie elementów odbywa się w zamortyzowanym czasie O(1) (na poniższym rysunku symbol ramki), natomiast w najgorszym przypadku będzie to O(n) – kiedy akurat trafimy na wolniejszy moment w którym musi wystąpić wewnętrzne powiększenie tablicy (oznaczone ikonką żółwia).

Czas zamortyzowany O(1) oznacza, że n operacji wykona się w czasie O(n). Jednakże nie ma gwarancji, że któraś z operacji nie zajmie więcej czasu.

Operacja pop to również czas O(1) (chyba, że chcemy odzyskiwać zajętą pamięć, wtedy jest to zamortyzowany koszt O(1)).

Oczywiście możemy wymyślić również inne implementacje stosu, które nie będą mieć zbyt wielkiego sensu – na przykład implementacja na bazie tablicy hashującej w Ruby:

def initialize
    @h = {}
  end
  
  def push(e)
    @h[e] = true
  end
  
  def pop
    e = @h.keys.last
    @h.delete(e)
    e
  end
  
  
end

Natomiast jest to wciąż poprawna implementacja (nawet jeżeli niewydajna czy nieco dziwna), ponieważ spełnia warunki stosu.

Stay tuned, kolejna część już wkrótce ;).

Zajrzyj do wcześniejszych wpisów o algorytmice:

 

Site Footer

Sliding Sidebar