Trwałe struktury danych

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

Kolejki: pierwsze starcie

Standardowa ulotna implementacja kolejek (zarówno jedno- jak i dwustronnych) opiera się na łączonej liście dwukierunkowej. Jednak łatwość poruszania się po takiej liście, która powoduje że jest ona świetną strukturą ulotną, całkowicie uniemożliwia jej wykorzystanie w trwałym środowisku. Przypomnijmy sobie nasz poprzedni przykład drzew: podczas zmiany stanu struktury musieliśmy skopiować wszystkie wierzchołki, z których osiągalny był nowo dodany element. Ale w liście dwukierunkowej każdy element jest osiągalny z każdego innego, więc musielibyśmy za każdym razem kopiować całą strukturę. Takie rozwiązanie oczywiście nie wchodzi w rachubę.

Okazuje się, że kolejki są jedną z najtrudniejszych do skutecznego zaimplementowania trwałych struktur danych (z klasycznych struktur trudniejsze są chyba tylko tablice); ich implementacji poświęcimy resztę artykułu.

Oczywiście, używając zbalansowanych drzew, możemy użyć kolejki priorytetowej zaimplementowanej z ich wykorzystaniem jako zwykłej kolejki FIFO. Jednak czas działania operacji $ \Theta(\log n) $, który w ten sposób osiągniemy, nie jest satysfakcjonujący. Poniżej przedstawimy kolejkę działającą w zamortyzowanym czasie stałym i zobaczymy, czemu nie rozwiązuje ona naszych problemów. Zobaczymy też jak taką kolejkę przerobić na kolejkę dwustronną. W ostatniej części artykułu otrzymamy kolejkę, której wszystkie podstawowe operacje działają w czasie stałym, pozostawiając jako zadanie czytelnikowi zmierzenie się z kolejką dwustronną.

Kolejka zamortyzowana

Kluczowa dla konstrukcji naszej pierwszej kolejki jest obserwacja, że tak naprawdę w kolejce nie wykonuje się operacji znacząco różnych od stosu ─ po prostu jedną z operacji wykonujemy na innym końcu struktury, niż drugą. Pomysł jest tak naprawdę prosty: wystarczy trzymać początek kolejki w odwrotnej kolejności, niż koniec! W ten sposób i początek, i koniec kolejki może być listą, jak na poniższym rysunku.

Pozostaje pytanie, co zrobić, kiedy lista ``przednia'', z której usuwamy, skończy się. Ale wtedy wystarczy tylko odwrócić ``ogon'' kolejki, jak na rysunku.

Oczywiście odwrócenie listy wymaga obejrzenia wszystkich jej elementów, więc zabiera $ O(n) $ jednostek czasu. Jednak żeby trzeba było obrócić listę długości $ n $, musieliśmy $ n $ razy włożyć do kolejki element (co kosztowało $ O(1) $ jednostek czasu), a więc mogliśmy na to odwrócenie listy ``zaoszczędzić'' w czasie wcześniejszych operacji. Poniżej przedstawiamy implementację takiej kolejki, z wykorzystaniem wcześniej zaprezentowanych list.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
typedef const pair<const List *, const List *> Queue;
 
List * reverse(List * s){ // Pomocnicza funkcja, odwracanie listy
  List * ret = nil;
  while(s != NULL) {
    ret = new List(s->head, ret);
    s = s->tail;
  }
  return ret;
}
 
Queue empty = make_pair(nil, nil);
 
Queue check(List * f, List * b){
  // Pomocnicza funkcja odwracająca tylną listę jeśli przednia się skończyła
  if (f == nil && b != nil){
    return make_pair(reverse(b), nil);
  }
  return make_pair(f,b);
}
Queue insert(int elem, Queue q){
  return check(q.first, new List(elem, q.second));
}
int front(Queue q){
  return q.first->head();
}
Queue tail(Queue q){
  return check(q.first->tail() , q.second);
}

Porażka amortyzacji

Powyższa implementacja jest ładna i prosta, jednak niestety nie nadaje się do naszych zastosowań: nie można używać dawnych wersji kolejki. Wyobraźmy sobie, że zmienna $ q $ pokazuje na kolejkę, w której przedniej liście pozostał dokładnie jeden element, zaś tylna lista jest długa. Weźmy teraz sekwencję instrukcji:

1
2
3
for (i=0;i<k;i++){
  t[i]=tail(q);
}

Taka sekwencja spowoduje, że tylną listę odwrócimy $ k $ razy a więc koszt zamortyzowany będzie rzędu $ O(n) $.

Istnieją metody, pozwalające na tworzenie trwałych struktur o koszcie zamortyzowanym, jednak są one wygodniejsze do stosowania w funkcyjnych językach programowania: w dalszej części artykułu skupimy się na innym, bardziej bezpośrednim, sposobie naprawienia naszych kolejek.

Kolejki dwustronne

Kolejki dwustronne, zwane z angielska dequeue (od double-ended queue), są wariantem kolejek, w którym elementy można wstawiać i usuwać z każdej ze stron. Naturalną implementacją ulotnej kolejki jest oczywiście lista dwustronna, której podobnie jak przy zwykłej kolejce nie możemy użyć, jeśli chcemy mieć struktury trwałe. Zastosowanie przedstawionej wyżej zamortyzowanej kolejki bezpośrednio również nie jest możliwe ─ po obróceniu listy tylnej na przednią nie moglibyśmy usuwać elementów z końca kolejki. Okazuje się jednak, że trzeba zmienić bardzo niewiele: wystarczy zamiast przekładać całą listę ``wyrównać'' listę przednią i tylną. Żeby wyrównać długości list trzeba wiedzieć ile elementów trzeba przełożyć: najłatwiej to osiągnąć rozszerzając stan obliczeń o dodatkową liczbę, mówiącą o różnicy długości list. Wtedy, jeśli jedna z list się skończy, będziemy znali długość drugiej, a zatem będziemy mogli przenieść jej połowę na odpowiednią listę. Implementacja, również wykorzystująca poprzednio zdefiniowane struktury danych, wygląda następująco:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
typedef const pair<const int, Queue> Dequeue;
 
Queue rev_n(const int n, List * f, List * b){
  if(n>0) return rev_n(n-1, pop(f), push(top(f), b));
  if(n<0) return rev_n(n+1, push(top(b), f), pop(b));
  return make_pair(reverse(f), reverse(b));
}
Dequeue empty_d = make_pair(0, empty);
Dequeue check_d(const int bal, List * f, List * b){
  if (f == NULL && b != NULL) // balans ujemny, przerzucamy b->f
    return make_pair(bal%2, rev_n(((bal-1)/2), nil, reverse(b)));
  if (b == NULL && f != NULL) // balans dodatni, przerzucamy f->b
    return make_pair(bal%2, rev_n(bal/2, reverse(f), NULL));
  return Dequeue(bal, Queue(f,b));
}
Dequeue insert_back(int elem, Dequeue q){
  return check_d(q.first-1, q.second.first, new List(elem, q.second.second));
}
Dequeue insert_front(int elem, Dequeue q){
  return check_d(q.first+1, new List(elem, q.second.first), q.second.second);
}
int front(Dequeue q){
  return q.second.first->head();
}
int back(Dequeue q){
  if(q.second.second == NULL) // jednoelementowe dequeue
    return q.second.first->head();
  return q.second.second->head();
}
Dequeue pop_front(Dequeue q){
  check_d(q.first-1, q.second.first->tail(), q.second.second);
}
Dequeue pop_back(Dequeue q){
  if(q == empty_d) throw Empty(); // z pustego i Salomon nie usunie
  if(q.second.second == NULL) // jednoelementowe dequeue ─ mozna
    return empty_d;
  return check_d(q.first+1, q.second.first, q.second.second->tail());
}

Oczywiście również tej kolejki nie możemy wykorzystać, jeśli chcemy używać starych stanów struktury. Jeśli jednak ich nie potrzebujemy, a z jakiegoś powodu używamy struktur trwałych, to powyższe kolejki są najszybszą i najprostszą implementacyjnie możliwością.

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