Zgoščena tabela/TinaKrmac

Iz MaFiRaWiki

GFDL Avtor tega članka je študent/ka TinaKrmac.

Pripravil/a ga je pri predmetu Računalništvo 2 (FMF PRA).


Kljub temu ste vsi vabljeni k urejanju in popravkom, saj je bistvo wikija ravno v sodelovalnem delu.

Vsebina

Definicija

Zgoščevalna tabela je podatkovna struktura, ki hrani pare (d, r) tako, da je omogočen direkten dostop do para glede na prvi argument d. Naravna implementacija zgoščevalne tabele je zato polje. Poleg implementacije abstraktnega podatkovnega tipa preslikave se zgoščevalne tabela najpogosteje uporablja za implementacijo slovarja s tremi osnovnimi operacijami: iskanjem, dodajanjem in brisanjem elementov. Pri slovarju par (d, r) interpretiramo kot oznako ali ključ d ter vsebino r danega elementa.

Reševanje problemov

Pri zgoščevalne tabeli je potrebno rešiti naslednje probleme:

  • Izbira veklikosti tabele oziroma polja, ki tabelo implementira. Idealna velikost je taka, kjer je število elementov polja enako številu parov dane preslikave. Temu pogoju je težko zadostiti, saj števila parov razen v izjemnih primerih ne poznamo. Pri tem bi morala biti zagotovljena tudi injektivnost zgoščevalne funkcije, tj. funkcija ne bi smela preslikati nobenih dveh elemetov iz originalne domene v isti element nove domene, kar je v praksi težko, če že ne nemogoče doseči.

  • Izbira ustrezne zgoščevalne funkcije. Idealna funkcija bi morala biti injektivna, kar je pri omejeni velikosti tabele in neznani podmnožici originalne domene praktično nemogoče doseči.

  • Reševanje problema neinjektivnosti zgoščevalne funkcije h, tj. sovpadanje dveh parov (d1,r1) in (d2,r2):

    d_1 \neq d_2 \wedge h(d_1) = h(d_2)

Ponovno zgoščevanje

Problem velikosti tabele lahko rešimo tako, da začnemo z dovolj majhno tabelo. Ko se tabela (preveč) napolni in postanejo zaradi tega operacije prepočasne, zgradimo novo, večjo tabelo ter vse elemente iz manjše tabele uvrstimo v novo tabelo z novo zgoščevalno funkcijo. Ponovno zgoščevanje zahteva O(n) časa, če je n število elementov v manjši tabeli. Na podoben način lahko tabelo tudi zmanjšamo, če je tabela dovolj redka in zaseda preveč pomnilnika. Tako simuliramo dinamično podatkovno strukturo.
Naj bo m začetna velikost tabele. Čas, potreben, da se tabela napolni, je večji ali enak času vstavljanja m elementov. Če po napolnitvi razpršimo tabelo v tabelo velikosti 2m, je za to potrebno spet m vstavljanj elementov v tabelo. če k-krat povečamo velikost tabele, je časovna zahtevnost vseh operacij na tabeli večja ali enaka:

\sum_{i=0}^k 2^i m = m(2^{k+1} - 1)

Od tega je vsaj 2km operacij potrebnih za vstavljanje ter (2k − 1)m za ponovno zgoščanje. To pomeni, da ponovno zgoščanje v najslabšem primeru podvoji povprečno časovno zahtevnost operacij na zgoščeni tabeli, kar je sprejemljivo.


Izbira zgoščevalne funkcije

Osnovna zgoščevalna funkcija predstavlja, da je originalna domena kar množica naravnih števil, zmanjšana domena pa naravna števila od 1 do m, kjer je m velikost zgoščene tabele:

h(x) = (x\mod n) + 1

Ob predpostavki, da so vsa naravna števila (do ponavadi neke zgornje meje) enako verjetna, taka funkcija enakomerno razporedi pare po tabeli. Dobro je, da zgoščevalna funkcija pri izračunu upošteva vse simbole, ki definirajo element iz originalne domene. To pomeni, da če izberemo za m = 2i pri računalnikih, ki števila predstavljajo z dvojiškim zapisom, bo funkcija pri izračuno upoštevala samo zadnjih i bitov. Zato je pri izbiri m potrebno paziti. V praksi se dobro obnese, če je m praštevilo, ki ni blizu 2i za nek i. Vsekakor pa je dobro izbrano funkcijo najprej pretestirati, kako se obnaša na ciljenm intervalu naravnih števil.

Obravnavanje sovpadanja

Sovpadanje lahko rešimo na dva osnovna načina: Zaprta zgoščevalna tabela zaseda manj pomnilniškega prostora kot odprta in je lahko za določene aplikacije boljša alternativa. Vendar ima tudi slabosti:

  • Pri iskanju elementa je potrebno pregledovati elemente polja prvega praznega prostora. V najslabšem možnem primeru to pomeni časovno zahtevnost reda O(n), kjer je n število elementov, ki so že v tabeli.
  • pri brisanju elementa iz zaprte tabele je potrebno na mesto zbrisanega elementa zapisati neko posebno vrednost, ki označuje, da element polja ni bil od vsega začetka prazen. To je potrebno zato, da lahko iskanje elementa nadaljujemo vedno od prvega praznega elementa in pri tem preskakujemo elemente, ki so bili nekoč že zasedeni. Pri vstavljanju novih elementov pa lahko take elemente polja zapolnimo z novimi elementi.
  • Pri zapri zgoščevalni tabeli velja, da mora biti velikost tabele m večja od števila elementov n , saj za već elementov preprosto ni prostora. Ko se n približa m , postane tabela zapolnjena in postanejo operacije iskanja, dodajanja in brisanja elementov nesprejemljivo počasne. Zato se zaprta Zgoščevalna tabela uporablja samo, če dobro poznamo pričakovano število elementov v tabeli.


Pri odprti Zgoščevalni tabeli v polju hranimo kazalce na seznam parov, ki sovpadajo. Če predpostavimo, da so vsi položaji v tabeli enako verjetni, potem je pri velikosti tabele m in n dodanih elementih v tabeli pričakovana dolžina vsakega seznama enaka m / n. To pa pomeni, da je pričakovana časovna zahtevnost iskanja in brisanja elemnta enaka O(n/m). Če velja m \simeq n, potem imamo v povprečju zagotovljen konstanten čas iskanja elementa v odprti Zgoščevalna tabeli. časovna zahtevnost dodajanja novega elementa pa je vedno O(1).
Pri zaprti Zgoščevalni tabeli v polju namesto kazalcev hranimo kar elmente. Zaprta Zgoščevalna tabela uporablja zaporedje zgoščevalnih funkcij: h0,h1,... V primetu sovpadanja izračunane vrednosti po prvi zgoščevalni funkciji izračunamo naslednji možni položaj novega elemnta z drugo funkcijo. Novi elemnt dodamo v prvi naslednji prazni element polja, ki ga izračuna naslenja zgoščevalna funkcija iz podanega zaporedja funkcij. Najbolj preprosto zaporednje funkcij je naslednje:

h'(x)_i = (h(x) + i) \mod m + 1

kjer je h(\cdot) običajna zgoščevalna funkcija. Tako zaporedje preiskuje polje po vrsti naprej od položaja, ki ga vrne prva funkcija h.
Boljša varianta je zaporedje funkcij:

h'(x)_i = (h_1(x) + i x h_2(x)) \mod m + 1

kjer sta h1 in h2 poljubni zgoščevalni funkciji. Npr.:

h_1 = x \mod m + 1

za neko praštevilo m in

h_2(x) = (x\mod m') + 2

kjer je m' = m − 1 ali m' = m − 2.

Zaprta Zgoščevalna tabela zaseda manj pomnilniškega prostora kot odprta in je lahko za določene aplikacije boljša alternativa. Vendar ima tudi slabosti:

  • Pri iskanju elementa je potrebno pregledovati elemente polja prvega praznega prostora. V najslabšem možnem primeru to pomeni časovno zahtevnost reda O(n), kjer je n število elementov, ki so že v tabeli.
  • pri brisanju elementa iz zaprte tabele je potrebno na mesto zbrisanega elementa zapisati neko posebno vrednost, ki označuje, da element polja ni bil od vsega začetka prazen. To je potrebno zato, da lahko iskanje elementa nadaljujemo vedno od prvega praznega elementa in pri tem preskakujemo elemente, ki so bili nekoč že zasedeni. Pri vstavljanju novih elementov pa lahko take elemente polja zapolnimo z novimi elementi.
  • Pri zapri Zgoščevalni tabeli velja, da mora biti velikost tabele m večja od števila elementov n , saj za već elementov preprosto ni prostora. Ko se n približa m , postane tabela zapolnjena in postanejo operacije iskanja, dodajanja in brisanja elementov nesprejemljivo počasne. Zato se zaprta Zgoščevalna tabela uporablja samo, če dobro poznamo pričakovano število elementov v tabeli.



Slabosti Zgoščevalnih tabel

Slabosti uporabe Zgoščevalnih tabel pri implementaciji bodisi preslikave ali pa slovarja so naslednje:

  • zgoščevalna tabela zaradi fiksne zgoščevalne funkcije ne more biti dinamična podatkovna struktura. Velikost tabele n moramo definirati v naprej, čeprav vnaprej ne poznamo števila elementov, ki jih bomo vstavili v tabelo. To pomeni, da lahko bodisi po nepotrebnem zapravljamo računalniški prostor, ker je izbrana tabela prevelika, ali pa zaradi premajhne tabele pride do prevelikega sovpadanja elementov in se časovna zahtevnost iz konstante O(1) izrodi v O(n/m), kjer je m velikost tabele, < n število elementov v tabeli in je m \ll n.

  • Če uporabimo metodo ponovnega zgoščanja, imamo sicer povprečni čas operacij zagotovljeno majhen, vendar je posamezna operacija ponovnega zgoščanja počasna in zato mogoče nesprejemljiva za določene vrste aplikacij.

  • Ker mora biti zgoščevalna funkcija fiksna, je ne moremo prilagoditi spremenjeni distribuciji elementov, ki jih shranjujemo. To pa pomeni, da se v najslabšem možnem primeru Zgoščevalna tabela lahko izrodi v seznam (vsi elementi pri dani zgoščevalni funkciji sovpadajo). To pa pomeni porazno časovno zahtevnost operacij, ki je za sezname reda O(n).
  • pogosto poleg osnovnih operacij iskanja, vstavljanja in brisanja elementov potrebujemo tudi operacije, ki temeljijo na urejenosti elementov po ključih: iskanje minimalnega in maksimalnega elementa, operaciji iskanja predhodnika in naslednika danega elementa ter operacije urejenega izpisa elementov na danem intervalu. Teh operacij v Zgoščevalni tabeli ni možno učinkovito implementirati.

Pogledi
Osebna orodja
Navigacija
posebne strani
Orodjarna