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       13 371×

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

Obrázek ke článku První český hackathon ve vlaku inspirovaly služby jako  Tinder, Airbnb nebo Uber

První český hackathon ve vlaku inspirovaly služby jako Tinder, Airbnb nebo Uber

Patnáct set kilometrů, cesta přes dva státy, šestnáct hodin programování a přísun
energy drinků, tak by se dal shrnout unikátní hackathon ve vlaku pořádaný Kiwi.com.
Z Prahy do Košic a zpět se svezlo celkem 13 týmů, každý s originálním nápadem. Hlavní
výhru, voucher na letenky v hodnotě 2 500 EUR, si v Praze převzal tým až z Ukrajiny.
Společně naprogramovali aplikaci Fly2event, která vytváří cestovatelské balíčky ušité
uživatelům na míru podle toho, co si „olajkovali“ na Facebooku. Projekt má i podle
organizátorů budoucnost a jeho tvůrci ho v současnosti už spouští na webové stránce
fly2event.com.

Reklama
Reklama
Obrázek ke článku Gamifikace nakupování dorazila i do České republiky

Gamifikace nakupování dorazila i do České republiky

Zákazníci zejména retailových společností jsou často znuděni klasickými věrnostními či motivačními programy. Většinou z toho důvodu, že jsou jeden jako druhý a nepřináší nic nového. Ale i v České republice se projevují zahraniční trendy, nedávno zde totiž vstoupila na trh a rychle se uchytila nová platforma kombinující to nejlepší z věrnostních a motivačních programů, která navíc využívá prvky gamifikace – Rondo.cz. Na hlavní milníky vývoje nálad a motivace zákazníků a nejnovější trendy se zaměřil Jan Hřebabecký, spoluzakladatel Rondo.cz

Obrázek ke článku NopCommerce – datová vrstva a přístup k datům – 2. díl

NopCommerce – datová vrstva a přístup k datům – 2. díl

V minulém článku jsme si představili platformu NopCommerce z globálního pohledu. V dnešním díle se již zaměříme na konkrétní část systému, a to datovou vrstvu. Představíme si základní stavební kameny systému v podobě doménových objektů. Ukážeme si, jakým způsobem rozšířit doménové objekty a jakým způsobem přistupuje NopCommerce k nastavení systému a modulů.

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