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

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

 

Algoritmizace v Delphi - 2. díl

Google       Google       14. 12. 2005       12 512×

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