Vyhledávání I. - sekvenční vyhledávání

1. Sekvenční vyhledávání
1.1.1. Sekvenční vyhledávání v seznamu
1.1.2. Sekvenční vyhledávání v poli
1.1.3. Rychlé sekvenční vyhledávání v poli
1.1.4. Dynamické vlastnosti sekvenčního vyhledávání v poli
1.1.5. Sekvenční vyhledávání v seřazeném seznamu
1.1.6. Sekvenční vyhledávání v seřazeném poli
1.1.7. Sekvenční vyhledávání v seřazeném poli se zarážkou
1.1.8. Dynamické vlastnosti sekvenčního vyhledávání v seřazeném poli

Metody vyhledávání můžeme klasifikovat podle různých hledisek. Metody interního vyhledávání pracují s daty uloženými ve vnitřní paměti počítače, zatím co metody externího vyhledávání pracují s daty na vnějších pamětech počítače. Statické metody vyhledávání pracují nad datovou strukturou, která se v průběhu zpracování nemění, zatímco dynamické vyhledávání předpokládá, že v datové struktuře mohou v průběh zpracování vznikat nové a zanikat nepotřebné položky. Jiné dělení může přihlížet k tomu, zda se pracuje s původními klíči nebo s transformovanými klíči (které vedou k tabulkám s rozptýlenými položkami) – a jsou známa i jiná hlediska.

Algoritmy pro vyhledávání úzce souvisí s algoritmy pro řazení a jejich volba může záviset na řadě okolností. Prvotním účelem řazení je urychlení vyhledávání.

Metody vyhledávání si rozdělíme do čtyř skupin:
	1. Sekvenční vyhledávání
	2. Nesekvenční vyhledávání v seřazeném poli
	3. Vyhledávání v uspořádaných binárních stromech
	4. Vyhledávání v tabulce s rozptýlenými položkami

1. Sekvenční vyhledávání

Principy sekvenčního vyhledávání lze ilustrovat na sekvenčním vyhledávání v tabulce implementované seznamem s použitím základních operací ATD seznam.

1.1.1. Sekvenční vyhledávání v seznamu

Je-li seznam neprázdný, bude mít algoritmus tuto podobu:


FIRST(LIST);
while ACTIVE(LIST) and (COPY(LIST) <> KEY) do SUCC(LIST);
SEARCH := ACTIVE(LIST);
{ if SEARCH then aktivní prvek je hledaným prvkem }

Může-li být seznam také prázdný, musíme zabránit chybovému stavu operace COPY nad prázdným seznamem. Algoritmus bude mít tento tvar:


FIRST(LIST);
SEARCH := false;
while ACTIVE(LIST) and not SEARCH do
	begin SEARCH := COPY(LIST) = KEY;
		if not SEARCH then SUCC(LIST)
	end;
{ if SEARCH then aktivní prvek je hledaným prvkem }

Není-li zapotřebí přístup k nalezenému prvku, nemusí být operace SUCC(LIST) podmíněná.

Nejrychleji budou vyhledány ty položky, které jsou zařazeny na začátek seznamu. Je-li známa pravděpodobnost vyhledávání jednotlivých položek, je účelné, aby byly položky seznamu seřazeny sestupně podle pravděpodobnosti svého vyhledání. Na této myšlence jsou založeny složitější „sebeorganizující“ algoritmy, které na základě informace o četnosti vyhledávání jednotlivých položek získaných v průběhu chodu programu, reorganizují uspořádání seznamu tak, že často vyhledávané položky umísťují do čela seznamu v naději, že tyto položky budou i v budoucnu vyhledávány často a že úspora času bude větší než čas potřebný na reorganizaci seznamu.

1.1.2. Sekvenční vyhledávání v pol

Nechť jsou dány datové typy:


	TYPPOLOZKY = record
				DATA:TYPDATA;
				KLIC:TYPKLIC;
			  end;

Kde nad typem TYPKLIC je definována relace ekvivalence, a dále


	TYPPOLE = ARRAY[1..MAX] of TYPPOLOZKY;

Nechť POLE:TYPPOLE je použito pro implementaci ATD tabulka a K:TYPKLIC má hodnotu vyhledávaného klíče; pak sekvenční vyhledávání v poli realizuje tento algoritmus:


	i := 0;
repeat
	i := succ(i)
until (i = n) or (POLE[i].KLIC = K);	{ POLE[n] je poslední aktivní prvek }
SEARCH := POLE[i].KLIC = K;
{ if SEARCH then prvek POLE[i[ je hledaným prvkem }

1.1.3. Rychlé sekvenční vyhledávání v poli

Jednoduchou úpravou lze tento algoritmus zrychlit. Zrychlení spočívá ve snížení hodnoty konstanty c vyjadřující délku cyklu tím, že se zjednoduší podmínka na konec cyklu. Předpokládáme, že tabulka obsahuje maximálně MAX-1 položek. Pak lze za poslední aktivní prvek vložit před zahájením cyklu „zarážku“, což je položka s hodnotou vyhledávaného klíče. Test na konec cyklu již nemusí „hlídat“ konec pole. Cyklus skončí vždy „úspěšným vyhledáním“, ke kterému dojde buď na zarážce (tzn. ve skutečnosti neúspěšné vyhledání) nebo dříve (což znamená úspěšné vyhledání). Algoritmus má tvar:


	POLE[n+1].KLIC := K;	{ vložení zarážky }
	i := 1;
	while POLE[i].KLIC <> K do i := succ(i);
SEARCH := i <> (n+1);
	{ if SEARCH then prvek POLE[i] je hledaným prvkem }

1.1.4. Dynamické vlastnosti sekvenčního vyhledávání v poli

Jestliže vyhradíme dostatečně velké pole, pak konec cyklu vyhledávání i pozice zarážky je určena posledním aktivním prvkem v poli. Při vložení nové položky do tabulky (operace INSERT) se tato pozice zvýší o jedničku a na novou poslední pozici se vloží nový prvek.
Poněkud složitější je (u všech implementací) rušení položky v tabulce (operace DELETE). V zásadě lze volit mezi dvěma přístupy:
a) Ruší-li se i-tý prvek, posune část pole od i+1 prvku až do posledního aktivního prvku o jednu pozici doleva.
b) Klíč rušeného prvku se nastaví na hodnotu, o které je jisto, že nikdy nebude vyhledávána.

Nevýhodou prvního přístupu je potencionálně významná časová náročnost posuvu. Nevýhodou druhého přístupu je, že vyřazení způsobí zmenšení použitelného prostoru tabulky „zaslepením“ místa rušených prvků. Tuto nevýhodu lze kompenzovat tím, že při vyčerpání celého pole se nové volné místo vyhledává mezi „zaslepenými“ položkami. Nevýhodou však zůstává skutečnost, že se zbytečně prohledávají i „zaslepené“ položky, což prodlužuje vyhledávání.

1.1.5. Sekvenční vyhledávání v seřazeném seznamu

Je-li nad typem TYPKLIC definována relace uspořádání, lze seznam seřadit (např. vzestupně) podle velikosti klíče. Sekvenční vyhledávání v seřazeném seznamu se pak zrychlí v případě neúspěšného vyhledávání, protože cyklus prohledávání lze ukončit v okamžiku, kdy klíč testované položky je větší než vyhledáváný klíč. Princip algoritmu této metody je ilustrován s použitím základních operací nad ATD seznam.


FIRST(LIST);
while ACTIVE(LIST) nad (COPY(LIST) < K) do SUCC(LIST);
SEARCH := COPY(LIST) = K;	{ Algoritmus  předpokládá neprázdný seznam }
{ if SEARCH then aktivní prvek je hledaným prvkem }

1.1.6. Sekvenční vyhledávání v seřazeném poli

Z předcházejicího algoritmu lze snadno odvodit jeho variantu pracující se seřazeným polem:


i := 0;
repeat
	i := succ(i);
until (i = n) or ({POLE[i].KLIC >= K);
SEARCH := POLE[i].KLIC = K;
{ if SEARCH then prvek POLE[i] je hledaným prvkem }

1.1.7. Sekvenční vyhledávání v seřazeném poli se zarážkou

Sekvenční vyhledávání v seřazeném poli lze urychlit s použitím zarážky, která odstraní nutnost testu na konec pole. Hodnota zarážky musí být větší, než hodnoty všech možných vyhledávaných klíčů K. Algoritmus má tvar:


i := 0;
POLE[n+1].KLIC := MAXKLIC;	{ MAXKLIC je větší než hodnoty všech vyhledávaných klíčů }
repeat
	i := succ(i);
until POLE[i].KLIC >= K;
SEARCH := POLE[i].KLIC = K;
{ if SEARCH then prvek POLE[i[ je hledaným prvkem }

1.1.8. Dynamické vlastnosti sekvenčního vyhledávání v seřazeném poli

Na rozdíl od neseřazeného pole, je s použitím seřazeného pole nutné při vkládání nového prvku (operace INSERT) zachovat uspořádanost pole. Prvek je nutno zařadit do seřazeného pole, s čímž je obecně spojen posun části pole od i-té polozice do pozice posledního aktivního prvku o jednu pozici doprava. Jestliže operace INSERT následuje po operaci SEARCH, končí předcházející algoritmy nalezením místa (indexu i), na který se po posunu části pole vloží nový prvek. Operace DELETE se bude provádět posunem části pole o jednu pozici doleva. Metoda “zaslepování” položek je principiálně možná, použije-li se klíč, který je menší než všechny možné vyhledávané klíče. Regenerace zaslepených míst však není jednoduchá.

Zdroj: Petr Pindur - vyhledávání

Vyhledávání I. - sekvenční vyhledávání

Programátoři po celém světě dnes slaví Den programátorů
Celá zprávička