Algoritmizace v Delphi - 1. díl
 x   TIP: Přetáhni ikonu na hlavní panel pro připnutí webu
Reklama
Reklama

Algoritmizace v Delphi - 1. dílAlgoritmizace v Delphi - 1. díl

 

Algoritmizace v Delphi - 1. díl

Google       Google       30. 11. 2005       11 563×

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ů...

Reklama
Reklama

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ů.

×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
Autor programuje v C++ a Delphi, zajímá se o muziku a sport.

Nové články

Reklama
Reklama
Obrázek ke článku Nový IT hráč na českém trhu

Nový IT hráč na českém trhu

V roce 2015 otevřela v Praze na Pankráci v budově City Tower své kanceláře společnost EPAM Systems (NYSE:EPAM), jejíž centrála se nachází v USA. Společnost byla založená v roce 1993 a od té doby prošla velkým vývojem a stále roste.

Obrázek ke článku České Radiokomunikace opět hledají nejlepší nápady pro internet věcí

České Radiokomunikace opět hledají nejlepší nápady pro internet věcí

České Radiokomunikace (CRA) pořádají druhý ročník CRA IoT Hackathonů. Zájemci z řad vývojářů a fanoušků moderních technologií mohou změřit své síly a během jediného dne sestrojit co nejzajímavější funkční prototyp zařízení, které bude komunikovat prostřednictvím sítě LoRa. CRA IoT Hackathony se letos uskuteční ve dvou fázích, na jaře a na podzim, v různých městech České republiky. Jarní běh se odstartuje 31. března v Brně a 7. dubna v Praze.

Obrázek ke článku Cloud computing je využíván stále intenzivněji

Cloud computing je využíván stále intenzivněji

Využívání cloud computingu nabývá na intenzitě. Jen v letošním roce vzroste podle analytiků trh se službami veřejného cloudu o 18 %, přičemž o téměř 37 % vzrostou služby typu IaaS. Růst o více než pětinu pak čeká služby poskytování softwaru formou služby, tedy SaaS. Aktuálním trendům v oblasti využívání cloudu se bude věnovat konference Cloud computing v praxi, která se koná 23. března. 2017 v pražském Kongresovém centru Vavruška na Karlově náměstí 5.

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ý