Prednáška 14

Oznamy

• Tento týždeň bude okrem bežnej rozcvičky na utorňajších cvičeniach aj bonusová rozcvička počas piatkových doplnkových cvičení (za 1 bonusový bod). Termín odovzdania zvyšných úloh z týchto cvičení bude streda 18. novembra, 22:00.
• Druhú domácu úlohu treba odovzdať do piatku 13. novembra, 22:00.
• Budúci týždeň budú kvôli štátnemu sviatku iba piatkové cvičenia. V pondelok 16. novembra bude zverejnených niekoľko úloh na cvičenia č. 9 (menej, než obvykle).
• V piatok 20. novembra bude na začiatku doplnkových cvičení krátky test, body za ktorý budú riadnou súčasťou hodnotenia z cvičení č. 9. Pokyny ohľadom technickej realizácie testu budú upresnené neskôr.

Ešte k smerníkom

Opakovanie základnej práce so smerníkmi

int a = 7;         // premenna typu int 
int *b = NULL;     // smernik na int 
b = &a;            // b obsahuje adresu premennej a 
*b = 8;            // v premennej a je teraz 8 
a = (*b)+1;        // v premennej a je teraz 9

Smerníky a struct

Smerník môže ukazovať aj na struct. Operátory . (prístup k prvku štruktúry) a [] (prístup k prvku poľa) majú vyššiu prioritu ako operátory * (dereferencia smerníka) a & (adresa). Preto napríklad:

• Zápis *s.cokolvek je to isté ako *(s.cokolvek) a vyjadruje dereferenciu smerníka s.cokolvek.
• Zápis (*p).cokolvek vyjadruje prvok cokolvek štruktúry získanej dereferenciou smerníka p.
• Zvyčajne je potrebnejší zápis (*p).cokolvek; existuje preň preto skratka p->cokolvek.

struct bod {
  int x, y;
};

// ...

bod b;             
b.x = 0;
b.y = 0;
bod *p  = &b;      // p ukazuje na bod b

bod *p2 = new bod; // alokovanie noveho bodu 
(*p2).x = 20;      // bod, na ktory ukazuje p2, bude mat x 20
p2->y = 10;        // bod, na ktory ukazuje p2, bude mat y 10
delete p2;         // uvolnenie pamate

Dynamická množina

Motivačný príklad

• Na fakulte sa dvere do niektorých miestností otvárajú priložením čipovej karty k čítačke
• Každá karta má v sebe uložené identifikačné číslo
• Čítačka má v pamäti zoznam identifikačných čísel oprávnených osôb (študenti, vyučujúci a pod.)
• Po priložení karty z nej prečíta číslo a zisťuje, či ho má vo svojom zozname
• Administrátor tiež potrebuje vedieť pridávať a uberať oprávnené osoby
• Ako asi môže byť systém pracujúci so zoznamom identifikačných čísel naprogramovaný?

Dynamická množina

Chceli by sme vytvoriť dátovú štruktúru s nasledujúcou špecifikáciou

• Máme množinu A, ktorá sa bude postupne meniť, preto ju nazývame dynamická množina
• Funkcia contains dostane množinu A a hodnotu x a zistí, či x patrí do A
• Funkcia add dostane množinu A a hodnotu x a pridá x do A
• Funkcia remove dostane množinu A a prvok x a odoberie x z A
• Pre jednoduchosť funkciu remove nebudeme dnes uvažovať
• Niekedy sa môžu zísť aj iné operácie.

Problém príslušnosti k množine sa vyskytuje aj v mnohých iných situáciách.

• Ako dnes uvidíme, dynamickú množinu môžeme implementovať rôznymi spôsobmi.
• Hovoríme, že dynamická množina je abstraktný dátový typ, špecifikuje totiž iba rozhranie, ktoré má dátová štruktúra poskytovať používateľovi, nie jeho implementáciu.
• Ak by sme zmenili implementáciu z jednej na inú, nemusíme nutne meniť programy, ktoré dynamickú množinu využívajú, pokiaľ k nej pristupujú iba pomocou uvedených funkcií.

Implementácie dynamických množín

• Pre jednoduchosť budeme uvažovať iba dynamickú množinu celých čísel.
• Dynamickú množinu budeme uchovávať v štruktúre set.
• Navyše budeme mať implementovaných niekoľko funkcií, ktoré s dynamickými množinami pracujú.
• Kostra programu teda bude vyzerať pre ľubovoľnú implementáciu dynamickej množiny takto:

/* Struktura reprezentujuca dynamicku mnozinu. */
struct set {
    // ...
};

/* Funkcia, ktora vytvori prazdnu dynamicku mnozinu. */
void init(set &s) {
    // ...
}

/* Funkcia, ktora zisti, ci prvok x patri do mnoziny s. */
bool contains(set &s, int x) {
    // ...
}

/* Funkcia, ktora prida prvok x do mnoziny s. */
void add(set &s, int x) {
    // ...
}

/* Funkcia, ktora uvolni mnozinu s z pamate. */
void destroy(set &s) {
    // ...
}

Bez ohľadu na implementáciu štruktúry set a uvedených funkcií už teraz môžeme napísať program, ktorý ich využíva. Z konzoly číta príkazy a postupne ich vykonáva.

#include <iostream>
#include <cstring>
using namespace std;

// ...

const int maxlength = 100;

int main(void) {
    set A;
    init(A);
    
    while (true) {
        char prikaz[maxlength];
        cin.width(maxlength);
        cin >> prikaz;
        if (strcmp(prikaz, "contains") == 0) {
            int x;
            cin >> x;
            cout << contains(A, x) << endl;        
        } else if (strcmp(prikaz, "add") == 0) {
            int x;
            cin >> x;
            add(A, x);
        } else if (strcmp(prikaz, "end") == 0) {    
            break;
        }
    }

    destroy(A);
}

Ukážeme si teraz niekoľko rôznych implementácii dynamickej množiny; začneme s dvoma, ktoré sú nám už v princípe známe.

Dynamická množina ako pole

Dynamickú množinu môžeme implementovať tak, že jej prvky budeme ukladať do poľa v ľubovoľnom poradí.

• Funkcia contains musí zakaždým prejsť celé pole lineárnym prehľadávaním (nie je teda zrovna rýchla).
• Funkcia add je naopak veľmi rýchla: stačí pridať prvok na koniec poľa.
• Je ale potrebné dávať pozor na prekročenie kapacity poľa (mohli by sme použiť dynamické pole).

#include <cassert>

// ...

const int maxN = 1000;

struct set {
    int *p;      // Smernik na nulty prvok pola.
    int length;  // Pocet prvkov v poli
};

void init(set &s) {
    s.p = new int[maxN];
    s.length = 0;
}

bool contains(set &s, int x) {
    for (int i = 0; i < s.length; i++) {
        if (s.p[i] == x) {
            return true;
        }
    }
    return false;
}

void add(set &s, int x) {
    assert(s.length < maxN);
    s.p[s.length] = x;
    s.length++;
}

void destroy(set &s) {
    delete[] s.p;
}

Dynamická množina ako utriedené pole

Prvky množiny môžeme v poli uchovávať aj utriedené od najmenšieho po najväčšie.

• Funkcia contains potom môže použiť binárne vyhľadávanie. Je teda rýchlejšia, ako v predchádzajúcom prípade (v poli veľkosti n sa pozrie len na približne log n pozícií; napríklad pre miliónprvkové pole sa pozrieme asi na 20 prvkov poľa).
• Funkcia add ale musí vložiť prvok na správne miesto v utriedenom poli; je teda o dosť pomalšia.

#include <cassert>

// ...

const int maxN = 1000;

struct set {
    int *p;      // Smernik na nulty prvok pola.
    int length;  // Momentalna dlzka pola. 
};

void init(set &s) {
    s.p = new int[maxN];
    s.length = 0;
}

bool contains(set &s, int x) {
    int left = 0;
    int right = s.length - 1;
    while (left <= right) {
        int index = (left + right) / 2;
        if (s.p[index] == x) {
            return true;
        } else if (s.p[index] > x) {
            right = index - 1;
        } else {
            left = index + 1;
        }    
    }
    return false;
}

void add(set &s, int x) {
    assert(s.length < maxN);
    int kam = s.length;
    while (kam > 0 && s.p[kam - 1] > x) {
        s.p[kam] = s.p[kam - 1];
        kam--;
    }
    s.p[kam] = x;
    s.length++;
}

void destroy(set &s) {
    delete[] s.p;
}

Ďalšie možnosti implementácie dynamickej množiny (plán na dnes)

Dnes uvidíme ďalšie dva spôsoby implementácie dynamickej množiny:

• Množina ako jednosmerne spájaný zoznam:
  • Ľahko pridáme nové prvky, nepotrebujeme vopred vedieť veľkosť.
  • Nedá sa rýchlo binárne vyhľadávať.
  • Založené na smerníkoch.
• Množina pomocou hešovania:
  • Často veľmi rýchle vyhľadávanie.
  • Použijeme polia aj spájané zoznamy.

Spájané zoznamy

Spájaný zoznam (angl. linked list) je postupnosť uzlov rovnakého typu usporiadaných za sebou. Každý uzol pritom pozostáva z dvoch častí:

• Samotné dáta; v našom prípade jedno číslo typu int.
• Smerník, ktorý ukazuje na nasledujúci prvok zoznamu – ten umožňuje „pohybovať sa” po zozname zľava doprava.

Posledný uzol zoznamu nemá následníka – jeho smerník na následníka teda bude mať hodnotu NULL.

Štruktúra spájaného zoznamu je znázornená na nasledujúcom obrázku:

Keďže si v každom uzle pamätáme iba smerník na následníka (t.j. uzol „napravo” od daného uzla), hovoríme tiež o jednosmerne spájanom zozname. Často sú užitočné aj obojsmerne spájané zoznamy, kde sa v každom uzle uchováva aj smerník na predchodcu; takéto zoznamy sú ale o niečo náročnejšie na „údržbu”.

Uzol jednosmerne spájaného zoznamu budeme reprezentovať pomocou struct-u node:

/* Struktura reprezentujuca uzol jednosmerne spajaneho zoznamu: */
struct node {
    int data;    // Hodnota ulozena v danom uzle
    node *next;  // Smernik na nasledujuci uzol
};

Vo vnútri definície typu node teda používame smerník na samotný typ node.

Na rozdiel od poľa, v ktorom je poradie stanovené indexmi, je poradie v spájanom zozname určované ukazovateľmi next. Ak x je uzol zoznamu, tak x.next je:

• Smerník na nasledujúci uzol zoznamu, ak takýto uzol existuje.
• NULL v opačnom prípade.

Samotný spájaný zoznam – resp. množina ním reprezentovaná – je potom iba štruktúra set obsahujúca smerník na prvý prvok zoznamu. Ak je zoznam prázdny, bude tento smerník NULL. V štruktúre set by sme v prípade potreby mohli uchovávať aj iné údaje, ako napríklad počet prvkov v zozname a podobne.

/* Struktura realizujuca mnozinu prostrednictvom spajaneho zoznamu: */
struct set {
    node *first; // Smernik na prvy uzol zoznamu
};

void init(set &s) {
    s.first = NULL;
}

Vkladanie na začiatok zoznamu

Nasledujúca funkcia na začiatok zoznamu vloží nový uzol s dátami x:

void add(set &s, int x) {
    node *p = new node;  // Vytvorime novy uzol ...
    p->data = x;         // ... a jeho data nastavime na x.
    p->next = s.first;   // Naslednikom noveho uzla p v zozname bude doposial prvy prvok zoznamu ...
    s.first = p;         // ... a uzol p bude odteraz novym prvym prvkom v zozname.
}

Vyhľadávanie v zozname

Funkcia vyhľadávajúca číslo x v zozname bude pracovať tak, že postupne prehľadáva zoznam od jeho začiatku, s využitím smerníkov na nasledujúce prvky:

bool contains(set &s, int x) {
    node *p = s.first;
    while (p != NULL) {
        if (p->data == x) {
            return true;
        } 
        p = p->next;
    }
    return false;
}

Uvoľnenie zoznamu

Funkcia realizujúca uvoľnenie zoznamu z pamäti pracuje podobne: prechádza postupne zoznam od začiatku až po jeho koniec a uvoľňuje z pamäte jednotlivé uzly. Treba si tu však dať pozor na to, aby sme smerník na nasledujúci uzol získali ešte predtým, než z pamäti uvoľníme ten predošlý.

void destroy(set &s) {
    node *p = s.first;
    while (p != NULL) {
        node *p2 = p->next;
        delete p;
        p = p2;
    }
}

Výpis zoznamu

Môžeme napísať aj nasledujúcu funkciu, ktorá po zavolaní vypíše obsah celého zoznamu:

void print(set &s) {
    node *p = s.first;
    while (p != NULL) {
        cout << p->data << " ";
        p = p->next;
    }   
    cout << endl; 
}

Hešovanie

Implementácia množiny priamym adresovaním

Úplne odlišným spôsobom implementácie dynamickej množiny je tzv. priame adresovanie (angl. direct addressing).

• Množinu všetkých možných hodnôt, ktoré v danej implementácii môžeme chcieť do množiny pridať, nazveme univerzum U
• Predchádzajúce implementácie sa ľahko dali upraviť na rôzne univerzá (celé čísla, desatinné čísla, smerníky na zložitejšie štruktúry, napr. struct, pole, reťazec)
• Na rozdiel od toho sa priame adresovanie dá použiť iba ak univerzum je U = {0,1,...,m-1} pre nejaké rozumne malé prirodzené číslo m
• Podmnožinu 'A univerza U potom môžeme reprezentovať ako pole booleovských hodnôt dĺžky m, kde i-ty prvok tohto poľa bude true práve vtedy, keď i patrí do A.
• Túto reprezentáciu sme používali napríklad v poli bolo pri pri prehľadávaní s návratom.

• Funkcie contains aj add sú potom veľmi jendoduché a rýchle.
• Problémom tohto prístupu je ale vysoká pamäťová zložitosť v prípade, že je číslo m veľké.
• Veľmi efektívne pre malé univerzá (napr. cifry 0,...,9, všetky znaky anglickej abecedy, všetky znaky s ASCII hodnotami od 0 po 255, a pod.).

#include <cassert>

// ...

const int m = 1000;

/* Struktura realizujuca mnozinu prostrednictvom priameho adresovania: */
struct set {
    bool *p;
};

void init(set &s) {
    s.p = new bool[m];
    for (int i = 0; i <= m - 1; i++) {
        s.p[i] = false;
    }
}

bool contains(set &s, int x) {
    assert(x >= 0 && x <= m - 1);
    return s.p[x];  
}

void add(set &s, int x) {
    assert(x >= 0 && x <= m - 1);
    s.p[x] = true;
}

void destroy(set &s) {
    delete[] s.p;
}

Jednoduché hešovanie

Priame adresovanie sa príliš nehodí pre veľmi veľké univerzá – v takom prípade je totiž potrebné veľké množstvo pamäte.

Hešovanie je jednoduchá finta, ktorá funguje nasledovne:

• Nech U je univerzum všetkých možných prvkov množiny (kľúčov). V nasledujúcom budeme pre jednoduchosť predpokladať, že ide o nejakú podmnožinu množiny celých čísel (prípadne priamo o množinu všetkých celých čísel).
• Vytvoríme tzv. hešovaciu tabuľku hashtable – pole nejakej rozumnej veľkosti m, pozostávajúce z prvkov rovnakého typu ako prvky univerza (v našom prípade teda int).
• Naprogramujeme hešovaciu funkciu, ktorá transformuje prvky univerza U na indexy hešovacej tabuľky; pôjde teda o funkciu h: U -> {0, 1, ... , m−1}.
• Hešovacia funkcia by mala byť jednoduchá a rýchla, ale pritom by nemala „často prideľovať rovnaké indexy” (mala by kľúče do tabuľky distribuovať rovnomerne).
• Najjednoduchšia hešovacia funkcia je h(x) = x mod m pre m ≥ 3.
  • Pozor: napríklad -10 % 3 je -1, takže radšej použijeme absolútnu hodnotu z x (funkcia abs z knižnice cstdlib).

int hash(int x, int m) {
    return abs(x) % m;
}

Pre m = 5 je táto funkcia znázornená na nasledujúcom obrázku.

S hešovacou tabuľkou teraz môžeme pracovať nasledovne:

Vkladanie prvku x:

• Spočítame index = hash(x, m) a prvok vložíme na pozíciu hashtable[index].

Vyhľadávanie prvku x:

• Ak je prvok s kľúčom x v tabuľke, musí byť na indexe hash(x, m).
• Skontrolujeme túto pozíciu a ak tam je niečo iné ako x, prvok x sa v tabuľke nenachádza.

Problémy:

• Na akú hodnotu inicializovať prvky poľa hashtable?
• Čo ak budeme potrebovať vložiť prvok na miesto, kde je už niečo uložené?

Kolízie

Pri vkladaní prvku sme narazili na problém, ak na už obsadané miesto chceme vložiť iný prvok. Môže sa stať, že dva prvky x a y sa zahešujú na rovnakú pozíciu h(x) = h(y). Takémuto javu hovoríme kolízia a existuje viacero spôsobov, ako sa s ním vysporiadať. Naše riešenie bude spočívať v nasledujúcej myšlienke:

• Kolidujúci prvok aj tak vložíme na vypočítané miesto v tabuľke, na ktorom už teda bude môcť byť uložený viac ako jeden prvok.
• Prvky na danej pozícii hešovacej tabuľky budeme uchovávať v spájanom zozname.

Existujú však aj iné prístupy – môžeme napríklad hľadať iné voľné miesto v tabuľke a podobne (viac budúci rok na predmete Algoritmy a dátové štruktúry).

Riešenie kolízií pomocou spájaných zoznamov

V každom políčku hešovacej tabuľky teda budeme uchovávať spájaný zoznam so všetkými prvkami množiny, ktoré hešovacia funkcia priradila na toto políčko. Táto situácia je znázornená na nasledujúcom obrázku, v ktorom šípky zodpovedajú vkladaniam prvkov (celých čísel) do množiny reprezentovanej hešovacou tabuľkou.

#include <cstdlib>

// ...

/* Hesovacia funkcia: */
int h(int x, int m) {
    return abs(x) % m;
}

/* Struktura reprezentujuca jeden prvok spajaneho zoznamu: */
struct node {
    int data;
    node *next;
};

/* Struktura realizujuca dynamicku mnozinu pomocou hesovania: */
struct set {
    node **hashtable;  // Pole smernikov na zaciatky jednotlivych zoznamov
    int m;             // Velkost hesovacej tabulky  
};

void init(set &s, int m) {  // Velkost tabulky bude parametrom funkcie init
    s.m = m;
    s.hashtable = new node *[m];
    for (int i = 0; i <= m - 1; i++) {
        s.hashtable[i] = NULL;
    }
}

bool contains(set &s, int x) {
    int index = h(x, s.m);     // Spocitame spravne policko hesovacej tabulky
    node *p = s.hashtable[index]; // Smernik p ukazuje na prvy prvok spajaneho 
                                  // zoznamu na danom policku
    while (p != NULL) {           // Prechadzame zoznam, hladame x
        if (p->data == x) {
            return true;
        }
        p = p->next;
    } 
    return false;    
}

void add(set &s, int x) {
    int index = h(x, s.m);        // Spocitame spravne policko hesovacej tabulky
    node *temp = new node;           // Vytvorime novy uzol do spajaneho zoznamu 
    temp->data = x;               
    temp->next = s.hashtable[index]; // Vlozime uzol temp na zaciatok zoznamu.
    s.hashtable[index] = temp;       
}

void destroy(set &s) {
    for (int i = 0; i <= s.m - 1; i++) {
        node *p = s.hashtable[i];   // Uvolni zoznam s.hashtable[i]
        while (p != NULL) {
            node *nxt = p->next;
            delete p;
            p = nxt;
        }
    }
    delete[] s.hashtable;
}

Cvičenie: Ako bude vyzerať hešovacia tabuľka pri riešení kolízií pomocou spájaných zoznamov, ak hešovacia funkcia je |x| mod 5 a vkladáme prvky 13, -2, 0, 8, 10, 17?

Zložitosť

• Rýchlosť závisí od toho, akú máme veľkosť tabuľky m, hešovaciu funkciu a koľko prvkov sa zahešuje do jedného políčka.
• V najhoršom prípade sa všetky prvky zahešujú do toho istého políčka, a teda musíme pri hľadaní prejsť všetky prvky množiny.
• Ak máme šťastie a v každom políčku máme len málo prvkov, bude aj vyhľadávanie rýchle.
  • Ak je tabuľka dosť veľká a hešovacia funkcia vhodne zvolená, tento prípad je pomerne obvyklý.
  • Hešovacie tabuľky sa často používajú v praxi.
• Viac budúci rok na predmete Algoritmy a dátové štruktúry.