Temat 7. Kolejki priorytetowe.

Jest to najbardziej ogólny rodzaj kolejek. Spośród elementów stojących w kolejce pobierany jest element o najwyższym priorytecie, a przy równych priorytetach ten element który wcześniej stanął w kolejce. Zwykła kolejka może być traktowana jako kolejka priorytetowa, w której priorytet jest określony przez czas wejścia do kolejki. Implementacja kolejki zależy od charakteru zbioru priorytetów.

a)- z nieograniczonym zbiorem wartości priorytetów

- nieuporządkowane

wstawianie na koniec kolejki (złożoność O(1))

usuwanie elementu o najwyższym priorytecie (pierwszego z równych) (złożoność O(N))

- uporządkowane, wykorzystujące:

-- uporządkowaną listę lub tablicę

usuwanie z początku kolejki (złożoność O(1))

wstawianie na właściwe miejsce (za ostatni o takim samym priorytecie) (złożoność O(N))

- stóg (złożoność wstawiania i pobierania O(log N))

 

b)- z priorytetami o wartościach wybranych z niewielkiego zbioru.

W tym wypadku wykorzystujemy tablicę zwykłych kolejek (dla każdego priorytetu osobna).

 

Implementacja kolejki bazującej na liście nieuporządkowanej:

 

package queues;

import lists.LinkedList;

import lists.List;

import sorting.Comparator;

 

public class UnsortedPriorityQueue implements Queue {

private final List _list;

private final Comparator _comparator; //do ustalenia priorytetu

 

public UnsortedPriorityQueue(Comparator comparator) {

_comparator = comparator;

_list = new LinkedList();

}

public void enqueue(Object value)

{ _list.add(value); }

 

public Object dequeue() throws EmptyQueueException {

if (isEmpty()) throw new EmptyQueueException();

return _list.delete(getIndexOfLargestElement());

}

 

private int getIndexOfLargestElement() {

int result = 0;

for (int i = 1; i < _list.size(); ++i)

if (_comparator.compare(_list.get(i), _list.get(result)) > 0)

result = i;

return result;

}

 

public void clear()

{ _list.clear(); }

 

public int size()

{ return _list.size(); }

 

public boolean isEmpty()

{ return _list.isEmpty();}

}

 

Implementacja wykorzystująca listę uporządkowaną:

 

package queues;

import lists.LinkedList;

import lists.List;

import sorting.Comparator;

 

public class SortedPriorityQueue implements Queue {

private final List _list;

private final Comparator _comparator;

 

public SortedPriorityQueue(Comparator comparator) {

_comparator = comparator;

_list = new LinkedList();

}

 

public void enqueue(Object value) {

int pos = _list.size();

while (pos > 0 && _comparator.compare(_list.get(pos - 1), value) > 0)

--pos;

_list.insert(pos, value);

}

 

public Object dequeue() throws EmptyQueueException {

if (isEmpty()) throw new EmptyQueueException();

return _list.delete(_list.size() - 1);

}

 

public void clear()

{ _list.clear(); }

 

public int size()

{ return _list.size();}

 

public boolean isEmpty()

{ return _list.isEmpty();}

}

Pojęcie stogu (Heap):

 

Stogiem zupełnym (stertą) nazywamy takie drzewo binarne, które ma dwie własności:

- kształtu: jest pełnym drzewem, przy czym ostatni poziom jest zapełniany od lewej strony

- uporządkowania: węzeł jest zawsze większy od swoich potomków.

 

Najprościej jest realizować stóg w tablicy. Wówczas synami węzła i są węzły 2*i+1 oraz 2*(i+1), a ojcem węzła i jest węzeł (i-1)/ 2.

 

Implementacja kolejki wykorzystującej stóg:

 

package queues;

import lists.ArrayList;

import lists.List;

import sorting.Comparator;

 

public class HeapPriorityQueue implements Queue {

private final List _list;

private final Comparator _comparator;

 

public HeapPriorityQueue(Comparator comparator) {

_comparator = comparator;

_list = new ArrayList();

}

 

public void enqueue(Object value) {

_list.add(value);

swim(_list.size() - 1);

}

 

//wynoszenie elementu w górę

private void swim(int index) {

int parent;

while(index!= 0 &&

_comparator.compare(_list.get(index), _list.get(parent= (index - 1) / 2)) > 0)

{ swap(index, parent);

index=parent;

}

}

 

private void swap(int index1, int index2) {

Object temp = _list.get(index1);

_list.set(index1, _list.get(index2));

_list.set(index2, temp);

}

 

public Object dequeue() throws EmptyQueueException {

if (isEmpty()) throw new EmptyQueueException();

Object result = _list.get(0);

if (_list.size() > 1) {

_list.set(0, _list.get(_list.size() - 1));

sink(0);

}

_list.delete(_list.size() - 1);

return result;

}

 

// opuszczanie elementu w dół stogu

private void sink(int index) {

boolean isDone=false;

int child;

while(!isDone && (child=2*index+ 1) < _list.size()) {

if (child < _list.size()- 1 &&

_comparator.compare(_list.get(child), _list.get(child+1)) < 0)

++child;

if (_comparator.compare(_list.get(index), _list.get(child)) < 0)

swap(index, child);

else isDone=true;

}

}

 

public void clear()

{ _list.clear(); }

 

public int size()

{ return _list.size(); }

 

public boolean isEmpty()

{ return _list.isEmpty();}

}

Zadania:

20) Stóg wykorzystywany do sortowania stogowego można zbudować bez wykorzystania metody swim (przesuwanie w górę). Jest to znacznie szybszy proces.Zaimplementuj odpowiednią metodę.

21) Flloyd zauważył, że można przyspieszyć usuwanie elementu kolejki stogowej przez modyfikację metody sink. Zaproponował żeby opuszczać element na sam dół stogu, a następnie jeśli trzeba to go podnieść na odpowiednią pozycję. Kiedy to podejście przynosi korzyść.

Temat 8. Tablice symboli (słowniki).

Słownik (inne nazwy to: tablica skojarzeniowa, tablica asocjacyjna, tablica indeksowana wartością klucza, odwzorowanie, mapa - bezmyślne przetłumaczenie angielskiego terminu map czyli odwzorowanie) - typ abstrakcyjny z określonymi operacjami:

JestElementem - czy dany element występuje w słowniku albo wyszukaj element o danym kluczu

Dodaj - dopisz element do słownika

Usun - usuń element ze słownika

Wybierz - k-ty co do wielkości element

Sortuj - wypisz wszystkie elementy w sposób uporządkowany

Połącz - połącz dwa słowniki w jeden

 

Należy pamiętać że podstawową operacją na typowym słowniku jest wyszukiwanie elementu; dodawanie i usuwanie albo nie występują, albo są wykonywane bardzo rzadko. Więc efektywność wyszukiwania decyduje o przydatności danej realizacji. Metody wyszukiwania elementu zależą od sposobu organizacji słownika. Klucze obiektów (elementów) występujących w słowniku nie mogą się powtarzać. Elementy występujące w słowniku mogą się składać albo z samego klucza (np. słownik słów kluczowych kompilatora, słownik do sprawdzania pisowni) lub z klucza i danych (np. słownik polsko-angielski, encyklopedia, książka telefoniczna). Od typu elementu zależy sposób działania operacji JestElementem:

- tylko sprawdzenie gdy element ma tylko klucz

- zwrócenie wartości pola dane dla elementów zbudowanych z klucza i danych.

Operacja dodawania elementu do słownika jest wykonywana znacznie rzadziej. Tylko w specyficznych sytuacjach w czasie normalnej pracy (on-line) i wówczas jej efektywność jest istotna, zazwyczaj jednak jest wykonywana w trybie off-line i szybkość nie ma praktycznego znaczenia. Usuwanie elementu prawie zawsze jest wykonywane w trybie off-line.

 

Można wyróżnić trzy podstawowe klasy struktur służących do przechowywania elementów słownika:

1. ciąg nieuporządkowany (tablica, plik lub lista)

2. tablica haszowana

3. ciąg uporządkowany (tablica, plik, lista, struktury drzewiaste).

Na początek zajmiemy się wyszukiwaniem na listach nieuporządkowanych i uporządkowanych.

Interfejs wyszukiwania:

 

package searching;

import lists.List;

 

public interface ListSearcher {

//zwraca pozycję obiektu na liście - jeśli jest

//jeśli nie to - (pozycja_wstawienia + 1)

// plus1 umożliwia wskazanie, że element powinien się znajdować na początku listy

 

public int search(List list, Object value);

}

 

Dla list nieuporządkowanych stosujemy wyłącznie proste przeszukiwanie liniowe (złożonośc O(N)).

Dla list uporządkowanych możemy zastosować:

- wyszukiwanie liniowe (O(N)), szybsze wykrywanie braku elementu w porównaniu do list nieuporządkowanych:

 

package searching;

import lists.List;

import sorting.Comparator;

 

public class LinearListSearcher implements ListSearcher {

private final Comparator _comparator;

 

public LinearListSearcher(Comparator comparator)

{ _comparator = comparator; }

 

public int search(List list, Object value) {

int cmp=0,i;

for (i=0; i<list.size() && (cmp = _comparator.compare(value, list.get(i)))>0; i++);

return i<list.size() && cmp ==0? i: -(i+1); //lista może być pusta

}

}

 

- wyszukiwanie binarne (złożoność O(log N)):

idea:

 

Oznaczenia: k- klucz szukanego elementu

poc - pozycja lewego końca przeszukiwanego obszaru k(poc) klucz tej pozycji

kon - pozycja prawego końca k(kon) jej klucz

b - wyznaczony w danym kroku punkt podziału k(b) klucz

 

do b= (poc+kon) div 2

if (k >k(b)) b+1 staje się lewym końcem nowego przedziału

else b staje się prawym końcem nowego przedziału

while (poc >=kon)

sprawdź element na pozycji poc

implementacja iteracyjna (nieco inna wersja - dla optymistów)

package searching;

 

import lists.List;

import sorting.Comparator;

 

public class IterativeBinaryListSearcher implements ListSearcher {

private final Comparator _comparator;

 

public IterativeBinaryListSearcher(Comparator comparator)

{ _comparator = comparator; }

 

public int search(List list, Object value) {

int lower = 0;

int upper = list.size() - 1;

int index=0,cmp=0;

while (lower <= upper &&

(cmp = _comparator.compare(value, list.get(index=(lower + upper)/2)))!=0)

if (cmp < 0) upper = index - 1;

else lower = index + 1;

return lower<=upper && cmp==0? index: -(lower+1);

}

}

 

Implementacja rekurencyjna

 

package searching;

import lists.List;

import sorting.Comparator;

 

public class RecursiveBinaryListSearcher implements ListSearcher {

private final Comparator _comparator;

 

public RecursiveBinaryListSearcher(Comparator comparator)

{ _comparator = comparator; }

 

public int search(List list, Object value)

{ return search(list, value, 0, list.size() - 1); }

 

// wersja dla miłośników instrukcji return (moim zdaniem nienajlepsza)

private int search(List list, Object value, int lower, int upper) {

if (lower > upper) return -(lower + 1);

int index = (lower + upper) / 2;

int cmp = _comparator.compare(value, list.get(index));

if (cmp < 0) return search(list, value, lower, index - 1);

if (cmp > 0) return search(list, value, index + 1, upper);

return index;

}

}

 

Jeszcze szybsze jest wyszukiwanie interpolacyjne (stosowane gdy klucze mają rozkład równomierny)

do b= poc+(k-k(poc))/(k(kon)-k(poc))*(kon-poc)

if (k >k(b)) b+1 staje się lewym końcem nowego przedziału

else b staje się prawym końcem nowego przedziału

while (poc >=kon)

sprawdź element na pozycji poc

 

Złożoność log log(N) - czyli praktycznie stała.

Zadania:

22) Zaimplementuj wyszukiwanie binarne dokładnie według przedstawionej powyżej idei. Sprawdź swój algorytm dla wszystkich granicznych przypadków.

23) Zaimplementuj rekurencyjną wersję wyszukiwania liniowego. Chodzi wyłącznie o gimnastykę umysłu - staramy się unikać rekurencji o głębokości liniowej.