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
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       17 231×

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 Konference: Moderní informační systémy podporují automatizaci

Konference: Moderní informační systémy podporují automatizaci

Současná situace v šíření onemocnění Covid-19 klade na řadu firem nové nároky a mnohé z nich jsou nyní více než kdy jindy závislé na nejmodernějších informačních technologiích. Proto i v oblasti podnikových informačních systémů vidíme rostoucí důraz na automatizaci nebo na důslednou integraci. Také o těchto trendech se bude mluvit na konferenci Firemní informační systémy, která se koná 24.9.2020 v pražském Kongresovém centru Vavruška na Karlově náměstí.

Reklama
Reklama
Obrázek ke článku Nebezpečí ukrytá v USB: z nuly na škvarek za pět sekund

Nebezpečí ukrytá v USB: z nuly na škvarek za pět sekund

Za cenu šesti dolarů lze celkem bez obtíží koupit nový, líbivě vyhlížející flash disk. Přidaná hodnota, které se vám spolu s ním dostane, už tak moc líbivá není. To, co se před pár sekundami tvářilo jako externí disk, se po připojení k počítači změní v důmyslné elektrické křeslo, které vaše zařízení v onen příslovečný škvarek promění za pár sekund. Cílovou skupinou pro koupi takových zařízení by mohli být záškodníci, kteří by tímto způsobem osnovali pomstu třeba vůči záletnému partnerovi. 

Obrázek ke článku Znalosti, dovednosti i prestižní titul MBA: Jde to i moderně a online

Znalosti, dovednosti i prestižní titul MBA: Jde to i moderně a online

Snad nikdy není špatná příležitost na investici do hodnotného vzdělání. Obzvlášť v případě, že absolvent dovede teoretické poznatky přetavit v praktické dovednosti, využitelné při řešení problémů i v komunikaci. Právě na to se specializuje studijní program MBA Řízení informačních technologií, vyučovaný na Business Institutu.

Obrázek ke článku Coding Bootcamp Praha: Obor IT krize nepoznamenala, žádaní jsou weboví vývojáři

Coding Bootcamp Praha: Obor IT krize nepoznamenala, žádaní jsou weboví vývojáři

Pandemie Covid-19 otřásla trhem práce v základech. Dopady krize pocítilo celkově až 45 % zaměstnanců. Není divu, že čím dál větší jistotu přináší obor IT. Ten zůstal krizí téměř nepoznamenán a při nutnosti začít dělat věci na dálku se ještě více ukázalo, jak moc mnohé firmy kvalitní IT potřebují. Do IT nyní přicházejí začátečníci, kteří v něm vidí lukrativní budoucnost a jistotu, ale i freelanceři a zaměstnanci z oborů zasažených krizí

Reklama autora

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