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 305×

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

Obrázek ke článku Delphi 10.1.2 (Berlin Update 2) – na co se můžeme těšit

Delphi 10.1.2 (Berlin Update 2) – na co se můžeme těšit

Touto roční dobou, kdy je zem pokrytá barevným listím a prsty křehnou v mrazivých ránech, se obvykle těšíme na zbrusu novou verzi RAD Studia. Letos si však ale budeme muset počkat na Godzillu a Linux až do jara. Vezměme tedy za vděk alespoň updatem 2 a jelikož dle vyjádření pánů z Embarcadero se budou nové věci objevovat průběžně, pojďme se na to tedy podívat.

Reklama
Reklama
Obrázek ke článku Konference: Moderní datová centra pro byznys dneška se koná už 24. 11.

Konference: Moderní datová centra pro byznys dneška se koná už 24. 11.

Stále rostoucí zájem o cloudové služby i maximální důraz na pružnost, spolehlivost a bezpečnost IT vedou k výrazným inovacím v datových centrech. V infrastruktuře datových center hraje stále významnější roli software a stále častěji se lze setkat s hybridními přístupy k jejich budování i provozu.

Obrázek ke článku Konference: Mobilní technologie mají velký potenciál pro byznys

Konference: Mobilní technologie mají velký potenciál pro byznys

Firmy by se podle analytiků společnosti Gartner měly  rychle přizpůsobit skutečnosti, že mobilní technologie už zdaleka nejsou horkou novinkou, ale standardní součástí byznysu. I přesto - nebo možná právě proto - tu nabízejí velký potenciál. Kde tedy jsou ty největší příležitosti? I tomu se bude věnovat již čtvrtý ročník úspěšné konference Mobilní řešení pro business.

Obrázek ke článku Hackerský kongres přiveze v září do Prahy špičky světové kryptoanarchie

Hackerský kongres přiveze v září do Prahy špičky světové kryptoanarchie

Hackerský kongres HCPP16 pořádá od 30. září do 2. října nezisková organizace Paralelní Polis již potřetí, a to ve stejnojmenném bitcoinovém prostoru v pražských Holešovicích. Letos přiveze na třídenní konferenci přes 40 většinou zahraničních speakerů – lídrů z oblastí technologií, decentralizované ekonomiky, politických umění a aktivismu. Náměty jejich přednášek budou také hacking, kryptoměny, věda, svoboda nebo kryptoanarchie.

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