Vyhledávání I. - sekvenční vyhledávání
 x   TIP: Přetáhni ikonu na hlavní panel pro připnutí webu
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       14 284×

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 Blockchain & Bitcoin konference

Blockchain & Bitcoin konference

V pátek 19. 5. 2017 se v pražském konferenčním centru Andel’s konala Blockchain & Bitcoin konference. Řada odborníků a podnikatelů v oboru blockchainu a kryptoměn představila možnosti budoucího směřování tohoto oboru. Speakeři většinou rusky mluvící provenience prezentovali řešení svých firem založená na technologii blockchainu.

Reklama
Reklama
Obrázek ke článku Malware KONNI se úspěšně skrýval 3 roky. Odhalil ho bezpečnostní tým Cisco Talos

Malware KONNI se úspěšně skrýval 3 roky. Odhalil ho bezpečnostní tým Cisco Talos

Bezpečnostní tým Cisco Talos odhalil celkem 4 kampaně dosud neobjeveného malwaru, který dostal jméno KONNI. Ten se dokázal úspěšně maskovat od roku 2014. Zpočátku se malware zaměřoval pouze na krádeže citlivých dat. Za 3 roky se ale několikrát vyvinul, přičemž jeho současná verze umožňuje útočníkovi z infikovaného počítače nejenom krást data, ale i mapovat stisky na klávesnici, pořizovat screenshoty obrazovky či v zařízení spustit libovolný kód. Pro odvedení pozornosti oběti zasílali útočníci v příloze také obrázek, zprávu a výhružkách severokorejského režimu či kontakty na členy mezinárodních organizací.

Obrázek ke článku Pouze jedna z deseti lokálních firem ví o pokutách plynoucích z GDPR

Pouze jedna z deseti lokálních firem ví o pokutách plynoucích z GDPR

Trend Micro, celosvětový lídr v oblasti bezpečnostních řešení a VMware, přední světový dodavatel cloudové infrastruktury a řešení pro podnikovou mobilitu, oznámily výsledky výzkumu mezi českými a slovenskými manažery zodpovědnými za ochranu osobních údajů, který zjišťoval, jak jsou připraveni na nové nařízení o ochraně osobních údajů (GDPR). Většina firem v České republice a na Slovensku nad 100 zaměstnanců je již s novým nařízením GDPR obeznámena. Výzkum provedený ve spolupráci s agenturou Ipsos ukázal, že téměř 8 firem z 10 o nařízení ví, přičemž jeho znalost je o něco vyšší na Slovensku (89 %) než v České republice (69 %).

Obrázek ke článku Vyděračský software Locky se vrací, tváří se jako potvrzení platby, odhalil tým Cisco Talos

Vyděračský software Locky se vrací, tváří se jako potvrzení platby, odhalil tým Cisco Talos

Jeden z nejznámějších ransomwarů, Locky, se vrací. Po většinu roku 2016 patřil mezi nejrozšířenější vyděračské softwary. Ke svému šíření využíval emailové kampaně s infikovanými přílohami. Ransomware Locky byl rozesílán prostřednictvím botnetu (internetový robot zasílající spamy) Necurs. Jeho aktivita na konci roku 2016 téměř upadla a spolu s ní i šíření ransomwaru Locky. Před několika týdny se Necurs opět probudil a začal posílat spamy nabízející výhodný nákup akcií. Dne 21. dubna zaznamenal bezpečnostní tým Cisco Talos první velkou kampaň ransomwaru Locky prostřednictvím botnetu Necurs za posledních několik měsíců.

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 © 20032017 Programujte.com
Zasadilo a pěstuje Webtea.cz, šéfredaktor Lukáš Churý