Razpršena tabela predstavljena v Mathematici

Iz MaFiRaWiki

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

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


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


Vsebina

Uvod

Problem urejanja in hitrega iskanja podatkov po ključih v statični tabeli je en od starejših problemov s področja podatkovnih struktur. In sicer gre za problem, da je območje ključev, po katerih razvrščamo in iščemo podatke v tabelah, torej njihovi "naslovi", pogosto bistveno večje od števila podatkov, ki bodo resnično nastopili. To je običajno posledica načina generiranja ključev, ko ključe sestavljamo iz polj, ki pomenijo neke atribute (npr. v študentski evidenci koda fakultete, letnica vpisa, koda študijskega programa in smeri ter zaporedna številka študenta v njem). Takšni ključi so seveda dolgi in ne morejo neposredno določati indeksa podatka v statični tabeli, kar bi bilo sicer najbolj elegantno in najhitrejše. Zaradi ekonomičnega izkoriščanja pomnilniškega prostora - velikosti tabel - torej te ključe transformiramo v dejanske indekse, ki določajo mesto v statični tabeli.

Definicija in osnovni podatki

Razpršena oziroma zgoščena tabela (hash table) je ena izmed pomembnejših predstavitev tabele simbolov. Z njo si pogosto pomagajo prevajalniki. To je podatkovna struktura, ki hrani pare (k, e) tako, da je omogočen direkten dostop do para glede na prvi argument k. Pri slovarju par (k, e) interpretiramo kot oznako ali ključ k ter vsebino e danega elementa. Poleg implementacije abstraktnega podatkovnega tipa preslikave se razpršena tabela najpogosteje uporablja za implementacijo slovarja s tremi osnovnimi operacijami: iskanjem, vstavljanjem in brisanjem elementov.

Angleški naziv "hash table" različni avtorji prevajajo v slovenščino kot "zgoščena" ali kot "razpršena" tabela. Čeprav naziva izgledata na prvi pogled kontradiktorna, imata vsak svoj smisel: v njih so tabele, kot jih naslavljajo njihovi dejanski naslovi (ključi) res zgoščene, obenem pa želimo, da so podatki v zgoščenih tabelah čim bolj enakomerno razpršeni.

Ker se konfliktom, ko različni ključi generirajo iste indekse (primarni trki), posebej, ko želimo čim bolj izkoristiti tabelo, ne moremo izogniti, lahko te konflikte rešujemo na različne načine. In sicer razreševanje primarnih trkov je lahko zunanje, v tem primeru uporabimo veriženje, ali pa notranje: ponovno zgoščevanje, linearno naslavljanje, kvadratno naslavljanje,... Prednost veriženja je v tem, da deluje tudi potem, ko je razpršena tabela polna. Ima pa tudi slabost, saj vstavljanje, iskanje in brisanje lahko "dolgo" traja (O(d) časa, kjer je d dolžina verige). Ponovno zgoščevanje slabše deluje, ko se tabela polni. Pri tem razreševanju trkov je tudi težko izbrati "pametno" zaporedje razpršitvenih funkcij in pa sekundarni trki lahko nastopijo, tudi če ni primarnega trka.

Zahtevnost postopkov vstavljanja oz. iskanja podatkov je konstanten, oz. neodvisen od števila podatkov v tabeli. Odvisen pa je od faktorja zasedenosti, torej razmerja med prostorom v tabeli in številom uporabljenih mest; iz tega podatka lahko tudi ocenimo kakovost razpršitvene funkcije in s tem pričakovani čas iskanja podatkov.

V nadaljevanju si bomo ogledali, kako lahko razpršeno tabelo sprogramiramo v programu Mathematica, nekaj razpršitvenih funkcij in pa primerjavo le teh.

Razpršitvene funkcije

Funkcijo, s katero določimo mesto vstavljanja elementa v tabeli, imenujemo razpršitvena oziroma zgoščevalna funkcija. Oglejmo si nekaj primerov razpršitvenih funkcij:

  • Funkcija f postavi prvi znak iz niza v razpršeno tabelo velikosti n, na mesto, ki ga dobimo če kodo znaka izračunamo po modulu n in prištejemo 1:
f[l_, n_] := Mod[First[ToCharacterCode[l]], n] + 1
  • Funkcija g uporabi metodo deljenja, in sicer število l, izračunano po modulu velikosti razpršene tabele n, nam pove mesto vstavljanja v tabeli:
g[l_,n_]:=Mod[l,n]/. 0\[Rule]n
  • Funkcija h1 uporabi metodo množenja, in sicer število l pomnožimo s številom C, nato vzamemo decimalni del rezultata ter dobljeno število pomnožimo z n. Rezultatu še odrežemo celoštevilski del ter prištejemo ena. Na ta način smo dobili mesto vstavljanja v razpršeni tabeli.
h1[C_] [l_,n_]:=Floor[n FractionalPart[N[l C]]]+1
  • Knuth predlaga, da za C vzamemo kar \frac{\sqrt{5}-1}{2}:
h2[l_,n_]:=h1[(Sqrt[5]-1)/2][l,n]

Primeri

{f["Mojca",7],f["Bedanec",7],f["Rožle",7],f["Kekec",7],f["Pehta",7],f["Vitranc",7],f["Kosobrin",7]}
{1,4,6,6,4,3,6}
Table[g[i,7],{i,23456,23470}]
{6,7,1,2,3,4,5,6,7,1,2,3,4,5,6}
Table[h1[Sqrt[6]][i,7],{i,23456,23470}]
{2,5,1,5,1,4,7,3,6,2,6,2,5,1,4}
Table[h2[i,7],{i,23456,23470}]
{5,2,6,4,1,5,3,7,4,2,6,3,1,5,2}

Primerjava razpršitvenih funkcij

Razpršitvene funkcije bomo primerjali med seboj tako, da bomo šteli trke, ki nastanejo pri posameznem "razprševanju" elementov. Za množico elementov si izberimo kar števila od 534 pa do 1300. Naša razpšena tabela bo velikosti 200. Primerjali bomo funkcije g, h1 in h2. A,B,F predstavljajo razpršene tabele:

A=Table[g[i,200],{i,534,1300}];
B=Table[h1[Sqrt[5]][i,200],{i,534,1300}];
F=Table[h2[i,200],{i,534,1300}];

Oglejmo si kako so funkcije "razpršile" elemente v tabelo (tabela predstavlja število elementov, ki se nahajajo na i-tem mestu v razpršeni tabeli):

A1=Table[Count[A,i],{i,200}]
{4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,
4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,
4,4,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,4,4,4,4,4,4,4,4,4,4,4,4,4,4,
4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,
4,4,4,4}
B1=Table[Count[B,i],{i,200}]
{4,4,3,5,3,4,4,3,5,3,4,4,5,2,6,2,5,3,4,4,4,3,5,3,3,5,3,4,4,3,4,4,3,5,3,4,5,4,3,5,2,5,3,4,4,4,3,5,4,
3,5,3,4,4,4,3,5,2,6,3,4,4,4,3,5,3,4,4,3,5,3,4,3,5,2,6,2,5,3,4,4,4,3,5,4,3,5,3,4,4,4,3,4,3,5,4,4,4,
4,3,5,3,4,3,4,4,5,3,4,4,3,5,3,4,4,4,3,5,2,5,3,4,4,4,3,5,3,4,4,3,5,4,4,3,5,2,6,2,5,3,4,4,5,3,4,4,3,
5,3,4,4,4,3,6,2,4,4,4,4,4,3,5,3,4,4,3,3,5,3,4,4,3,5,3,4,4,4,3,6,2,5,3,4,4,4,3,5,3,4,5,3,4,4,4,3,5,
2,6,2,5}
F1=Table[Count[F,i],{i,200}]
{4,4,4,3,4,4,4,4,4,4,3,4,4,4,4,4,4,3,4,4,4,3,4,4,4,4,4,4,3,4,4,4,4,4,4,3,4,4,4,3,4,4,4,4,4,4,3,4,4,
4,4,3,4,4,4,4,4,4,4,3,4,4,4,4,3,4,3,4,4,4,4,4,4,4,4,4,4,3,4,4,4,4,3,4,3,4,4,4,4,4,4,4,4,4,4,3,4,4,
4,4,4,4,3,4,4,4,3,4,4,4,4,4,4,3,3,4,4,4,5,4,3,4,4,4,3,4,4,3,4,5,4,3,4,4,4,4,4,4,3,4,4,4,3,4,4,3,4,
5,4,3,4,4,4,4,4,4,3,4,4,4,3,4,4,3,4,5,4,3,4,4,4,4,4,4,3,4,5,3,4,4,4,3,4,4,4,3,4,4,3,4,4,4,3,4,5,4,
4,4,4,3}

Preštejmo še koliko je takšnih "podseznamov", ki so dolžine od 1 do 6:

Table[Count[A1,i],{i,6}]
{0,0,33,167,0,0}
Table[Count[B1,i],{i,6}]
{0,13,60,81,39,7}
Table[Count[F1,i],{i,6}]
{0,0,39,155,6,0}

Opazimo, da je elemente najbolj enakomerno razporedila funkcija g. Funkcija h1 je sedmim ključem priredila vsakemu po šest elementov, kar 39 klučem pa vsakemu po pet elementov. Malo slabše kot funkcija g je razprševala funkcija h2.

Predstavitev razpršene tabele

Naj bo f razpršitvena funkcija in d1, d2 ključa. Primrani trk pri zgoščevanju natane, ko je f(d1) = f(d2) in d_1\neq d_2. Ogledali si bomo reševanje primarnih trkov z veriženjem in linearnim naslavljanjem.

Reševanje primarnih trkov z veriženjem

Razpršeno tabelo lahko predstavimo s seznamom, kateri ima za elemente sezname, v katerih so elementi, ki jih vstavljamo v tabelo. Primarne trke pri zgoščevanju v tem primeru razrešimo z veriženjem (element pripnemo na konec seznama, ki je na mestu v tabeli, ki jo vrne razpršitvena funkcija):

Clear[Pripravi,Vstavi,Isci,Odstrani]

Pripravi[n_Integer]:=Table[{},{n}]

Vstavi[s_,l_,f_]:=Module[{i,n},
   n=Length[s];
   i=f[l,n];
   ReplacePart[s,Append[si,l],i]
   ]
 
Isci[s_,l_,f_]:=Module[{i,n},
   n=Length[s];
   i=f[l,n];
   MemberQ[si,l]
   ]

Odstrani[s_,l_,f_]:=Module[{i,n},
   n=Length[s];
   i=f[l,n];
   ReplacePart[s,DeleteCases[si,l],i]
   ]

Primer

Vstavi[Pripravi[5],"a",f]
{{},{},{a},{},{}}
Vstavi[%,"b",f]
{{},{},{a},{b},{}}
Vstavi[%,"z",f]
{{},{},{a,z},{b},{}}
Vstavi[%,"f",f]
{{},{},{a,z,f},{b},{}}
r=Vstavi[%,"i",f]
{{i},{},{a,z,f},{b},{}}
Isci[r,"b",f]
True
Isci[r,"s",f]
False
Odstrani[r,"a",f]
{{i},{},{z,f},{b},{}}

Reševanje primarnih trkov z linearnim naslavljanjem

Razpršeno tabelo pa sedaj predstavimo s seznamom elementov, ki jih vstavljamo v tabelo, le da primarne trke pri zgoščevanju v tem primeru razrešimo z linearnim naslavljanjem. Potrebno je definirati še dve razpršitveni funkciji:

Prvi znak v nizu nam predstavlja mesto v razpršeni tabeli (tabela je velikosti n):

f2[l_,i_,n_]:=Mod[f[l,n]+i,n]+1

Metoda deljenja: število l nam (po modulu velikosti tabele n) predstavlja ker pozicijo v tabeli:

g2[l_,i_,n_]:=Mod[g[l,n]+i,n]/. 0\[Rule]n
Clear[Pripravi,Vstavi, Isci]

Pripravi[n_]:=Table[Null,{n}]

Vstavi[s_,l_,f_,j_:0]:=Module[{i,n},
   n=Length[s];
   i=f[l,j,n];
   If[si===Null,ReplacePart[s,l,i],Vstavi[s,l,f,j+1]]
   ]
Vstavi[s_,l_,f_,j_:0]/;j===Length[s]:=s

Isci[s_,l_,f_]:=Module[{i,j,n},
   n=Length[s];
   i=0;
   While[i≠n && s[[j=f[l,i,n]]]=!=Null,
     If[sj===l,Return[j]];
     i++;
     ];
   Return["Elementa ni v tabeli."];
   ]

Primer

Pripravi[8]
{Null,Null,Null,Null,Null,Null,Null,Null}
Vstavi[%,"m",f2]
{Null,Null,Null,Null,Null,Null,m,Null}
Vstavi[%,"r",f2]
{Null,Null,Null,r,Null,Null,m,Null}
Vstavi[%,"a",f2]
{Null,Null,a,r,Null,Null,m,Null}
Vstavi[%,"b",f2]
{Null,Null,a,r,b,Null,m,Null}
d=Vstavi[%,"m",f2]
{Null,Null,a,r,b,Null,m,m}
Isci[d,"r",f2]
4
Isci[d,"c",f2]
Elementa ni v tabeli.

Ko je tabela polna ne moremo več vstavljati. Na primer:

{a,f,z,u};
Vstavi[%,"b",f2]
{a,f,z,u}

Glej tudi

Osebna orodja