TIP: Přetáhni ikonu na hlavní panel pro připnutí webu
V první lekci si ukážeme způsoby vyhledávání v polích, uděláme si rozbor binárního a sekvenčního vyhledávání a napíšeme aplikaci pro testování rychlostí obou algoritmů...
Minule jsme si na úvod popsali, co je to algoritmus. Můžeme ho také nazvat "obecnou metodou k dosažení nějakého výpočtu (výsledku)". Hned si uvedeme jednoduchý příklad:
Máme pole textových řetězců (např. jména) a chceme vyhledat konkrétně jeden z nich (třeba Jan Novák). Postup není složitý a pravděpodobně by napadl většinu z vás i bez znalosti programování. Stačí procházet jeden řetězec po druhém a porovnávat ho s hledaným řetězcem Jan Novák, dokud nedorazíme k tomu správnému. Ačkoliv se to třeba zdá až příliš jednoduché, jedná se o algoritmus známý jako tzv. sekvenční vyhledávání.
Existuje však i jiný způsob, jak najít Jana Nováka v našem pomyslném poli řetězců. Jestliže například víme, že se jedná o pole řazené podle příjmení, můžeme použít tzv. binární vyhledávání: nejdříve porovnáme přesně prostřední jméno v poli s Janem Novákem. Pokud je to Jan Novák, máme hotovo. Pokud ne (což je pravděpodobnější), začneme porovnávat příjmení podle abecedy. Takže, pokud je prostřední prvek pole abecedně před Novákem, dá se z toho usoudit, že Novák je ve druhé polovině pole (samozřejmě, pokud je prostřední prvek za Novákem, patří Novák do poloviny první). Nyní můžeme udělat v podstatě to samé. Podíváme se na prostřední prvek vybrané části pole (první či druhá polovina) a opět porovnáváme s Novákem. Poté opět rozdělíme na půl, porovnáme prostřední prvek, ... a takto bychom pokračovali, dokud bychom Nováka nenašli.
Tento postup je určitě o něco kopmlikovanější než původní sekvenční vyhledávání, které může být zapsáno jednoduchým kódem pomocí for cyklu. Kód pro binární vyhledávání vyžaduje o něco více výpočtů a lokálních proměnných.
Pro lepší představu uvedu zdrojové kódy obou metod vyhledávání:
// sekvenční vyhledávání
function SeqSearch(Strings: Array of String; PocetPrvku: Integer; Hodnota: String): Integer;
{ Strings - pole stringů (textových řetězců) ve kterém se bude vyhledávat,
PocetCisel - počet prvků v poli,
Hodnota - hledaná hodnota }
var i: Integer;
begin
for i := 0 to pred(Count) do // opakovat tolikrát, kolik je prvků v poli
if CompareText(Strings[i], Value) = 0 then // pokud se řetězec rovná hledanému...
begin
SeqSearch := i; // ...hotovo
Exit;
end;
SeqSearch := -1; // pokud nebyl prvek nalezen, vrátí funkce hodnotu -1
end;
// binární vyhledávání
function BinSearch(Strings: Array of String; PocetPrvku: Integer; Hodnota: String): Integer;
{ Strings - pole stringů (textových řetězců) ve kterém se bude vyhledávat,
PocetCisel - počet prvků v poli,
Hodnota - hledaná hodnota }
var L, R, M: Integer;
Porovnani: Integer;
begin
L := 0;
R := Pred(Count);
while (L <= R) do // opakovat, dokud se půlením nedostaneme až k jedinému číslu
begin
M := (L + R) div 2;
CompareResult := CompareText(Strings[M], Value);
if (CompareResult = 0) then
begin
BinSearch := M;
Exit;
end
else if (CompareResult < 0) then
L := M + 1
else
R := M - 1;
end;
BinSearch := -1;
end;
Vzhledem k již zmíněné větší komplikovanosti binárního vyhledávání by se mohlo zdát, že sekvenční vyhledávání je rychlejší. Je ale těžké udělat si úsudek o rychlosti pouhým pročtením zdrojového kódu. Proto si napíšeme aplikaci, která bude testovat rychlosti obou způsobů.
Je jasné, že pokud pustíme pouze jeden vyhledávací cyklus, bude výsledná doba nejen téměř neměřitelná, ale výsledek bude i silně neobjektivní. Proto je nutné spustit vyhledávání vícekrát za sebou a pokaždé s jinými hodnotami. Pro účely tohoto testovacího programu použijeme čísla místo jmen. Postup u jmen by byl stejný, ale dalo by zbytečnou práci ukládání velkého množství jmen do pole. Při použití čísel není problém uložit data do pole za pomocí jednoduchého for cyklu.
Takže, postup bude následující: nejdříve zaplníme pole čísel, poté pomocí funkce Random určíme hledané číslo a nakonec číslo vyhledáme (nejdříve sekvenčním, potom binárním vyhledáváním). Toto (bez nahrávání hodnot do pole) budeme opakovat alespoň 10 000 krát. Jak dlouho celá operace trvala zjistíme pomocí funkce GetTickCount, která udává, kolik milisekund uběhlo od spuštění systému. Stačí si udělat dvě proměnné. Do první se uloží GetTickCount před vyhledáváním a do druhé až po skončení. První hodnotu odečteme od druhé a máme výsledný čas.
Pro úplnost ještě uvedu zdrojový kód obou vyhledávacích metod, upravených pro vyhledávání čísel:
// sekvenční vyhledávání
function SekVyhledavani(Cisla: Array of Integer; PocetCisel, Hodnota: Integer; var PocetKroku: Integer): Integer;
{ Cisla - pole čísel ve kterém se bude vyhledávat,
PocetCisel - počet prvků v poli,
Hodnota - hledaná hodnota,
PocetKroku - počet podmínek if, který se musel vyhodnotit, aby byla hledaná hodnota nalezena }
var i: Integer;
begin
PocetKroku := 0;
for i := 0 to pred(PocetCisel) do // opakovat tolikrát, kolik je prvků v poli
begin
if Cisla[i] = Hodnota then // pokud se číslo rovná hledanému...
begin
SekVyhledavani := i; // ...hotovo
Exit;
end;
Inc(PocetKroku); // podmínka if - zvýšit počet kroků
end;
SekVyhledavani := -1; // pokud nebyl prvek nalezen, vrátí funkce hodnotu -1
end;
// binární vyhledávání
function BinVyhledavani(Cisla: Array of Integer; PocetCisel, Hodnota: Integer; var PocetKroku: Integer): Integer;
{ Cisla - pole čísel ve kterém se bude vyhledávat,
PocetCisel - počet prvků v poli,
Hodnota - hledaná hodnota,
PocetKroku - vrátí počet podmínek if, který se musel vyhodnotit, aby byla hledaná hodnota nalezena }
var L, R, M: Integer;
Porovnani: Integer;
begin
PocetKroku := 0;
L := 0;
R := Pred(PocetCisel);
while (L <= R) do // opakovat, dokud se půlením nedostaneme až k jedinému číslu
begin
M := (L + R) div 2; // půlení intervalu
Porovnani := Cisla[M] - Hodnota; // porovnání prostředního prvku s hledaným
if (Porovnani = 0) then // pokud se rovná...
begin
BinVyhledavani := M; // ...hotovo
Inc(PocetKroku); // porovnávání pomocí if - zvýšit počet kroků
Exit;
end
else
begin
if (Porovnani < 0) then // pokud je prostřední prvek menší než hledaný...
L := M + 1 // ...hledaný prvek je ve druhé polovině
else
R := M - 1; // ... hledaný prvek je v první polovině
Inc(PocetKroku); // podmínka if - zvýšit počet kroků
end;
end;
BinVyhledavani := -1; // pokud nebyl prvek nalezen, vrátí funkce hodnotu -1
end;
Jistě jste si všimli, že kromě úpravy pro vyhledávání čísel, obsahují obě funkce i další změnu. Je jí proměnná PocetKroku. V té funkce vrací počet podmínek if, které bylo nutno vyhodnotit k vyhledání čísla. O tom však více až příště.
Pro dnešek je to všechno, více se mi toho sem již nevejde. Příště vám ukážu zdrojový kód testu rychlosti a ještě si ho trochu rozebereme. Zejména se zaměříme na výsledné hodnoty z testu a podíváme se, jak je to s efektivností obou vyhledávacích algoritmů.
