9.Prednaska

9. Prednáška

späť | ďalej

---

úlohy | cvičenie

Typ záznam

Typ záznam je ďalší štruktúrovaný typ, ktorý definujeme sami. Pripomeňme si typ pole: je to skupina nejako očíslovaných prvkov (premenných), ktoré sú všetky rovnakého typu, napr. 100-prvkové pole reťazcov, alebo 10000-prvkové pole znakov, alebo 7-prvkové pole textových súborov a pod. Takáto štruktúra má svoje meno (meno poľa) a k prvkom pristupujeme cez index (nejaký ordinálny typ, najčastejšie je to interval celých čísel).

Záznam je tiež skupina premenných, ktoré ale nemusia byť rovnakého typu. K prvkom záznamu (budeme hovoriť položky) budeme pristupovať cez ich meno. Pozrime si to na príklade. Najprv všeobecná konštrukcia definície záznamu

type meno typu = record meno položky: typ položky; meno položky: typ položky; ... end;

Teraz niekoľko definícií typov:

type
  TBod = record
    X, Y: Integer;
  end;
 
  TStudent = record
    Meno: string;
    Adresa: string;
    Rocnik: Byte;
    Priemer: Real;
  end;
 
  TSprite = record
    Pozicia: TBod;
    Faza: 0..3;
    Bmp: array [0..3] of TBitmap;
  end;
  

Prvým definovaným novým typom je tu TBod. Tento typ sa skladá z dvoch celočíselných premenných X a Y a preto bude v pamäti zaberať 8 bajtov.

Druhým novým typom je záznam TStudent, ktorý sa skladá zo štyroch položiek (premenných). Prvé dve položky sú znakové reťazce, za tým je jednobajtové celé číslo a na koniec je to jedno desatinné číslo. Keby sme pomocou SizeOf() ziťovali, koľko pamäte zaberá takýto typ, tak dostaneme hodnotu 24. Hoci v pamäti je to uložené takto:

obrázok rámik, v ktorom sú pod sebou ďalšie rámiky ...

a hodnota 24 vyplýva z toho, na aké adresy sa ukladajú desatinné čísla (vždy je to adresa deliteľná číslom 8, takže medzi premennou Rocnik a Priemer je 7 nevyužitých bajtov)

Typ TSprite obsahuje položku Pozicia, ktorá je opäť záznamom. Položka Bmp je zase 4-prvkové pole.

Identifikátory položiek musia spĺňať kritériá nových identifikátorov (nesmú začínať číslicou, musia sa líšiť od rezervovaných slov a pod.), ale sú to "súkromné" premenné záznamu a preto sa neprekrývajú s menami iných premenných, podprogramov, typov, ...

So záznamom pracujeme buď ako s celkom (celou skupinou položiek), napr. pri priraďovaní jednej premennej do inej, alebo pri posielaní ako parameter podprogramu a pod. Alebo môžeme pracovať so samostatnými položkami ako s obyčajnými premennými. Ukážeme to na príklade:

type
  TStudent = record
    Meno: string;
    Adresa: string;
    Rocnik: Byte;
    Priemer: Real;
  end;
 
var
  Student, Spoluziak: TStudent;
begin
  Student.Meno := 'Janko Hrasko';
  Student.Adresa := 'Mlyny';
  Student.Rocnik := 1;
  Student.Priemer := 1.23;
 
  Spoluziak := Student;
  Spoluziak.Meno := 'Jurko Fazulka';
 
end;

V príklade vidíme, že k položkám pristupujeme pomocou bodkového zápisu: za premennú typu záznam zapíšeme bodku a za tým meno položky. Malo by vám to pripomínať, napr. prácu s rôznymi nastaveniami pre Canvas (napr. Canvas.Brush, Pen.Color, ...), alebo s nastaveniami pre bitmápy (napr. Obrazok.Width := 100). Princíp je rovnaký, len grafické časti a bitmapy sú objekty, ktoré sú trochu zložitejšie ako záznamy. V príklade sme najprv priradili nejaké hodnoty do všetkých položiek záznamu Student, potom sme celý tento záznam priradili (skopírovali) do ďalšej záznamovej premennej Spoluziak. Na záver sme spolužiakovi zmenili Meno, pričom Adresa, Rocnik a Priemer ostali rovnaké ako v zázname Student.

V ďalšom príklade ukážeme, ako sa záznamy používajú v procedúrach a funkciách:

type
  TBod = record
    X, Y: Integer;
  end;
 
function BodToStr(B: TBod): string;
begin
  Result := Format('(%d, %d)', [B.X, B.Y]);
end;
 
procedure Posun(var B: TBod; DX, DY: Integer);
begin
  Inc(B.X, DX);   // B.X := B.X + DX;
  Inc(B.Y, DY);
end;
 
function Bod(NoveX, NoveY: Integer): TBod;
begin
  Result.X := NoveX;
  Result.Y := NoveY;
end;
 
var
  A, B, C: TBod;
begin
  A.X := 100;
  A.Y := 200;
  B := Bod(50, 150);
  C := A;
  Posun(C, 20, -15);
  WtiteLn('C = ', BodToStr(C));

V príklade sme zadefinovali tri podprogramy, ktoré pracujú so záznamom TBod. Funkcia BodToStr zo záznamu vyrobí znakový reťazec. Procedúra Posun zmení v zázname obe súradnice. Funkcia Bod z dvoch celých čísel vyrobí záznam.

Príklad s mestami na mape

Budeme riešiť príklad, v ktorom budeme klikať do obrázku mapy Slovenska na miesta, kde sa nachádzajú mestá. Informácie o týchto mestách (meno a pozíciu) budeme ukladať do poľa. Každým prvkom poľa bude štruktúra záznam s položkami Meno a X a Y. Do grafickej plochy vložíme obrázok mapy Slovenska zo súboru mapa.bmp: v inšpektore objektov dvojklikneme na nastavenie Picture a v dialógu nastavíme práve tento súbor:

Do grafickej plochy vložíme aj vstupný riadok Edit1, napr. takto

Pripravíme procedúry pre udalosti Form1Create (dvojklikneme do formuláru mimo komponentov) a Image1MouseDown (cez inšpektor objektov). Prvá verzia našej aplikácie môže vyzerať takto:

type
  TMesto = record
    X, Y: Integer;
    Meno: string;
  end;
 
procedure KresliMesto(M: TMesto; C: TCanvas);
begin
  C.Pen.Color := clBlue;
  C.Pen.Width := 3;
  C.Ellipse(M.X - 5, M.Y - 5, M.X + 5, M.Y + 5);
  c.Font.Height := 20;
  C.TextOut(M.X, M.Y, M.Meno);
end;
 
var
  Mesto: array [1..1000] of TMesto;     // zoznam miest
  N: Integer;                                   // momentálny počet miest
 
procedure TForm1.FormCreate(Sender: TObject);
begin
  N := 0;
  Edit1.Text := ;
end;
 
procedure TForm1.Image1MouseDown(Sender: TObject; Button: TMouseButton;
  Shift: TShiftState; X, Y: Integer);
begin
  Inc(N);
  Mesto[N].X := X;
  Mesto[N].Y := Y;
  Mesto[N].Meno := Edit1.Text;
  Edit1.Text := ;
  KresliMesto(Mesto[N], Image1.Canvas);
end;

Ako to funguje: po naštartovaní programu sa objaví mapa. Keď chceme pridať nejaké mesto, najprv do vstupného riadka napíšeme jeho meno (napr. Zvolen) a potom klikneme na miesto, kde sa má toto mesto vyznačiť (na bod so Zvolenom). Na príslušnom mieste sa nakreslí modrý krúžok a aj meno mesta. Procedúra Image1MouseDown zvýši počet miest , na posledné miesto v zozname miest (t.j. do premennej Mesto[N]) vloží súradnice a meno mesta a toto mesto nakreslí do mapy.

Zrejme pri každom spustení programu musíme zadávať všetky mestá od začiatku, lebo program si ich nikde nepamätá. Využijeme na to textový súbor "slovensko.txt", do ktorého sa automaticky pri štarte programu prečíta zoznam miest a pri končení programu sa momentálny zoznam miest zapíše do tohto súboru. Okrem toho dorobíme ešte jednu udalosť: keď zapíšeme nejaký text do Edit1 (teda meno nejakého mesta) a zatlačíme kláves <Enter>, udalosť Edit1KeyPress (vyberieme ju v inšpektore objektov v záložke Udalosti pre komponent Edit1) zapíše toto meno k posledne vytváranému mestu (v premennej Mesto[N]). Vďaka tomuto, ak pri kliknutí zabudneme vložiť meno mesta, tak <Enter> vo vstupnom riadku toto meno doplní dodatočne.

Už vieme, že udalosť FormCreate sa automaticky spúšťa pri štarte programu (ešte pred zobrazením formulára). Sem zapíšeme kód, ktorý prečíta textový súbor, informácie z neho zapíše do poľa záznamov Mesta a tieto mestá aj vykreslí do mapy. Pri čítaní využijeme pomocnú funkciu CitajMesto, ktorá z jedného riadku súboru prečíta informácie a vráti to ako výsledok funkcie, teda záznam typu TMesto.

K procedúre FormCreate existuje analogická procedúra FormDestroy, ktorá sa spúšťa pri udalosti onDestroy - vtedy, keď sa aplikácia končí. Túto procedúru vytvoríme v inšpektore objektov na komponente Form1 v záložke Udalosti, dvojklikneme v riadku onDestroy.

Kompletný projekt teraz vyzerá takto:

type
  TMesto = record
    X, Y: Integer;
    Meno: string;
  end;
 
procedure KresliMesto(M: TMesto; C: TCanvas);
begin
  C.Pen.Color := clBlue;
  C.Pen.Width := 3;
  C.Ellipse(M.X - 5, M.Y - 5, M.X + 5, M.Y + 5);
  c.Font.Height := 20;
  C.TextOut(M.X, M.Y, M.Meno);
end;
 
function CitajMesto(var T: TextFile): TMesto;
var
  Z: Char;
begin
  Result.Meno := ;
  Read(T, Z);
  while Z <> ';' do
  begin
    Result.Meno := Result.Meno + Z;
    Read(T, Z);
  end;
  ReadLn(T, Result.X, Result.Y);
end;
 
var
  Mesto: array [1..1000] of TMesto;
  N: Integer;
 
procedure TForm1.FormCreate(Sender: TObject);
var
  T: TextFile;
  I: Integer;
begin
  N := 0;
  Edit1.Text := ;
  if FileExists('slovensko.txt') then         // funkcia zistí, či takýto súbor už existuje
  begin
    AssignFile(T, 'slovensko.txt');
    Reset(T);
    while not Eof(T) do
    begin
      Inc(N);
      Mesto[N] := CitajMesto(T);
      KresliMesto(Mesto[N], Image1.Canvas);
    end;
    CloseFile(T);
  end;
end;
 
procedure TForm1.FormDestroy(Sender: TObject);
var
  T: TextFile;
  I: Integer;
begin
  AssignFile(T, 'slovensko.txt');
  Rewrite(T);
  for I := 1 to N do
    WriteLn(T, Mesto[I].Meno, ';', Mesto[I].X, ' ', Mesto[I].Y);
  CloseFile(T);
end;
 
procedure TForm1.Edit1KeyPress(Sender: TObject; var Key: char);
begin
  if (Key = #13) and (N > 0) and (Edit1.Text <> ) then
  begin
    Mesto[N].Meno := Edit1.Text;
    Edit1.Text := ;
    KresliMesto(Mesto[N], Image1.Canvas);
  end;
end;
 
procedure TForm1.Image1MouseDown(Sender: TObject; Button: TMouseButton;
  Shift: TShiftState; X, Y: Integer);
begin
  Inc(N);
  Mesto[N].X := X;
  Mesto[N].Y := Y;
  Mesto[N].Meno := Edit1.Text;
  Edit1.Text := ;
  KresliMesto(Mesto[N], Image1.Canvas);
end;

Ešte niekoľko poznámok k projektu:

• funkcia CitajMesto číta reťazec Meno po znakoch, lebo čítať musíme len po prvý výskyt znaku ';'
  • ak by sme to chceli prečítať napr. takto ReadLn(T, Result.Meno, Result.X, Result.Y); spadlo by to na chybovej správe
• vo FormCreate používame štandardnú funkciu FileExists, ktorá vie zistiť, či súbor, ktorý chceme otvoriť, už existuje
  • keby tu tento test nebol a textový súbor by ešte neexistoval, program by spadol pri otváraní príkazom Reset(T)
• nová procedúra FormDestroy sa automaticku spustí, keď bežiacu aplikáciu ukončíme korektne (napr. Alt-F4), keď ju ukončíme z prostredia Lazarus tlačidlom Zastaviť (alebo Ctrl-F2), FormDestroy sa nespustí, teda neuloží prípadné nové mestá

Príklad s poľom bodov

Zadefinujme nový typ TPoint, ktorý bude reprezentovať bod v grafickej ploche.

type
  TPoint = record
    X, Y: Integer;
  end;
 
function Point(X, Y: Integer): TPoint;
begin
  Result.X := X;
  Result.Y := Y;
end;
 
var
  XY: array [1..100000] of TPoint;
  N: Integer;

Zároveň s týmto novým typom zadefinujeme pole XY, do ktorého budeme ukladať postupnosť bodov v rovine. V premennej N si budeme pamätať momentálny počet bodov v tomto poli, na začiatku je N = 0, nový bod do tohto zoznamu pridávame za doteraz uložené, t.j. XY[N+1]. Nový bod budeme teda pridávať do tohto poľa takto:

  Inc(N);
  XY[N] := Point(nejakeX, nejakeY);

Napíšeme program, v ktorom budeme kresliť do grafickej plochy ťahaním myši. Pritom sa budú všetky body, ktoré prídu z udalostí Image1MouseDown a Image1MouseMove ukladať do poľa XY. Procedúra Image1MouseUp (ktorá sa zavolá pri udalosti onMouseUp, t.j. pri pustení tlačidla myši) by mohla s týmto poľom bodov robiť rôzne akcie. Napr.

• uložiť tento zoznam do súboru,
• uložiť zoznam do nejakej dátovej štruktúry,
• prekresliť túto krivku s nejakými novými parametrami;
• nejako spracovať tento zoznam matematickými operáciami (napr. zmenšovať, otáčať, ...)

Ukážeme program, v ktorom pri pustení myši sa kresba prekreslí hrubšou čiarou náhodnou farbou:

type
  TPoint = record
    X, Y: Integer;
  end;
 
function Point(X, Y: Integer): TPoint;
begin
  Result.X := X;
  Result.Y := Y;
end;
 
var
  XY: array [1..100000] of TPoint;
  N: Integer;
 
procedure TForm1.FormCreate(Sender: TObject);
begin
  Image1.Canvas.FillRect(Image1.ClientRect);
end;
 
procedure TForm1.Image1MouseDown(Sender: TObject; Button: TMouseButton;
  Shift: TShiftState; X, Y: Integer);
begin
  Image1.Canvas.Pen.Color := clBlack;
  Image1.Canvas.Pen.Width := 1;
  Image1.Canvas.MoveTo(X, Y);
  N := 1;
  XY[N] := Point(X, Y);
end;
 
procedure TForm1.Image1MouseMove(Sender: TObject; Shift: TShiftState; X,
  Y: Integer);
begin
  if Shift = [ssLeft] then
  begin
    Image1.Canvas.LineTo(X, Y);
    Inc(N);
    XY[N] := Point(X, Y);
  end;
end;
 
procedure TForm1.Image1MouseUp(Sender: TObject; Button: TMouseButton;
  Shift: TShiftState; X, Y: Integer);
var
  I: Integer;
begin
  if N > 0 then
  begin
    Image1.Canvas.Pen.Color := Random($1000000);  // to isté ako Random(256 * 256 * 256)
    Image1.Canvas.Pen.Width := 3;
    Image1.Canvas.MoveTo(XY[1].X, XY[1].Y);
    for I := 2 to N do
      Image1.Canvas.LineTo(XY[I].X, XY[I].Y);
  end;
  N := 0;
end;

Pozrime si deklaráciu nášho nového typu TPoint. Hoci sme ho definovali na začiatku nášho programu, túto deklaráciu môžeme úplne vyhodiť, keďže úplne rovnako definovaný typ je aj v štandardnej knižnici Pascalu. Taktiež funkcia Point, ktorá ako výsledok vracia záznam typu TPoint je definovaná už v štandardnej knižnici a preto jej definíciu môžeme z programu vyhodiť. Ak to vyskúšate (vyhodíte deklaráciu TPoint aj funkciu Point), program normálne funguje.

Vyhodenie deklarácie TPoint má ešte jeden užitočný dôsledok: grafické príkazy Polyline a Polygon očakávajú ako parameter ľubovoľné pole, ktorého prvkami sú TPoint. Ale nie ten náš pôvodný TPoint, ale len ten štandardný. Preto, namiesto for-cyklu, pomoocu ktorého sme vykresľovali lomenú čiaru v poli XY, môžeme použiť Polyline (s úplne rovnakým efektom):

procedure TForm1.Image1MouseUp(Sender: TObject; Button: TMouseButton;
  Shift: TShiftState; X, Y: Integer);
//var
//  I: Integer;
begin
  if N > 0 then
  begin
    Image1.Canvas.Pen.Color := Random($1000000);
    Image1.Canvas.Pen.Width := 3;
    Image1.Canvas.Polyline(XY[1..N]);
    //Image1.Canvas.MoveTo(XY[1].X, XY[1].Y);
    //for I := 2 to N do
    // Image1.Canvas.LineTo(XY[I].X, XY[I].Y);
  end;
  N := 0;
end;

Všimnite si skutočný parameter pri volaní Polyline: hoci parametrom má byť pole bodov TPoint, teda napr. Image1.Canvas.Polyline(XY);, my ale nechceme vykresľovať celý obsah poľa XY (10000 prvkov), ale len prvých N. Preto môžeme zapísať Image1.Canvas.Polyline(XY[1..N]);

Keď nahradíme volanie Polyline volaním Polygon, tak kreslená lomená čiara ohraničuje oblasť, ktorá sa vyplní farbou štetca. Procedúru Image1MouseUp môžeme zapísať takto:

procedure TForm1.Image1MouseUp(Sender: TObject; Button: TMouseButton;
  Shift: TShiftState; X, Y: Integer);
begin
  if N > 0 then
  begin
    Image1.Canvas.Pen.Color := Random($1000000);
    Image1.Canvas.Pen.Width := 3;
    Image1.Canvas.Polygon(XY[1..N]);
  end;
  N := 0;
end;

Príkaz with

Príkaz with umožňuje pristupovať k prvkom záznamu (alebo objektu) bez toho, aby sme zakaždým museli uvádzať meno premennej (resp. objektu). Syntax príkazu je

with premenná do príkaz;

Premenná musí byť typu záznam (objekt). V tele príkazu sa potom všetky premenné skontrolujú, či nie sú položkami tohto záznamu. Ak nie sú, tak zrejme to budú "obyčajné" premenné. Ak máme deklarácie

type
  TStudent = record
    Meno: string;
    Adresa: string;
  end;
var
  Prvak: TStudent;

nasledovné príkazy budú ekvivalentné:

Prvak.Meno := ’Tomas’;
Prvak.Adresa := ’Kosice’;

s týmto zápisom

with Prvak do
begin
  Meno := ’Tomas’;
  Adresa := ’Kosice’;
end;

Príkazy with môžu byť vnorené, napr.

with premenná1 do with premenná2 do príkaz;

môžeme to skrátene zapísať aj takto:

with premenná1, premenná2 do príkaz;

Príkaz with môžeme využiť aj pri kreslení. Grafická plocha Image1, plátno Canvas ale napr. aj štetec Brush sú objekty a preto môžeme využiť with. Takýto zápis

Image1.Canvas.Brush.Color := clYellow;
Image1.Canvas.Brush.Style := bsSolid;
Image1.Canvas.Rectangle(0, 100, 50, 200);

Môžeme prepísať

with Image1.Canvas do
begin
  Brush.Color := clYellow;
  Brush.Style := bsSolid;
  Rectangle(0, 100, 50, 200);
end;

ale aj

with Image1.Canvas do
begin
  with Brush do
  begin
    Color := clYellow;
    Style := bsSolid;
  end;
  Rectangle(0, 100, 50, 200);
end;

ale aj

with Image1.Canvas, Brush do
begin
  Color := clYellow;
  Style := bsSolid;
  Rectangle(0, 100, 50, 200);
end;

Tento príkaz niektorí programátori neobľubujú, lebo niekedy je tu nemalé riziko, že to Pascal pochopí inak, ako sme zamýšľali, hlavne pri vnorených príkazoch with.

Hľadanie v poli

Predpokladajme, že máme nejaké veľké pole celých čísel, v ktorom máme nájsť nejakú konkrétnu hodnotu. Hoci v praxi by sme skôr prehľadávali pole, napr. znakových reťazcov, alebo pole záznamov, my si to zjednodušíme na pole celých čísel.

type
  TPole = array [1..100000] of Integer;
var
  Pole: TPole;
  N: Integer;

Pole môžeme zaplniť náhodnými hodnotami, napr. takto:

N := High(Pole);
for I := 1 to N do
  Pole[I] := Random(MaxInt);

Nasledujúca funkcia zisťuje, či sa nejaká hodnota v tomto poli nachádza a ak áno, vráti index tohto prvku v poli. Inak vráti hodnotu 0:

function Hladaj(Hodnota: Integer): Integer;
begin
  Result := 1;
  while (Result <= N) and (Pole[Result] <> Hodnota) do
    Inc(Result);
  if Result > N then
    Result := 0;
end;

Ak hľadáme hodnotu, ktorá sa v poli nenachádza, tak ju musíme porovnať so všetkými hodnotami v poli. Teda vtedy while-cyklus prejde N-krát.

Algoritmus hľadania môžeme trochu vylepšiť, ak budeme predpokladať, že pole je vzostupne utriedené (zrejme ho nemôžeme vytvárať hore uvedeným for-cyklom). Vylepšená verzia hľadania:

function Hladaj(Hodnota: Integer): Integer;
begin
  Result := 1;
  while (Result <= N) and (Pole[Result] < Hodnota) do
    Inc(Result);
  if (Result > N) or (Pole[Result] <> Hodnota) then
    Result := 0;
end;

Zistite, čo bude funkcia Hladaj vyhľadávať, ak z nej vyhodíme zeleným označenú časť.

Utriedenú pole môžeme prehľadávať aj od konca:

function Hladaj(Hodnota: Integer): Integer;
begin
  Result := N;
  while (Result > 0) and (Pole[Result] > Hodnota) do
    Dec(Result);
  if (Result <> 0) and (Pole[Result] <> Hodnota) then
    Result := 0;
end;

Predpokladali sme, že pole je utriedené, napíšme procedúru Pridaj, tak aby sa nová hodnota vkladala na správne miesto.

procedure Pridaj(Hodnota: Integer);
var
  I: Integer;
begin
  I := N;
  while (I > 0) and (Pole[I] > Hodnota) do
  begin
    Pole[I+1] := Pole[I];
    Dec(I);
  end;
  Pole[I+1] := Hodnota;
  Inc(N);
end;

While-cyklus tu posunie prvky poľa tak, aby sa nová hodnota mohla zasunúť na správne miesto. Zrejme predpokladáme, že zaraďovaná hodnota sa ešte v poli nenachádza.

Binárne vyhľadávanie

---

Naučíme sa nový typ algoritmu, tzv. binárne vyhľadávanie. Je podobný tomu, ako keď hľadáme v telefónnom zozname:

• otvoríme približne v strede zoznamu: ak je hľadané slovo v abecede skôr ako slovo v strede telefónneho zoznamu, tak budeme pokračovať v prednej v jeho polovici, inak v druhej polovici,
• opäť vo vybranej polovici zoznamu sa pozrieme do jeho stredu a porovnáme s hľadaným slovom: ak je v abecede skôr, budeme pokračovať v prvej časti, inak v druhej,
• takto budeme postupne hľadať v menšom a menšom úseku zoznamu, až kým nenarazíme na hľadané slovo.

Treba si zapamätať, že to funguje, len ak je pole, resp. tabuľka utriedená:

function Hladaj(Hodnota: Integer): Integer;
var
  Zac, Kon, Stred: Integer;
begin
  Zac := 1;                          // začiatok intervalu
  Kon := N;                          // koniec intervalu
  while Zac <= Kon do
  begin
    Stred := (Zac + Kon) div 2;      // stred intervalu
    if Pole[Stred] < Hodnota then
      Zac := Stred + 1
    else if Pole[Stred] > Hodnota then
      Kon := Stred - 1
    else
      Zac := K + 1;                  // našiel
  end;
  if Pole[Stred] = Hodnota then
    Result := Stred
  else
    Result := 0;
end;

alebo ešte iné riešenie, ktoré využije vyskočenie z podprogramu pomocou príkazu Exit:

function Hladaj(Hodnota: Integer): Integer;
var
  Zac, Kon: Integer;
begin
  Zac := 1;
  Kon := N;
  while Zac <= Kon do
  begin
    Result := (Zac + Kon) div 2;
    if Pole[Result] = Hodnota then
      Exit;
    if Pole[Result] < Hodnota then
      Zac := Result + 1
    else
      Kon := Result - 1;
  end;
  Result := 0;
end;

Príkaz Exit neukončí vykonávanie celého programu, ale len podprogramu, v ktorom sa nachádza. Ak vyskakujeme z funkcie, zrejme ešte pred príkazom Exit treba priradiť do Result výslednú hodnotu funkcie.

Ďalšie informácie o tomto vyhľadávaní si môžete pozrieť na stránkach sk.wikipedia alebo en.wikipedia

Meranie rýchlosti vyhľadávania

Použitím štandardných podprogramov Now (vráti momentálny dátum a čas v počítači s presnosťou na tisíciny sekundy) a DecodeTime (dekóduje takto získaný čas na hodiny, minútu, sekundy a milisekundy) môžeme dosť presne odmerať, ako dlho bežal nejaký výpočet. (Keďže pracujeme v konzolovom režime, musíme do riadku uses pridať aj SysUtils) Budeme to organizovať napr. takto:

uses
  Classes, SysUtils;
 
function Cas(C: TDateTime): string;
var
  Hod, Min, Sek, Msek: Word;
begin
  DecodeTime(C, Hod, Min, Sek, Msek);
  Result := Format('%d:%.2d:%.2d:%.3d', [Hod, Min, Sek, Msek]);
end;
 
var
  ZapamatanyCas: TDateTime;
begin
 
  ZapamatanyCas := Now;                               // zapamätá si momentálny čas
  WriteLn('start o ', Cas(ZapamatanyCas));
 
  // výpočet, ktorý potrebujeme odmerať
 
  WriteLn('testovanie trvalo ', Cas(Now - ZapamatanyCas));     // výpis času
  ReadLn;
end.

Vyhľadávania môžeme otestovať napr. takto:

var
  Pole: array [1..10000000] of Integer;
 
function Hladaj1(Hodnota: Integer): Integer;
begin
  Result := High(Pole);
  while (Result > 0) and (Pole[Result] <> Hodnota) do
    Dec(Result);
end;
 
function Hladaj2(Hodnota: Integer): Integer;
begin
  Result := High(Pole);
  while (Result > 0) and (Pole[Result] > Hodnota) do
    Dec(Result);
  if (Result <> 0) and (Pole[Result] <> Hodnota) then
    Result := 0;
end;
 
function Hladaj3(Hodnota: Integer): Integer;
var
  Zac, Kon: Integer;
begin
  Zac := 1;
  Kon := High(Pole);
  while Zac <= Kon do
  begin
    Result := (Zac + Kon) div 2;
    if Pole[Result] = Hodnota then
      Exit;
    if Pole[Result] < Hodnota then
      Zac := Result + 1
    else
      Kon := Result - 1;
  end;
  Result := 0;
end;
 
const
  Pocet = 1000;   // Pocet = 10000000; pre binárne vyhľadávanie
var
  ZapamatanyCas: TDateTime;
  I, Max: Integer;
begin
  Randomize;
  Pole[1] := 1;
  for I := 2 to High(Pole) do
    Pole[I] := Pole[I-1] + Random(100) + 1;
  Max := Pole[High(Pole)] + 100;
 
  ZapamatanyCas := Now;
  WriteLn('startujem o ', Cas(ZapamatanyCas), ' pre ', Pocet, ' testov ... ');
  for I := 1 to Pocet do
    Hladaj1(Random(Max));
 
  WriteLn('testovanie trvalo ', Cas(Now - ZapamatanyCas));
  ReadLn;
end.

Postupne otestujeme rýchlosť vyhľadávania pre obyčajné sekvenčné (Hladaj1), sekvenčné v utriedenom poli (Hladaj2) a binárne vyhľadávanie (Hladaj3). Pre Binárne vyhľadávanie zmeníme počet testov z 1000 na 10000000 (t.j. 10000-krát viac). V závislosti od kvality vášho počítača vám môžu vyjsť asi takéto výsledky:

algoritmus	počet testov	trvanie	trvanie jedného
Hladaj1	1000	48 sek.	0.048 sek.
Hladaj2	1000	25 sek.	0.025 sek
Hladaj3	10000000	24 sek.	0.0000024 sek

Otestujte a porovnajte to na vašom počítači. Vedeli by ste matematicky zdôvodniť, prečo je binárne vyhľadávanie v 10mld. prvkovom utriedenom poli asi 10000-krát rýchlejšie ako sekvenčné?

Poznámky:

• pole má 10M celých čísel, t.j. v pamäti zaberá 40MB,
• pole sa na začiatku vygenerovalo tak, aby bolo vzostupne utriedené - každý ďalší prvok sa vypočítal tak, že sa k predchádzajúcemu pripočítala nejaká malá náhodná hodnota,
• potom sa zapamätá momentálny čas (až na milisekundy), potom sa nejaký počet-krát (napr. 1000) spustí algoritmus hľadania s nejakými náhodnými hodnotami a na záver sa od momentálneho času odpočíta zapamätaný - tým dostaneme čas trvania 1000 spustení funkcie
  • všimnite si, že hoci je Hladaj funkciou, volali sme ju ako keby bola procedúrou - toto si môžeme dovoliť vtedy, keď nám nevadí, že sa stratí výsledok funkcie

späť | ďalej