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

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

 
Hledat
Moderní platforma pro vytvoření vašeho nového webu – Wix.com.
Nyní už můžete mít web zdarma.
Vybavení pro Laser Game
Spuštěn Filmový magazín
Laser Game Brno
Laser Game Ostrava

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

Google       Google       30. 1. 2006       16 398×

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 Otevřené bankovnictví usnadní život nejen jednotlivcům, ale i firmám.

Otevřené bankovnictví usnadní život nejen jednotlivcům, ale i firmám.

Většina lidí by ráda obsluhovala své bankovní účty z jednoho místa. Díky evropské směrnici o platebních službách PSD2 by se brzy mohlo jednat o realitu. Některé tuzemské banky již služby takzvaného otevřeného bankovnictví umožňují, nejpozději od září by měly svá API rozhraní zpřístupnit vývojářům třetích stran. To otevírá prostor pro fintech firmy a start-upy, ale třeba i vývojáře ERP a fakturačních systémů, kteří by díky propojení svých produktů s bankami významně ulehčili klientům při správě financí.

Reklama
Reklama
Obrázek ke článku Velké srovnání TOP e-shopových řešení!

Velké srovnání TOP e-shopových řešení!

Předmět případové studie je ​středně velký e-shop​ s počtem produktů do 5 000, který chce expandovat na slovenský trh a potřebuje ​druhou jazykovou mutaci v eurech ​na vlastní doméně.

Výběr vhodného systému závisí na mnoha aspektech a měl by být pečlivě zvážen na základě potřeb a konkrétních požadavků plánovaného nebo migrovaného e-shopu.

Obrázek ke článku Master Data Management a jak nám pomůže

Master Data Management a jak nám pomůže

Master Data (česky také kmenová data) jsou data sdílená napříč různými systémy, nemění se příliš často a netransakční. Jedná se o informace o obchodních partnerech, produktech, vlastních pracovnících. Objednávky, faktury, účetní zápisy do této oblasti nespadají.

Obrázek ke článku Startup DoDo zajistí městskou logistiku pro RunCzech

Startup DoDo zajistí městskou logistiku pro RunCzech

Startup DoDo se stává důležitým partnerem RunCzecha na významných běžeckých závodech včetně 25. ročníku Volkswagen Maratonu Praha se bude starat o logistické zázemí. Lídr v oblasti městské logistiky bude mimo jiné zásobovat občerstvovací stanice a pomůže rovněž se zajištěním televizních přenosů ze závodů.

Reklama autora

Hostujeme u Českého hostingu       ISSN 1801-1586       ⇡ Nahoru Webtea.cz logo © 20032019 Programujte.com
Zasadilo a pěstuje Webtea.cz, šéfredaktor Lukáš Churý