Algoritmizace v Delphi - 2. díl

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

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.

// 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;

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.