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

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

 

Algoritmizace v Delphi - 2. díl

Google       Google       14. 12. 2005       13 732×

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

Reklama
Reklama
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

Reklama
Reklama
Obrázek ke článku Bezrealitky.cz na novém webu rychleji propojí vážné zájemce s majiteli nemovitostí

Bezrealitky.cz na novém webu rychleji propojí vážné zájemce s majiteli nemovitostí

Největší platforma pro přímý prodej a pronájem domů a bytů Bezrealitky.cz představila novou podobu svého portálu. Redesign zásadně zjednodušuje všechny transakce, mění způsob, jakým zájemci o bydlení komunikují s majiteli nemovitostí, přináší nejpřesnější filtrování nabídek na trhu, ale také umožňuje prověřovat důvěryhodnost zájemců. 

Obrázek ke článku Samba.ai: Personalizační nástroje hlásí připravenost na GDPR

Samba.ai: Personalizační nástroje hlásí připravenost na GDPR

Do ostrého nasazení nařízení GDPR, které upravuje nakládání s osobními údaji, zbývá pár dní, a vzbuzuje vrásky u řady provozovatelů služeb, které pracují s profilací návštěvníků na stránkách a personalizací obsahu. Český personalizační nástroj Samba.ai(dříve Yottly) zajišťující personalizaci webu a prediktivní automatizaci email marketingu je však slovy svého CEO Davida Vyskočila na GDPR plně připraveno. 

Obrázek ke článku Jak se liší metody šifrování dat?

Jak se liší metody šifrování dat?

Jaké výhody má celodiskové a souborové šifrování? A co vám přinese šifrování virtuálního disku? Ochranu důležitých dat řeší firmy různě. Mohou využít přístupových práv, zálohování, VPN nebo šifrování. Právě šifrování považují odborníci na kybernetickou bezpečnost za nejspolehlivější řešení.

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