FAV wiki - Příspěvky uživatele [cs]

Tabulky s rozptýlenými položkami, vyhledávání v tabulkách

2014-06-13T06:35:53Z

212.158.144.250: /* Otevřené rozptýlení - hash funkce */

To samé jako PPA2 14 a 15,

jen doplňky/opakování/upřesnění:

'''Vnitřní zřetězen'''í - synonyma (položky s kolizemi) se ukládají do volných míst

'''Vnější zřetězení''' - synonyma se ukládají do seznamů pod klíči

== Otevřené rozptýlení - hash funkce ==

Kolize:

1) nedefinované chování při kolizi - nutno dodefinovat

2) lineární posun - při kolizi vkládáme na první volné místo lineárně (na indexech 1,2,3,4 od původní polohy

3) kvadratický posun - při kolizi hledáme první volné místo na indexech podle kvadratické funkce (vzdálenosti 1, 4, 9, 16...)

4) opakovaný hash - hashovací fci použijeme víckrát pokud dojde ke kolizi

Pro rovnoměrné rozptýlení prvků v tabulce se rozptylová funkce skládá ze dvou částí. Například když máme rozdělovat do tabulky podle počátečních písmen jmen -> 26 písmen, ale od Q moc jmen není. Modulární rozptylová funkce se vynásobí multiplikativní konstantou. Konstanta ''c'' je z intervalu ''0 ≤ c < 1''. Příkladem takové funkce potom je ''H(m,k)=0,97 * k mod m'', kde ''k'' je klíč a ''m'' velikost pole.

== Uzavřené rozptýlení - přímé adresování ==

metody 2) a 3) nejsou vhodné, vzniká shlukování (clustering), proto je dobré použít způsob 4) nebo lepší hash funkci

== Tabulky s uzavřeným rozptýlením a vnějším zřetězením ==

= kombinace obou

- adresujeme přímo, při kolizi si ale do tabulky na konec uložíme, kam budeme vnitžně zřetězovat. Hash funkce tedy může být při kolizi (třeba náhodná), nebo tabulku rozdělíme na 2 části, jednu pro vyhledávání klíčů, a druhou pro ukládání synonym. ta už může být dynamicky alokovaná.

== Metoda rozptýlených indexů ==

To co bylo v předchozím případě v tabulce vyjmeme, a vytvoříme vedle. Uděláme si mapu synonym (synonyma v seznamu pro každý klíč) a tyto pak ukazují na index do pole.

== Vyhledávání ==

Má samozřejmě smysl jen pokud nemáme orákulum (= hashovací fci). Pokud orákulum máme, není třeba hledat protože ideální orákulum vždy ví, kam se podívat pro správná data (The all-knowing Oracle is never surprised. How can she be, she knows everything. -- The Matrix: Revolution), reálné ví aspoň kde hledat.

Jelikož je při přímém adresování orákulum pouhý index do tabulky (mno, to moc orákulum není, orákulum vždy ví, kam jít, aby nebyla kolize), alespoň nám napoví odkud hledat.

'''Sekvenční:'''

Hledáme klíč lineárně, pokud na něj narazíme, vrátíme hodnotu

+ snadná implementace

+ tabulka nemusí být uspořádaná

- pomalé hledání

'''Binární'''

Jako sekvenční, ale klíče musí být seřazeny, a nad nimi vytvoříme BVS, tedy hledáme vždy v půlce intervalu

+ rychlejší (O(log n))

- nutnost udržovat tabulku seřazenou

'''Fibonacciho'''

Jako binární, ale nerozdělujeme v polovině, ale podle Fibonacciho posloupnosti (tedy ne 1:1 -> 1:(1:1) -> 1:((1:1): 1) ale (1:1) -> (1:(1:2)) - > (1:((2:3):2))

Prvky vybíráme jako dvojice, první z dvojice je ve Fibonacciho posloupnosti na pozici odpovídající úrovni vnožení stromu (výška větve, ve které hledáme)

Fibonacciho ppst: a1 = 1, a2 = 1, ai = ai-1 + ai - 2 , tedy 1,1,2,3,5,8,13,21,34,55, ....

'''Podle sekundárního klíče'''

Jen pouze pokud sekundární klíč existuje v datech, např seznam jmen, jméno je primární (není, ale pro vysvětlení řekněme, že je) a rok je sekundární. Vyhledáme jména v sekundárním klíči a v nich pak hledáme jméno podle primárního klíče.

Sekundární klíče máme v seznamu, který obsahuje seznam primárních klíčů zabulky pro každý sekundární klíč

[[Kategorie:fav-kiv-bzinf]]

Rozptylové tabulky s s vnějším řetězením

2014-06-13T06:34:44Z

212.158.144.250:

HASH
Pokud máme množinu záznamů, ve které mohou v klíčích existovat duplicity pro různé hodnoty (například tabulka slov podle prvího písmena). Pro tento přístup je nemožné používat přímé adresování, jelikož by docházelo ke kolizím.

[[Soubor:Rozptylova-tabulka.jpg]]

Můžeme ale v poli využít prázdná místa a do nich duplicitní hodnoty ukládat. Vyhladávání a ukládání potom obecně nebude v konstantním čase. Můžeme tedy například uložit duplicitní hodnotu do následujícího prázdného místa v tabulce. Problémy jsou však následující:

Můžeme zabrat místo pro klíč, který má na toto místo právoplatný nárok (kolize tedy nastanou nejen pro hodnoty se stejným klíčem, ale i obecně pro libovolný klíč)
Odsuneme-li i tento klíč, dojde k vytváření shluků (a nabalovíní dalších klíču na tyto shluky, na obr. skluk od písmene A)
Dochází také k fragmentaci, je tedy nutné hledat až do prvního prázdného klíče, což je při shlukování a vyšší saturaci tabulky pomalé

Tento přístup tedy použijeme, pokud vímě, že jsou klíče hodnot rovnoměrně rozmístěny, a že hodnot není více než klíčů, a nazývá se vnitřní zřetězení.

Vnější zřetězení znamená, že ke kažnému klíči přiřadíme seznam hodnot. Nedochází tedy ke kolizím, ale vyhledání hodnoty je O(m), kde m je počet hodnot ke každému klíči, tedy nejhůže O(n) (všechny hodnoty jsou v jednom klíči). Tento způsob však zvládá i situace, kde je více hodnot než klíčů

Rozptýlení klíčů.

Pro vnitřní zřetezení lze použít lepší vyhledáváci (a ukládací) funkci, než lineární posun, třeba kvadratickou fci. Kvadratická funkce se může protonout s jinou kv. fcí s jiným počátkem jen jednou) Tím omezíme clustery a kolize, a ukládání a hledání je rychlejší.

Pro vnější zřetezení, nebo pokud je při vnitřním zřetězení mnoho podobných klíčů, je vhodné použít orákulum, rozptylovou (hashovací) funkci. Ta má 2 vlastnosti:

Namapuje hodnoty do rozsahu počtu klíčů
Ideálně zruší nebo alespoň naruší vztahy mezi podobnými klíči

Příklad: Slovník se vnitřním zřetězením. Slovo převedeme na číslo součtem ASCII hodnot znaků

Vlastnost 1: na toto číslo použijeme operaci modulo. Tato operace je pomalá (jde o dělení), použijeme tedy ideálně velikosti tabulky, které jsou mocninou 2, a po té je dělení pouhým bitovým posunem
Vlastnost 2: vazby v tomto postupu existují (například anagramy se namapují do stejného pole). Použijeme tedy například následující postup: (( (1. písmeno * (2k+1) ) + 2. písmeno) * (2k+1)) + ... Tím zrušíme vazby mezi podobnými slovy. (2k+1) použijeme, protože jde o bitový posun a přičtení 1, což je velmi rychlé a 1 přičítáme, protože by poté modulo ztratilo význam.

Pro rovnoměrné rozptýlení prvků v tabulce se rozptylová funkce skládá ze dvou částí. Například když máme rozdělovat do tabulky podle počátečních písmen jmen -> 26 písmen, ale od Q moc jmen není. Modulární rozptylová funkce se vynásobí multiplikativní konstantou. Konstanta ''c'' je z intervalu ''0 ≤ c < 1''. Příkladem takové funkce potom je ''H(m,k)=0,97 * k mod m'', kde ''k'' je klíč a ''m'' velikost pole.

Mohli bychom použít i kryptografické hashování, jako MD5, to je však pro O(1) přístup k seznamům příliš pomalé.

{{fav-kiv-bzinf}}
[[Kategorie:fav-kiv-bzinf]]

Rozptylové tabulky s s vnějším řetězením

2014-06-13T06:34:16Z

212.158.144.250: Přidání informací o rozšířené rozptylovací funkci

HASH
Pokud máme množinu záznamů, ve které mohou v klíčích existovat duplicity pro různé hodnoty (například tabulka slov podle prvího písmena). Pro tento přístup je nemožné používat přímé adresování, jelikož by docházelo ke kolizím.

[[Soubor:Rozptylova-tabulka.jpg]]

Můžeme ale v poli využít prázdná místa a do nich duplicitní hodnoty ukládat. Vyhladávání a ukládání potom obecně nebude v konstantním čase. Můžeme tedy například uložit duplicitní hodnotu do následujícího prázdného místa v tabulce. Problémy jsou však následující:

Můžeme zabrat místo pro klíč, který má na toto místo právoplatný nárok (kolize tedy nastanou nejen pro hodnoty se stejným klíčem, ale i obecně pro libovolný klíč)
Odsuneme-li i tento klíč, dojde k vytváření shluků (a nabalovíní dalších klíču na tyto shluky, na obr. skluk od písmene A)
Dochází také k fragmentaci, je tedy nutné hledat až do prvního prázdného klíče, což je při shlukování a vyšší saturaci tabulky pomalé

Tento přístup tedy použijeme, pokud vímě, že jsou klíče hodnot rovnoměrně rozmístěny, a že hodnot není více než klíčů, a nazývá se vnitřní zřetězení.

Vnější zřetězení znamená, že ke kažnému klíči přiřadíme seznam hodnot. Nedochází tedy ke kolizím, ale vyhledání hodnoty je O(m), kde m je počet hodnot ke každému klíči, tedy nejhůže O(n) (všechny hodnoty jsou v jednom klíči). Tento způsob však zvládá i situace, kde je více hodnot než klíčů

Rozptýlení klíčů.

Pro vnitřní zřetezení lze použít lepší vyhledáváci (a ukládací) funkci, než lineární posun, třeba kvadratickou fci. Kvadratická funkce se může protonout s jinou kv. fcí s jiným počátkem jen jednou) Tím omezíme clustery a kolize, a ukládání a hledání je rychlejší.

Pro vnější zřetezení, nebo pokud je při vnitřním zřetězení mnoho podobných klíčů, je vhodné použít orákulum, rozptylovou (hashovací) funkci. Ta má 2 vlastnosti:

Namapuje hodnoty do rozsahu počtu klíčů
Ideálně zruší nebo alespoň naruší vztahy mezi podobnými klíči

Příklad: Slovník se vnitřním zřetězením. Slovo převedeme na číslo součtem ASCII hodnot znaků

Vlastnost 1: na toto číslo použijeme operaci modulo. Tato operace je pomalá (jde o dělení), použijeme tedy ideálně velikosti tabulky, které jsou mocninou 2, a po té je dělení pouhým bitovým posunem
Vlastnost 2: vazby v tomto postupu existují (například anagramy se namapují do stejného pole). Použijeme tedy například následující postup: (( (1. písmeno * (2k+1) ) + 2. písmeno) * (2k+1)) + ... Tím zrušíme vazby mezi podobnými slovy. (2k+1) použijeme, protože jde o bitový posun a přičtení 1, což je velmi rychlé a 1 přičítáme, protože by poté modulo ztratilo význam.

Pro rovnoměrné rozptýlení prvků v tabulce se rozptylová funkce skládá ze dvou částí. Například když máme rozdělovat do tabulky podle počátečních písmen jmen -> 26 písmen, ale od Q moc jmen není. Modulární rozptylová funkce se vynásobí multiplikativní konstantou. Konstanta ''c'' je z intervalu ''0 ≤ c < 1''. Příkladem takové funkce potom je ''H(m,k)=0,97 * k mod m'', kde ''k'' je klíč a ''m'' velikost pole.

Mohli bychom použít i kdyptografické hashování, jako MD5, to je však pro O(1) přístup k seznamům příliš pomalé.

{{fav-kiv-bzinf}}
[[Kategorie:fav-kiv-bzinf]]