© Květuše Sýkorová
20.05.2016
• vyhledávací algoritmy – Brute Force – Binary Search – Interpolation Search
• indexové soubory
© Květuše Sýkorová
– Dense index, Sparse index
• transformační funkce – Perfect Hash, Close Hash Table, Open Hash Table
• vyhledávací stromové struktury – binary tree, digi tree, BST, B‐tree, AVL tree, R‐B tree, Trie, …
1
20.05.2016
• Co potřebujeme zjistit? – funkce: • – čas potřebný pro nalezení/nenalezení záznamu s danou hodnotou klíče ) (
• – čas potřebný pro přidání záznamu (uspořádání vstupních dat)
• © Květuše Sýkorová
– čas potřebný pro odebrání záznamu (logicky/fyzicky)
•
, – čas potřebný pro nalezení 1. záznamu, n‐tého záznamu
•
, – čas potřebný pro nalezení předchozího záznamu, následujícího záznamu » má smysl jen v některých případech
• funkce: – • hledáme záznam s hodnotou klíče – hledáme takové i, kde 0 » hledáme všechna taková i
∗
pro které platí:
∗
– • přidáváme záznam s hodnotou klíče
∗
© Květuše Sýkorová
– nesmí být porušena organizace vstupního souboru (setřídění, struktura)
– • odebíráme záznam s hodnotou klíče
∗
– záznam musíme nejdříve nalézt + ??? » tj. – mazání logické nebo fyzické (pokud to jde)
2
20.05.2016
• vyhledávání hrubou silou – lineární vyhledávání (linear search) – sekvenční vyhledávání
• nejjednodušší způsob vyhledávání – nepředpokládá žádnou organizaci dat na vstupu • „nulová chytrost“ algoritmu © Květuše Sýkorová
– prochází posloupnost klíčů od začátku do konce
– doplňuje ostatní vyhledávací algoritmy • vyhledání záznamů s duplicitní hodnotou klíče – vstupní soubor určitým způsobem organizován (setříděn)
• binární vyhledávání – vyhledávání pomocí bisekce (bisection search) – vyhledávání půlením intervalu (half‐interval search)
• nejběžnější způsob vyhledávání – předpokládá na vstupu setříděnou posloupnost záznamů
© Květuše Sýkorová
• využívá numerickou metodu „půlení intervalu“ – v každém kroku je eliminována ta část souboru, kde se hledaný klíč určitě nevyskytuje
3
20.05.2016
• interpolační vyhledávání – vyhledávání pomocí lineární interpolace – extrapolační vyhledávání (extrapolation search)
• další, rychlejší způsob vyhledávání – předpokládá na vstupu setříděnou posloupnost záznamů
© Květuše Sýkorová
• pro vyhledávání využívá numerickou metodu interpolace, tj. metodu „regula falsi“ (metoda sečen) – v každém kroku je eliminována ta část pole, kde se hledaný klíč určitě nevyskytuje – obtížnější výpočet (vhodné pro třídění neindexovaných dat na disku)
– pouze pro unikátní hodnoty klíčů • předpokládá rovnoměrné rozložení hodnot klíčů
• Algoritmus: – pro
0,1,2, … ,
• porovnáme
1 s hledaným
∗
∗ , pak algoritmus končí nalezením záznamu
© Květuše Sýkorová
– pokud » v případě duplicitních hodnot pokračujeme v hledání až do konce ∗ , pak pokračujeme v hledání pro 1 – pokud
4
20.05.2016
• Algoritmus: – porovnáme krajní hodnoty • tj.
∗
s hledaným
a
s hledaným
∗
– není nutné
0 a
– pro
1
• spočteme index • porovnáme
∗
s hledaným
© Květuše Sýkorová
∗ , pak algoritmus končí nalezením záznamu – pokud » v případě duplicitních hodnot pokračujeme v hledání Brute Force ∗ , pak pokračujeme v hledání pro – pokud » tj. budeme pokračovat v hledání na intervalu , ∗ , pak pokračujeme v hledání pro – pokud » tj. budeme pokračovat v hledání na intervalu ,
• Algoritmus: – porovnáme krajní hodnoty • tj.
∗
s hledaným
a
s hledaným
∗
– není nutné
– pro
0 a
1 ∗
• spočteme index
© Květuše Sýkorová
• porovnáme
s hledaným
∙ ∗
∗ , pak algoritmus končí nalezením záznamu
– pokud ∗ , pak pokračujeme v hledání pro – pokud » tj. budeme pokračovat v hledání na intervalu , ∗ – pokud , pak pokračujeme v hledání pro » tj. budeme pokračovat v hledání na intervalu ,
1 1
5
20.05.2016
• Kdy hledání ukončit? – nalezením záznamu se stejným klíčem ∗
• najdu i, pro které platí
1
– v tomto případě platí: 0
• Problém: duplicitní hodnoty klíčů – nutné prohledat celý soubor záznamů ( ), » „odfláknuté“ vyhledávání – nedoporučuje se,
© Květuše Sýkorová
– nenalezením záznamu se stejným klíčem • prohledávání skončí neúspěchem • nutné informovat o nenalezení – v tomto případě platí:
• Problém: nastavit se na určitý záznam v souboru s „podobným“ klíčem – nesetříděný soubor: nastavit na konec souboru
• Kdy hledání ukončit? – nalezením záznamu se stejným klíčem ∗
• najdu s, pro které platí 1
– v tomto případě platí:
• Problém: duplicitní hodnoty klíčů – nutné dohledat další záznamy (Brute Force) oběma směry, » „odfláknuté“ vyhledávání – nedoporučuje se
© Květuše Sýkorová
– nenalezením záznamu se stejným klíčem • prohledávání skončí neúspěchem • nutné informovat o nenalezení – v tomto případě platí:
1
• Problém: nastavit se na určitý záznam v souboru s „podobným“ klíčem – setříděný soubor: nastavit na předchozí nebo následující pozici ∗ ∗ nebo ? » Co v případě
6
20.05.2016
• Kdy hledání ukončit? – nalezením záznamu se stejným klíčem ∗
• najdu s, pro které platí 1
– v tomto případě platí:
• Problém: duplicitní hodnoty klíčů – NEDOPORUČUJE SE: narušuje rovnoměrné rozdělení hodnot klíčů
– nenalezením záznamu se stejným klíčem © Květuše Sýkorová
• prohledávání skončí neúspěchem • nutné informovat o nenalezení 1
– v tomto případě platí:
• Problém: nastavit se na určitý záznam v souboru s „podobným“ klíčem – setříděný soubor: nastavit na předchozí nebo následující pozici ∗ ∗ nebo ? » Co v případě
0
1
2
3
4
5
6
7
8
9
10
11
12
1
3
5
7
9
11
13
15
17
19
21
23
25
∗
17
0 →
1
∗
1 →
3
∗
2 →
5
∗
© Květuše Sýkorová
atd. 8 →
17
∗
→
∗
duplicita klíčů = pokračujeme dál v prohledávání až do konce
7
20.05.2016
0
1
2
3
4
5
6
7
8
9
10
11
12
1
3
5
7
9
11
13
15
17
19
21
23
25
∗
8
0 →
1
∗
1 →
3
∗
2 →
5
∗
∗
∗
© Květuše Sýkorová
atd. 12 →
25
prohledán celý vstup
0
1
2
3
4
5
6
7
8
9
10
11
12
1
3
5
7
9
11
13
15
17
19
21
23
25
∗
17
0 →
7,
0,
12 →
6,
12 →
6,
9→ 9→
0
12 12 2
6
9 2
7
9 2
∗
25
2 6
∗
1
12 →
© Květuše Sýkorová
→
6 →
13
∗
9 →
19
∗ →
7 → 8 8 →
∗
15 17
∗
→
→
→ ∗
8
20.05.2016
0
1
2
3
4
5
6
7
8
9
10
11
12
1
3
5
7
9
11
13
15
17
19
21
23
25
∗
8
0 →
© Květuše Sýkorová
12 → 0,
12 →
0,
6→
3,
6→
3,
4 →
0
12 6
2 3
6 2
6 →
∗
13
3 →
7
∗ →
4 →
9
∗ →
→
∗
1 1 →
0
1
2
3
4
5
6
7
8
9
10
11
12
1
3
5
7
9
11
13
15
17
19
21
23
25
∗
0 →
0
17
1 ∙ 12 25 1
25 0
8 →
∗ ∗
17
∗
→
∗
© Květuše Sýkorová
12 →
17 1
12 → 0,
∗
25
2 0
∗
1
9
20.05.2016
0
1
2
3
4
5
6
7
8
9
10
11
12
1
3
5
7
9
11
13
15
17
19
21
23
25
∗
8
0 →
1
© Květuše Sýkorová
12 → 0,
12 →
0
3,
12 →
3
∗ ∗
25
8
1 ∙ 12 25 1
0
8
7 ∙ 12 25 7
3
3,5 → 3,5 →
7
∗
→
∗
• vstupní soubor – nesetříděný • nalezený záznam fyzicky zrušit (přepsat) – okamžitý posun všech následujících záznamů » ČASOVĚ NÁROČNÉ: 1
• nalezený záznam nahradit jiným záznamem (poslední v souboru)
© Květuše Sýkorová
– záznamy musí mít pevnou délku 1 »
– setříděný • nalezený záznam logicky zrušit (označit ke smazání) – označit neexistující hodnotou klíče / přidat mazací bit 1 » – evidence % zrušených záznamů (fronta) » občas nutné spustit „setřásající“ algoritmus:
10
20.05.2016
• vstupní soubor – nesetříděný • vložíme záznam na konec souboru – záznamy mohou mít různou délku 1 » » Delete: záznamy musí mít pevnou délku
– setříděný © Květuše Sýkorová
• vložíme záznam na konec souboru + Sort – Sort: nutné po každém vložení záznamu, celý vstupní soubor 1 1 » ČASOVĚ NÁROČNÉ: »
∙
1
• vstupní soubor – setříděný • vložíme záznam na pozice záznamů určených pro smazání – záznamy musí mít pevnou délku 1 » – nutná evidence zrušených záznamů (fronta) » nutné občas spustit „setřásající“ algoritmus, tj.
© Květuše Sýkorová
– Search: nutné prohledávat i frontu rušených záznamů (Brute Force)
• vložíme záznam na pozice mimo soubor do „oblasti přetečení“ – udržuje se sekvenčně (Brute Force) – záznamy mohou mít různou délku 1 » » nutné občas spustit přirozený třídící algoritmus, tj. – Search: nutné prohledávat i „oblast přetečení“ (Brute Force)
11
20.05.2016
• pozitiva – jednoduchá realizace • pouze jeden cyklus
• negativa
© Květuše Sýkorová
– nejpomalejší
• 1 • •
1 1
• pozitiva – nejčastější
• negativa – setříděná data
• 1
log
© Květuše Sýkorová
•
1
• •
1
• –
1
–
1
T(n)
10
1↔10
102
1↔100
103
1↔1 000
104
1↔10 000
105
1↔100 000
106 1↔1 000 000
1
–
n
n
T(n)
10
1↔4
102
1↔7
103
1↔10
104
1↔14
105
1↔17
106
1↔20
12
20.05.2016
• pozitiva – méně časté
• negativa – setříděná data, unikátní klíče
• 1
log log
© Květuše Sýkorová
•
1
• •
1
• –
1
–
1
• pozitiva – nejrychlejší
• negativa – setříděná data, unikátní klíče
• 1
log log log
© Květuše Sýkorová
•
1
• •
1
• –
1
–
1
n
T(n)
10
1↔2
102
1↔3
103
1↔4
104
1↔4
105
1↔5
106
1↔5
n
T(n)
10
1↔1
102
1↔2
103
1↔2
104
1↔2
105
1↔3
106
1↔3
Lepší už to nebude !
13
