Vyhledávání I. - sekvenční vyhledávání
 x   TIP: Přetáhni ikonu na hlavní panel pro připnutí webu
Reklama
Reklama

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

 

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

Google       Google       30. 1. 2006       13 731×

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

Reklama
Reklama

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í

×Odeslání článku na tvůj Kindle

Zadej svůj Kindle e-mail a my ti pošleme článek na tvůj Kindle.
Musíš mít povolený příjem obsahu do svého Kindle z naší e-mailové adresy kindle@programujte.com.

E-mailová adresa (např. novak@kindle.com):

TIP: Pokud chceš dostávat naše články každé ráno do svého Kindle, koukni do sekce Články do Kindle.

Hlasování bylo ukončeno    
0 hlasů
Google
(fotka) Lukáš ChurýLukáš je šéfredaktorem Programujte, vyvíjí webové aplikace, fascinuje ho umělá inteligence a je lektorem na FI MUNI, kde učí navrhovat studenty GUI. Poslední dobou se snaží posunout Laser Game o stupeň výše a vyvíjí pro něj nové herní aplikace a elektroniku.
Web     Twitter     Facebook     LinkedIn    

Nové články

Obrázek ke článku NEWTON Media prohledá 200  milionů mediálních zpráv během sekund díky Cisco UCS

NEWTON Media prohledá 200 milionů mediálních zpráv během sekund díky Cisco UCS

Česká společnost NEWTON Media provozuje největší archiv mediálních zpráv ve střední a východní Evropě. Mezi její zákazníky patří například ministerstva, evropské instituce nebo komerční firmy z nejrůznějších oborů. NEWTON Media rozesílá svým zákazníkům každý den monitoring médií podle nastavených klíčových slov a nabízí online službu, kde lze vyhledat mediální výstupy v plném znění od roku 1996.

Reklama
Reklama
Obrázek ke článku Delphi 10.1.2 (Berlin Update 2) – na co se můžeme těšit

Delphi 10.1.2 (Berlin Update 2) – na co se můžeme těšit

Touto roční dobou, kdy je zem pokrytá barevným listím a prsty křehnou v mrazivých ránech, se obvykle těšíme na zbrusu novou verzi RAD Studia. Letos si však ale budeme muset počkat na Godzillu a Linux až do jara. Vezměme tedy za vděk alespoň updatem 2 a jelikož dle vyjádření pánů z Embarcadero se budou nové věci objevovat průběžně, pojďme se na to tedy podívat.

Obrázek ke článku Konference: Moderní datová centra pro byznys dneška se koná už 24. 11.

Konference: Moderní datová centra pro byznys dneška se koná už 24. 11.

Stále rostoucí zájem o cloudové služby i maximální důraz na pružnost, spolehlivost a bezpečnost IT vedou k výrazným inovacím v datových centrech. V infrastruktuře datových center hraje stále významnější roli software a stále častěji se lze setkat s hybridními přístupy k jejich budování i provozu.

Obrázek ke článku Konference: Mobilní technologie mají velký potenciál pro byznys

Konference: Mobilní technologie mají velký potenciál pro byznys

Firmy by se podle analytiků společnosti Gartner měly  rychle přizpůsobit skutečnosti, že mobilní technologie už zdaleka nejsou horkou novinkou, ale standardní součástí byznysu. I přesto - nebo možná právě proto - tu nabízejí velký potenciál. Kde tedy jsou ty největší příležitosti? I tomu se bude věnovat již čtvrtý ročník úspěšné konference Mobilní řešení pro business.

Reklama autora

loadingtransparent (function() { var po = document.createElement('script'); po.type = 'text/javascript'; po.async = true; po.src = 'https://apis.google.com/js/plusone.js'; var s = document.getElementsByTagName('script')[0]; s.parentNode.insertBefore(po, s); })();
Hostujeme u Českého hostingu       ISSN 1801-1586       ⇡ Nahoru Webtea.cz logo © 20032016 Programujte.com
Zasadilo a pěstuje Webtea.cz, šéfredaktor Lukáš Churý