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

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

 

Algoritmizace v Delphi - 2. díl

Google       Google       14. 12. 2005       16 374×

V dnešním díle si ukážeme program pro testování vyhledávacích algoritmů. Zjistíme, který je rychlejší a proč...

Vminulém díle jsme skončili ukázkou zdrojových kódů pro sekvenční a binární vyhledávání. Vzhledem k 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í hodněkrát za sebou (pomocí for cyklu) 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 pomoci jednoduchého for cyklu.

Jak přibližně budeme při psaní testovacího programu postupovat, jsem uvedl již minule, ale pro jistotu zopakuji:
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.

Takže zdrojový kód:

// test rychlosti
function TestRychlosti(ZpusobHledani: Byte; PocetPrvku, PocetOpakovani: Integer; var PrumerneKroky: Real): Cardinal;
{ ZpusobHledani - typ algoritmu, který se pro vyhledávání použije (sekvenční nebo binární),
  PocetPrvku - kolik prvků má mít pole, ze kterého se bude testovat rychlost vyhledávání,
  PocetOpakovani - kolikrát se má celý proces vyhledávání opakovat (pro větší objektivitu výsledku),
  PrumerneKroky - vrátí průměrný počet podmínek if, který se musel vyhodnotit k vyhledání prvku }
var PrvniCas: Cardinal;
    i: Word;
    PoleCisel: Array of Integer;
    Hodnota : Word;
    PocetKroku: Integer;
begin
PrumerneKroky := 0;
Randomize;      // initializace generátoru náhodných čísel
SetLength(PoleCisel, PocetPrvku);	// nastavení velikosti dynamického pole na zadaný počet prvků
for i := 1 to PocetPrvku do PoleCisel[i] := i;
PrvniCas := GetTickCount;     // uložení času před zpuštěním testu
for i := 1 to PocetOpakovani do     // proces určování a vyhledávání náhodného čísla se bude opakovat ...
  begin
  Hodnota := Random(PocetPrvku) + 1;      // určení náhodného čísla pro vyhledávání
  if ZpusobHledani = 0 then SekVyhledavani(PoleCisel, PocetPrvku, Hodnota, PocetKroku) else
    BinVyhledavani(PoleCisel, PocetPrvku, Hodnota, PocetKroku);
  PrumerneKroky := PrumerneKroky + PocetKroku;
  end;
TestRychlosti := GetTickCount - PrvniCas;     // vypočítání celkového času
PrumerneKroky := PrumerneKroky / PocetOpakovani;    // vypočítání celkového počtu kroků (příkazů if) nutného k vyhledání čísla
Finalize(PoleCisel);	// dealokace dynamického pole z paměti
end;

Já jsem při opakování 20 000 naměřil tyto hodnoty:

Sekvenční vyhledávání:

Počet prvků v poli
Průměrná doba vyhledávání
Průměrný počet kroků 
 512  0.03  257.9
1024
0.06
513.0
5000
0.27
2513.1
10000
0.56
5026.0
50000
2.94
25068


Binární vyhledávání:

Počet prvků v poli
Průměrná doba vyhledávání
Průměrný počet kroků 
 512  0.02  8.0
1024
0.03
9.0
5000
0.16
11.3
10000
0.31
12.4
50000
1.53
14.7




Z uvedeného vyplývá, že binární vyhledávání je rozhodně rychlejší. Rozdíl je patrný zejména u větších polí.

Proč tomu tak je, napovídají hodnoty Počet kroků, což jsou čísla, která vracejí obě funkce pro vyhledávání a udávají, kolik příkazů if bylo nutno vyhodnotit k dosažení výsledku. Z naměřených hodnot je jasně vidět, že binární vyhledávání v průměru potřebuje mnohonásobně méně if příkazů. Jistě, mohlo by se říci, že funkce binárního vyhledávání využívá jiné příkazy, které taktéž zatěžují procesor. Mně šlo ale pouze o názornost. Aby bylo jasné, proč je binární vyhledávání rychlejší - protože zatímco sekvenční prohledává vždy prvek po prvku, binární se k hledané hodnotě dostane půlením intervalu a najde tak prvek v mnohem méně krocích.

Všimněte si také, že u sekvenčního vyhledávání se doba zvyšuje přímo úměrně k počtu prvků a počet kroků se vždy pohybuje kolem poloviny počtu prvků. Kdežto u binárního roste doba vyhledávání jen zvolna a lze říci, že počet kroků, pokud si uvědomíme obrovský rozdíl mezi čísly 512 a 50000, se téměř nemění.

Pokud si chcete stáhnout hotový test rychlosti i se zdrojáky, můžete zde.

Pro tentokrát je to vše. Příště se sice stále budeme věnovat polím, ale tentokrát již jiným algoritmům, které budete pro práci s nimi potřebovat.

×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 Stavebnice umělé inteligence 1

Stavebnice umělé inteligence 1

Článek popisuje první část stavebnice umělé inteligence. Obsahuje lineární a plošnou optimalizaci.  Demo verzi je možné použít pro výuku i zájmovou činnost. Profesionální verze je určena pro vývojáře, kteří chtějí integrovat popsané moduly do svých systémů.

Obrázek ke článku Hybridní inteligentní systémy 2

Hybridní inteligentní systémy 2

V technické praxi využíváme často kombinaci různých disciplín umělé inteligence a klasických výpočtů. Takovým systémům říkáme hybridní systémy. V tomto článku se zmíním o určitém typu hybridního systému, který je užitečný ve velmi složitých výrobních procesech.

Obrázek ke článku Jak vést kvalitně tým v IT oboru: Naprogramujte si ty správné manažerské kvality

Jak vést kvalitně tým v IT oboru: Naprogramujte si ty správné manažerské kvality

Vedení týmu v oboru informačních technologií se nijak zvlášť neliší od jiných oborů. Přesto však IT manažeři čelí výzvě v podobě velmi rychlého rozvoje a tím i rostoucími nároky na své lidi. Udržet pozornost, motivaci a efektivitu týmu vyžaduje opravdu pevné manažerské základy a zároveň otevřenost a flexibilitu pro stále nové výzvy.

Obrázek ke článku Síla týmů se na home office může vytrácet. Odborníci radí, jak z pracovních omezení vytěžit maximum

Síla týmů se na home office může vytrácet. Odborníci radí, jak z pracovních omezení vytěžit maximum

Za poslední rok se podoba práce zaměstnanců změnila k nepoznání. Především plošné zavedení home office, které mělo být zpočátku jen dočasným opatřením, je pro mnohé už více než rok každodenní realitou. Co ale dělat, když se při práci z domova ztrácí motivace, zaměstnanci přestávají komunikovat a dříve fungující tým se rozpadá na skupinu solitérů? Odborníci na personalistiku dali dohromady několik rad, jak udržet tým v chodu, i když pracovní podmínky nejsou ideální.

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