Programovanie (2) v Jave
1-INF-166, LS 2016/17

Úvod · Pravidlá · Prednášky · Projekt · Netbeans · Odovzdávanie · Test a skúška
· Vyučujúcich môžete kontaktovať pomocou e-mailovej adresy E-prg.png (bude odpovedať ten z nás, kto má príslušnú otázku na starosti alebo kto má práve čas).
· Predvádzanie projektov bude v pondelok 5.6. od 9:00 do 12:00 a v utorok 6.6 od 12:00 do 13:30 (po skúške), oboje v miestnosti M217. Na termín sa prihláste v AIS. Ak robíte vo dvojici, prihlási sa iba jeden člen dvojice.
· Body zo záverečného testu sú na testovači. Poradie príkladov: P1: do šírky, P2: topologické, P3: výnimky, P4: iterátor, P5: testy, P6: strom. Bolo potrebné získať aspoň 20 bodov zo 40.
· Opravný test bude 19.6.2017 od 9:00 v miestnosti M-I. Na termín sa prihláste v AISe.
· Zapisovanie známok a osobné stretnutia ku skúške budú v utorok 13.6. 13:30-14:30 v M163 a v stredu 14.6. 14:00-14:30 v M163.


Prednáška 23

Z Programovanie
Prejsť na: navigácia, hľadanie

Organizačné poznámky

  • Dnes a zajtra posledné prednášky, dnes posledné cvičenie s poslednou rozcvičkou.
  • Doplnkové cvičenie v piatok nebude.
  • Písomka v piatok o 11:30 v posluchárni A. Body z písomky nájdete na testovači.
  • Nezabudnite sa v AIS prihlásiť na skúšku (najneskôr do 14:00 deň pred skúškou, ale aj skôr, kým sú voľné miesta)
  • Do konca skúškového môžete vypĺňať študentskú anketu: https://anketa.uniba.sk/fmph/ Tešíme sa na konštruktívne návrhy, ktoré nám pomôžu zlepšiť predmet do budúcnosti.
  • Do konca týždňa sa pokúsime opraviť všetky DÚ a rozcvičky. Prípadné reklamácie bodov čím skôr, ale najneskôr deň pred skúškou.

Hešovacie tabuľky

Predpokladajme, že chceme implementovať jednoduchú množinu (set) celých čísel.

  • Hlavné operácie insert, find, prípadne delete
  • Zatiaľ sme videli: utriedené pole, neutriedené pole, spájaný zoznam, binárny vyhľadávací strom (keďže nejde o reťazce, lexikografické stromy sa príliš nehodia)

Priame adresovanie

  • Videli sme však ešte jeden prístup: ak sú prvky množiny čísla z {0,1,...,m-1}, môžeme množinu reprezentovať ako pole boolovských hodnôt dĺžky m (viď pole bolo používané pri generovaní variácií bez opakovania)
  • Tento prístup sa volá priame adresovanie (direct adressing)
  • insert, delete aj find v čase O(1)
struct set {
   int m;
   bool *a;
}

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

void insert(set &s, int k) {
  assert(0<=k && k<s.m);
  s.a[k] = true;
}

bool find(set &s, int k) {
  assert(0<=k && k<s.m);
  return s.a[k];
}

Jednoduché hešovanie

Priame adresovanie sa príliš nehodí, ak prvky môžu byť veľmi veľké, lebo potrebuje veľa pamäte. Hešovanie je jednoduchá finta, ktorá funguje nasledovne:

  • vytvoríme si hešovaciu tabuľku: pole veľkosti m rovnakého typu ako prvky množiny, napr. int
  • nech K je množina všetkých možných prvkov množiny (kľúčov)
  • Naprogramujeme hešovaciu funkciu, ktorá transformuje prvky množiny K na indexy poľa, teda pôjde o funkciu h : K -> {0 , 1 , . . . , m−1}.
  • Hešovacia funkcia by mala byť jednoduchá a rýchla, ale pritom by nemala prideľovať často rovnaké indexy (mala by kľúče do tabuľky distribuovať rovnomerne).
  • Často sa používa funkcia h(k) = k mod m (je dobré, ak v tomto prípade m je prvočíslo a nie je blízko mocniny 2).
    • pozor, -10 % 3 je -1, takže radšej použijeme absolútnu hodnotu z k (funkcia abs z knižnice cstdlib)
struct set {
   int m;
   int *data;  // data je pole dlzky m
}

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

Vkladanie

  • spočítame miesto hash(k) a prvok tam vložíme
void insert(set &s, int k) {
    int index = hash(k, s.m);
    s.data[index]=k;
}

Vyhľadávanie

  • ak prvok s kľúčom k je v tabuľke, musí byť na mieste hash(k).
  • skontrolujeme toto miesto a ak tam je niečo iné ako k, k sa v tabuľke nenachádza
bool find(set &s, int k){
    int index = hash(k, s.m);
    return s.data[index]==k;
}

Problémy:

  • na akú hodnotu inicializovať pole s.data?
  • čo ak chceme vložiť prvok na miesto, kde už je 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. Existuje viacero spôsobov, ako ju riešiť.

  • Budeme aj tak vkladať na toto miesto, len tam nebude iba jeden prvok, ale potenciálne viac prvkov v spájanom zozname
  • Budeme hľadať inú voľnú pozíciu v tabuľke
    • buď postupným prezeraním nasledovných prvkov
    • alebo s pozeraním prvkov s nejakým daným krokom
    • o tomto sa dozviete viac o rok na predmete ADŠ

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

Namiesto prvkov typu int budeme mať v každom políčku hashovacej tabuľky spájaný zoznam s prvkami, ktoré hešovacia funkcia priradila na toto políčko.

struct node {
    int item;
    node* next;
};

struct set {
    node** data;
    int m;
};


Vyhľadávanie pracuje na spájanom zozname, ktorý sa nachádza na správnom mieste hešovacej tabuľky.

  • Správny index dostaneme pomocou hash(k,s.m), kde k je hľadaný kľúč a s.m je veľkosť tabuľky s.
bool find(set &s, int k){
    int index = hash(k, s.m);
    node* v = s.data[index];
    while(v!=NULL){
        if(v->item==k) return true;
        v = v->next;
    }
    return false;
}

Pri vkladaní stačí nový prvok pridať na začiatok spájaného zoznamu na správnom mieste tabuľky.

  • Prečo vkladáme na začiatok a nie na koniec?
  • Ak by sme chceli kontrolovať, či tam vkladaný prvok už náhodou nie je, museli by sme najskôr prejsť a skontrolovať celý spájaný zoznam
void insert(set &s, int k) {
    int index = hash(k, s.m);
    node* temp = new node;
    temp->item = k;
    temp->next = s.data[index];
    s.data[index] = temp;
}

Ďalšie funkcie

  • Vymazávanie prebieha podobne ako všetky ostatné operácie na spájanom zozname, ktorý je na mieste tabuľky, kam nás nasmeroval zahešovaný kľúč.
  • Inicializácia vytvorí tabuľku data a nastaví všetky smerníky v nej na NULL.

Príklad. Ako bude vyzerať hešovacia tabuľka pri riešení kolízií pomocou spájaných zoznamov, ak hešovacia funkcia je |k| 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, teda máme insert O(1) a find O(n), kde n je počet prvkov množiny.
  • Ak máme štastie a v každom políčku máme len niekoľko málo (konštantný počet) prvkov, budeme mať insert aj find O(1).
    • Ak je tabuľka dosť veľká a hešovacia funkcia vhodne zvolená, tento príklad je pomerne obvyklý.
    • Hešovacie tabuľky sa často používajú v praxi.
  • Viac budúci rok na ADŠ.

ADT slovník (asociatívne pole)

Pripomíname: abstraktný dátový typ (ADT)

  • Určíme, aké operácie by mala dátová štruktúra spĺňať (hlavičky funkcií), nestaráme sa o implementáciu
  • Napríklad ADT množina poskytuje operácie init, insert, find, príp. delete, atď
  • Videli sme aj ďalšie ADT, napr. vektor, zásobník, rad
  • Pre jeden ADT môže byť viacero implementácií, napr. množina pomocou triedeného poľa, netriedeného poľa, binárneho vyhľadávacie stromu, hešovacou tabuľkou atď
  • Program, ktorý slovník používa, netreba meniť kvôli zmene implementácie (alebo len veľmi málo, napr. pridanie hešovacej funkcie)
  • Budúci semester si ukážeme ako ADT krajšie implementovať pomocou objektovo-orientovaného programovania a generického programovania
    • Je to však len zmena syntaxe (hlavičky funkcií, definície typov a pod.), algoritmy a dátové štruktúry (zoznamy, polia) zostávajú tie isté

K prvkom množiny si často chceme uložiť nejakú prídavnú informáciu. Napr. k menu telefónne číslo alebo e-mailovú adresu. Takáto rozšírená štruktúra sa zvykne nazývať slovník alebo asociatívne pole.

  • V slovníku máme záznamy typu itemType
  • Súčasťou itemType je kľúč (key), podľa ktorého chceme v slovníku vyhľadávať, napr. meno osoby
  • Namiesto jedného typu dataType budeme mať itemType (celý záznam) a keyType (iba kľúč)
struct person {
  char * name;
  char * phone;
  char * address;
};
typedef person itemType;
typedef char * keyType;

Základné operácie so slovníkom potom môžu vyzerať napríklad takto:

  • void insert(dictionary &d, itemType *x);
    • do dátovej štruktúry d vloží záznam *x
    • predpokladá, že v štruktúre je dosť miesta a nie je tam záznam s rovnakým kľúčom
  • itemType *find(dictionary &d, keyType k);
    • nájde záznam s kľúčom k a vráti smerník na neho ho. Ak taký kľúč v slovníku nie je, vráti NULL
  • itemType * remove(dictionary &d, keyType k);
    • vymaže záznam s kľúčom k z d a vráti na záznam smerník

Pre naše typy záznamu a kľúča potrebujeme definovať pomocné funkcie, ktoré budú využívané implementáciou insert, find, remove. Napríklad:

keyType key(itemType *x) {
  return x->name;
}
bool equal(keyType x, keyType y) {
  return strcmp(x, y)==0;
} 

Implementácie ADT množina (poľom, zoznamom, binárnym vyhľadávacím stromom, lexikografickým stromom) sa dajú ľahko rozšíriť na implementácie ADT slovník.

  • Implementáciu hešovaním si teraz ukážeme

Implementácia ADT slovník pomocou hešovania

Ukážeme si program, ktorý

  • implementuje ADT slovník pomocou hešovacej tabuľky
  • použije tento slovník na spočítanie frekvencie výskytu slov vo vstupnom texte
    • toto sme robili aj na prednáške o lexikografických stromoch, tam sme si však spravili štruktúru špecificky na tento účel, tu použijeme všeobecný slovník

Štruktúra programu

  1. definícia typov (keyType, itemType) špecifických pre dané použitie, pomocné funkcie pre tieto typy (napr. key, equal, hash)
  2. implementácie slovníkových funkcií (insert, find, delete,...)
  3. použitie slovníka na daný účel

Druhú časť môžeme hocikedy vymeniť za inú implementáciu slovníka bez zmeny zvyšku programu. Alebo zmenou prvej a tretej časti môžeme využiť ten istý slovník na iný účel.


Definícia typov a pomocných funkcií

V danej aplikácii si musíme najskôr zadefinovať typy itemType a keyType, ktoré určujú, aké záznamy a aké kľúče budeme do slovníka ukladať.

struct word {
  char * str;
  int count;
};
typedef word itemType;
typedef char * keyType;

Ďalej potrebujeme funkciu, ktorá nám pre záznam dá kľúč a funkciu, ktorá zistí, či sú dva kľúče rovnaké. Niektoré implementácie slovníka budú potrebovať aj ďalšie podobné funkcie, napr. zistiť, či je jeden kľúč menší ako druhý.

keyType key(itemType *x) {
  return x->str;
}
bool equal(keyType x, keyType y) {
  return strcmp(x, y)==0;
} 
int hash(keyType x, int m) {
    // Funkcia dostane vstupny retazec str a velkost hashovacej tabulky m.
    // Vrati cislo medzi 0 a m-1
    int h = 0;
    char *c = str;
    while (*c) {
        h = (h*256 + (*c))%m;
        c++;
    }
    h = abs(h) % m;
    return h;
}

Slovníkové funkcie

A tu sú hlavičky základných slovníkových funkcií:

  • void insert(dictionary &d, itemType *x);
    • do dátovej štruktúry d vloží záznam *x
    • predpokladá, že v štruktúre je dosť miesta a nie je tam záznam s rovnakým kľúčom
  • itemType *find(dictionary &d, keyType k);
    • nájde záznam s kľúčom k a vráti smerník na neho ho. Ak taký kľúč v slovníku nie je, vráti NULL
  • itemType* remove(dictionary &d, keyType k);
    • vymaže záznam s kľúčom k z d a vráti na záznam smerník

A pomocné funkcie:

  • void init(dictionary &d, int maxN);
    • vytvorí slovník, do ktorého sa zmestí maxN záznamov (niektoré implementácie maxN nepotrebujú, rastú podľa potreby)
  • void destroy(dictionary &d);
    • uvoľní pamäť, ktorú zaberá slovník (neuvoľnuje pamäť záznamov)
  • itemType ** items(dictionary &d, int &n);
    • vráti novo alokované pole so smerníkmi na jednotlivé záznamy, ich počet dá do n

Implementácie vyzerajú podobne ako pre implementáciu množiny, napr. funkcia find:

itemType* find(dictionary &d, keyType k) {
    // nájde záznam s kľúčom k a vráti smerník na neho ho. 
    // Ak taký kľúč v slovníku nie je, vráti NULL 
    int index = hash(k, d.m); // najdi poziciu v tabulke
    node* v = d.data[index]; // prehladaj spajany zoznam
    while (v != NULL) {
        if (equal(key(v->item), k)) { // spravny prvok najdeny
            return v->item;
        }
        v = v->next;
    }
    return NULL; // kluc nebol najdeny v slovniku
}

Využitie na počítanie slov

Samotný program používajúci slovník na počítanie slov môže vyzerať nejako takto:

int main() {
    dictionary d; // vytvorenie slovnika
    init(d, 19);

    char word[maxLen + 1];
    cin >> word;
    while (strcmp(word, "*") != 0) { // nacitavanie slov zo vstupu
        itemType *item = find(d, word); // najdeme zaznam pre slovo
        if (item != NULL) { // ak existuje, zvysime mu pocitadlo
            item->count++;
        } else { // ak zaznam neexistuje, vytvorime novy
            item = new itemType;
            item->str = new char[strlen(word) + 1]; // pamat pre slovo
            strcpy(item->str, word);
            item->count = 1;
            insert(d, item); // a vlozime ho do slovnika
        }
        cin >> word;
    }

    int n; // pocet zaznamov v slovniku
    itemType **a = items(d, n); // vsetky zaznamy v slovniku

    for (int i = 0; i < n; i++) { // vypis vsetky zaznamy
        cout << a[i]->str << " " << a[i]->count << endl;
    }

    for (int i = 0; i < n; i++) { // odalokuj vsetky zaznamy
        delete[] a[i]->str;
        delete a[i];
    }
    delete[] a; // odalokuj aj pole a

    destroy(d); // odalokuj samotny slovnik
}

Zdrojové kódy

Zdrojový kód programu na ADT slovník pomocou hešovania

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

const int maxLen = 100; // maximalna dlzka slova na vstupe 

struct word { // struktura pre jdno slovo 
    char * str; // samotne slovo ako retazec 
    int count; // pocet vyskytov slova
};
typedef word itemType; // typ celeho zaznamu pre slovnik
typedef char * keyType; // typ kluca pre slovnik

keyType key(itemType *x) { // pre dany zaznam v slovniku vrat kluc
    return x->str;
}

bool equal(keyType x, keyType y) { // su dva kluce totozne?
    return strcmp(x, y) == 0;
}

int hash(keyType x, int m) {
    // Funkcia dostane vstupny kluc x (retazec) a velkost hashovacej tabulky m.
    // Vrati cislo medzi 0 a m-1
    int h = 0;
    char *c = x;
    while (*c) {
        h = (h * 256 + (*c)) % m;
        c++;
    }
    h = abs(h) % m;
    return h;
}

struct node { // vrchol spajaneho zoznamu v slovniku
    itemType* item; // samotne data vo vrchole
    node* next; // dalsi vrchol v zozname
};

struct dictionary { // struktura pre slovnik pomocou hesovacej tabulky
    node** data; // pole dlzky m smernikov na spajane zoznamy
    int m; // dlzka pola data
    int size; // pocet prvkov v slovniku
};

void init(dictionary &d, int m) {
    // vytvori slovnik s hesovacou tabulkou velkosti m
    d.m = m;
    d.data = new node*[m]; // alokovanie tabulky
    for (int i = 0; i < m; i++) {
        d.data[i] = NULL; // vsetky zoznamy su prazdne
    }
    d.size = 0; // v slovniku je 0 zaznamov
}

void destroy(dictionary &d) {
    // uvolni pamt, ktory zabera hesovacia tabulka a spajane zoznamy
    // neuvolnuje pamat jednotlivych zaznamov
    for (int i = 0; i < d.m; i++) {
        node* it = d.data[i]; // uvolni pamat zoznamu na pozicii i
        while (it) {
            node* next = it->next;
            delete it;
            it = next;
        }
    }
    delete[] d.data; // uvolni tabulku
}

void insert(dictionary &d, itemType *x) {
    // do slovnika d vlozi prvok x
    // predpoklada, ze slovnik s takym klucom este v slovniku nie je
    int index = hash(key(x), d.m); // najdi poziciu v tabulke
    node* temp = new node; // vloz novy vrchol na zaciatok zoznamu
    temp->item = x;
    temp->next = d.data[index];
    d.data[index] = temp;
    d.size++; // zvys pocet prvkov v slovniku
}

itemType* find(dictionary &d, keyType k) {
    // nájde záznam s kľúčom k a vráti smerník na neho ho. 
    // Ak taký kľúč v slovníku nie je, vráti NULL 
    int index = hash(k, d.m); // najdi poziciu v tabulke
    node* v = d.data[index]; // prehladaj spajany zoznam
    while (v != NULL) {
        if (equal(key(v->item), k)) { // spravny prvok najdeny
            return v->item;
        }
        v = v->next;
    }
    return NULL; // kluc nebol najdeny v slovniku
}

itemType* remove(dictionary &d, keyType k) {
    // vymaže záznam s kľúčom k z d (ak tam je)
    // navratova hopdnota je zaznam vymazany zo slovnika
    // (jeho pamat nebola uvolnena)
    int index = hash(k, d.m); // najdi poziciu v tabulke
    node** p = &(d.data[index]); // vymaz zo zoznamu pomocou dvojiteho smernika
    while (*p != NULL) {
        node* v = *p; // aktualny vrchol zoznamu
        if (equal(key(v->item), k)) { // nalsi sme hladany kluc - mazeme
            *p = v->next; // *p je smernik, ktory ukazoval na v
            itemType *item = v->item; // odlozime si zaznam, aby sme ho mohli vratit
            delete v; // uvolnime pamt pre uzol zoznamu
            d.size--; // znizime pocet zaznamov v slovniku
            return item; // vratime item, skoncime s hladanim 
        }
        p = &(v->next);
    }
    return NULL; // zaznam sme nenasli, nic sme nezmazali
}

itemType ** items(dictionary &d, int &n) {
    // vráti novo alokované pole so smerníkmi na záznamy, ich počet dá do n 
    n = d.size;
    itemType ** a = new itemType *[n]; // alokujeme pole
    int num = 0; // pocet zaplnenych prvkov v a
    for (int i = 0; i < d.m; i++) { // prejdeme cez hesovaciu tabulku
        node* v = d.data[i];
        while (v != NULL) { // prejdeme cez kazdy spajany zoznam
            a[num] = v->item; // vsetko pridavame do pola a
            num++;
            v = v->next;
        }
    }
    assert(num == n);
    return a;
}

int main() {
    dictionary d; // vytvorenie slovnika
    init(d, 19);

    char word[maxLen + 1];
    cin >> word;
    while (strcmp(word, "*") != 0) { // nacitavanie slov zo vstupu
        itemType *item = find(d, word); // najdeme zaznam pre slovo
        if (item != NULL) { // ak existuje, zvysime mu pocitadlo
            item->count++;
        } else { // ak zaznam neexistuje, vytvorime novy
            item = new itemType;
            item->str = new char[strlen(word) + 1]; // pamat pre slovo
            strcpy(item->str, word);
            item->count = 1;
            insert(d, item); // a vlozime ho do slovnika
        }
        cin >> word;
    }

    int n; // pocet zaznamov v slovniku
    itemType **a = items(d, n); // vsetky zaznamy v slovniku

    for (int i = 0; i < n; i++) { // vypis vsetky zaznamy
        cout << a[i]->str << " " << a[i]->count << endl;
    }

    for (int i = 0; i < n; i++) { // odalokuj vsetky zaznamy
        delete[] a[i]->str;
        delete a[i];
    }
    delete[] a; // odalokuj aj pole a

    destroy(d); // odalokuj samotny slovnik
}