Dynamické datové struktury (další poznámky povrchní)

V našem minulém programu pro h-genealogii jsme do pole ukládali strom záznamů. Každý záznam obsahoval jméno a seznam ČOP potomků. ČOP je vlastně index konkrétního záznamu v poli záznamů, které natahujeme podle potřeby. Zde je kód programu ještě jednou pro potřeby dnešní přednášky, pole pro uložení záznamů je navíc nove pojmenováno Pamet:

program DynDa;

type tCOP = integer;

type tUzel = record
               Jmeno : string;
               Deti  : array of tCOP;
             end;

var  Pamet : record
               Prvky : array of tUzel;
               Pocet : tCOP;
             end;

function X(const NoveJmeno : string; const NoveDeti : array of tCOP): tCOP;
var k : integer;
    i : tCOP;
begin
  // Sileny trik: necham nulty prvek nastaveny na zadne jmeno, zadne deti
  {Nejdříve musím vyrobit NOVOU POLOŽKU i}
  i := Pamet.Pocet+1;
  Pamet.Pocet := i;
  if i>High(Pamet.Prvky) then begin SetLength(Pamet.Prvky,10+2*High(Pamet.Prvky)); end;
  {Nikdy nezvetsovat po jedne, vzdy geometrickou radou !!!}
  X := i;
  with Pamet.Prvky[i] do begin
    Jmeno := NoveJmeno;
    SetLength(Deti,High(NoveDeti)+1);
    for k:=Low(NoveDeti) to High(NoveDeti) do Deti[k] := NoveDeti[k];
  end;
end;

function Jmeno2COP(const Jmeno:string) : tCOP;
var i : tCOP;
begin
   Jmeno2COP := 0;
   for i := Low(Pamet.Prvky) to High(Pamet.Prvky) do
     if Pamet.Prvky[i].Jmeno = Jmeno then begin
       Jmeno2COP := i;
       exit;
     end;
end;

function PocetPotomku(const COP:tCOP) : integer;
var i,s : integer;
begin
   s := 0;
   with Pamet.Prvky[COP] do
     for i := Low(Deti) to High(Deti) do s:=s+1+PocetPotomku(Deti[i]);
   PocetPotomku := s;
end;


var Otec : tCOP;
begin

  Otec := X('Petr',[
                    X('Karel',[
                               X('Mirek',[]),
                               X('Zdenek',[])
                              ]),
                    X('Ivan',[
                               X('Hugo',[
                                         X('Rudolf',[]),
                                         X('Gustav',[
                                                     X('Cecil',[])
                                                    ]),
                                         X('Klement',[])
                                        ])
                             ])
                   ]);

  Writeln(PocetPotomku( Jmeno2COP('Ivan') ) );

  Readln;
end.

V proceduře Jmeno2COP jsme pro hledání záznamu s daným jménem použili naivní metodu prohlížení pole prvek po prvku, konkréně
for i := Low(Pamet.Prvky) to High(Pamet.Prvky) do ....

V našem případě se funkce chová podle očekávání. Zavedeme-li ale proceduru pro likvidaci záznamu, třeba

procedure SmazPotomka(const COP_Rodice, COP_Potomka: tCOP);
var j,jmax : integer;
begin 
   with Pamet.Prvky[COP_Rodice] do
     for j := Low(Deti) to High(Deti) do begin
        if Deti[j] = COP_Potomka then begin
          jmax:=High(Deti);
          if j<jmax then Deti[j] := Deti[jmax];
          SetLength(Deti,jmax); {Zmesi pocet deti o jednu}
        end;
     end;
end;

která se použije v případě, že se dodatečně zjistí, že X není potomek rodiče Y [Hollywood 19??-2003]. V tom případě jednoduše smažeme příslušné číslo OP potomka ze seznamu dětí příslušného rodiče. Teď ale celý podstrom potomka zůstane viset ve vzduchu a příslušné záznamy stále obsahují strukturu potomstva vymazaného potomka. Naše funkce Jmeno2COP nám tak stále vrátí COP již vymazaného nelegitimního potomka, či některého z jeho potomků. Navíc tyto záznamy stále zabírají místo. Vypadá to, že bychom se museli naučit uvolňovat záznamy v poli tak, aby jejich místo mohli příště zabrat nově přidávané záznamy. Navíc, pokud bychom nechtěli s vymazáním nějakého záznamu přečíslovat OP osob uložených v následujících položkách pole, museli bychom snést, že volné položky se nebudou nacházet jen na konci pole záznamů ale i uprostřed. Tím by se podstatně zesložitila struktura potřebná k uchování informace o obsazených a volných položkách.

Typ ukazatel (delší desetiminutovka)

Na minulém příkladě jsme viděli, že se přirozeně objevil nový typ tCOP. Jakkoli šlo o přejmenovaný typ integer, jeho význam byl pořadí položky v seznamu, přičemž ale sama jeho hodnota (tedy to pořadí) význam neměla, pouze to, že na daném indexu je uložen Petr nebo Pavel. Kdyby někdo přehodil dvě položky nebo vložil do seznamu prázdné důležité by jen bylo jestli je význam tentýž (podobně jako vás v životě nezajímá ČOP vašich přátel a dokonce ani jasnovidkyně jej nechtějí znát při přepovídání vašeho osudu).

Každý pokus pracovat s prvkem s daným ČOP v proměnné i vede na zápis Pamet.Prvky[i] a nebylo by špatné kdybychom mohli použít nějakou zkratku a nemuseli pořád psát, že i je index, když máme na mysli zvíře s daným ČOP. Také by bylo dobré, kdybychom si pro každý typ nemuseli vytvářet zvláštní strukturu pro přidělování (alokaci) nových položek. V Pascalu na to jsou již od Wirtha proměnné typu ukazatel (angl. pointer).

Píšeme
type tXPtr = ^tXTyp;
var x : tXPtr;

a pak jen

x^ nebo třeba x^.Jmeno, kdykoli chceme pracovat s položkou na niž x ukazuje nebo jejími částmi. x^ se nazývá dynamická proměnná.

Protože jsme zavedli nový typ je na místě zopakovat si, že jako obvykle máme k dispozici tři povolené operace:

• Ta speciální, kvůli které byl daný typ vymyšlen, v tomoto případě dereference,
  tedy přidání ^ za výraz typu ukazatel na tXTyp, čímž dostaneme výraz typu tXTyp.
• Přiřazení. Jako obvykle lze přiřazovat proměnné stejných typů (nanejvýš svázaných přes =)
• Použití jako parametr procedury nebo funkce.
• Navíc je tu možnost ukazatele (stejného typu) porovnávat relačními operátory = a <> (to se záznamem ani polem nešlo)

V Pascalu máme k dispozici mechanismus pro vytvoření libovolného počtu nových proměnných přímo za běhu, aniž si musíme vytvářet zvláštní strukturu jako byla Pamet výše. Místo v paměti na novou proměnnou si vyžádáme procedurou New(x) a to z oblasti paměti zvané halda (angl. heap). V této oblasti najde správce haldy dostatečně veliký kus volné paměti a změní hodnotu proměnné x tak, aby na tento kus paměti ukazovala. Navíc si poznamená, že příslušný kus paměti je obsazený. Až proměnnou nebudeme potřebovat, přesněji data uložená na nějakém místě haldy, kam x ukazuje, nikoli vlastní proměnnou typu ukazatel, ta bude, řekněme, jako lokální proměnná procedury neustále zabírat 4 byte na zásobníku, budeme moci zabranou paměť označit zpět jako volnou pro případnou další recyklaci. Když už tedy x^ nepotřebujeme, měli bychom zabranou paměť vrátit voláním procedury Dispose(x). Tak udržíme za běhu programu minimální spotřebu paměti. V každém případě po skončení běhu programu mu OS veškerou paměť sebere, takže úklid na konci běhu programu není nezbytně nutný.
Pozn. Přesto to při ladění pokročilých programů uděláme, a poté se přesvědčíme, že nic nezůstalo neuvolněno, čímž můžeme odhalit skutečné chyby v uvolňování paměti. Příklad: vezměme program, který neustále běží a každou celou hodinu zapípá. Zvuk k pípání si pokaždé uložíme do (řekněme 200 kB) paměti z haldy. Opomeneme ji ale vrátit. Po měsíci běhu programu sebere tak program ostatním např. 150 MB paměti ... (Mimochodem, moderní operační systémy se vyrovnají i s takovou chybou a nevyužitých 150 MB paměti sice bude stále patřit pípacímu programu, ale protože nebude používaná, OS obsah paměti odloží do jakéhosi depozitáže, kde bude zabírat relativně levný odkládací prostor.)

Na paměť už nahlížíme jako na pole, ukazatel x totiž není index do pole prvků daného typu, ale přímo adresa paměti, kde je uložen. Do doby, než jakoukoli proměnnou typu ukazatel inicializujeme přiřazením nebo voláním New, ji nesmíme používat, možná někam ukazuje, ale určitě tam nemáme co šťourat, podobně jako se nemáme co koukat na náhodný index pole, když jsme si předtím nezařídili (přiřazením známé hodnoty indexu), že tam smíme.

var x: ^integer;
    y: ^real;
    w: real;
begin
  w := Pi;
  new(y);
  y := w;
  new(x);
  x := 12;
...
  dispose(x);
  dispose(y);
end;

Tabulka k výkladu kde a jak dlouho žijí lokální/globální a jak dlouho dynamické proměnné.

Existuje speciální hodnota nil, odpovídající adrese NULA, které sice smí ukazatel nabývat a kterou můžeme kontrolovat porovnáním (if x=nil then ...), ale x^ je nedovolená operace pokud x=nil. Na téhle adrese nic není a dnes už se z ní ani nesmí nic číst natož na ni něco psát. Příklad:

var x:^integer;
...
x  := nil; //ok
if (x=nil) then  // ok
                x^ := 0; // katastrofa

Následuje přepis minulého programu s použitím ukazatelů. Protože už není žádné globání pole Pamet a všechna zvířata jsou na haldě, nemůžeme je projít klec po kleci (stejně to vlastně bylo špatně) a musíme i při hledání podle jména v proceduře Jmeno2COP procházet strom jako graf pěkně nejdřív rodič, potom děti ...

program DynPtr;

type tCOP = ^tUzel; // jediná dovolená situace, kdy v Pascalu použití ident. předchází jeho deklaraci !!!
     tUzel = record
               Jmeno : string;
               Deti  : array of tCOP;
             end;

function X(const NoveJmeno : string; const NoveDeti : array of tCOP): tCOP;
var k : integer;
    i : tCOP;
begin
  New(i); //tady jsme si ušetřili práci
  X := i;
  with i^ do begin
    Jmeno := NoveJmeno;
    SetLength(Deti,High(NoveDeti)+1);
    for k:=Low(NoveDeti) to High(NoveDeti) do Deti[k]  := NoveDeti[k];
  end;
end;

function Jmeno2COP(const Koren : tCOP; const Jmeno:string) : tCOP;
var i : integer;
    Dite : tCOP;
begin
   Jmeno2COP := nil;
   {tady ale nemůžeme jako dríve projít pole, musíme rekursí projít strom}

   {Neni nahodou Koren^.Jmeno = Jmeno ?}
   if Koren^.Jmeno = Jmeno then begin
       Jmeno2COP := Koren;
       exit;
   end;

   {Ted projdu deti}
   for i := Low(Koren^.Deti) to High(Koren^.Deti) do begin
     Dite := Jmeno2COP(Koren^.Deti[i], Jmeno);
     if Dite <> nil then begin
       Jmeno2COP := Dite;
       exit;
     end;
  end;
end;

function PocetPotomku(const COP:tCOP) : integer;
var i,s : integer;
begin
   s := 0;
   with COP^ do
     for i := Low(Deti) to High(Deti) do s:=s+1+PocetPotomku(Deti[i]);
   PocetPotomku := s;
end;


var Otec : tCOP;
begin

  Otec := X('Petr',[
                    X('Karel',[
                               X('Mirek',[]),
                               X('Zdenek',[])
                              ]),
                    X('Ivan',[
                               X('Hugo',[
                                         X('Rudolf',[]),
                                         X('Gustav',[
                                                     X('Cecil',[])
                                                    ]),
                                         X('Klement',[])
                                        ])
                             ])
                   ]);

  Writeln(PocetPotomku( Jmeno2COP(Otec, 'Ivan') ) );

  Readln;
end.

function X(const NoveJmeno : string; 
           const NoveDeti : array of tCOP): tCOP;
var k : integer;
    i : tCOP;
begin

  i := Stromek.Pocet+1;
  Stromek.Pocet := i;
  if i>High(Stromek.Prvky) then 
        SetLength(Stromek.Prvky,10+2*High(Stromek.Prvky)); 

  X := i;

  Stromek.Prvky[i].Jmeno := NoveJmeno;
  SetLength(Stromek.Prvky[i].Deti,High(NoveDeti)+1);
  for k:=Low(NoveDeti) to High(NoveDeti) do 
         Stromek.Prvky[i].Deti[k] := NoveDeti[k];

end;

function X(const NoveJmeno : string; 
           const NoveDeti : array of tCOP): tCOP;
var k : integer;
    i : tCOP;
begin


  
  New(i);


  X := i;

  i^.Jmeno := NoveJmeno;
  SetLength(i^.Deti,High(NoveDeti)+1);
  for k:=Low(NoveDeti) to High(NoveDeti) do 
         i^.Deti[k] := NoveDeti[k];
  end;
end;

Tabulka: Reklama na ukazatele

Doplněním programu o několik příkazů Writeln si můžeme hodnoty pointerů znázornit graficky (cvičení v postscriptu pro nadšence). Vertikální souřadnice v grafu je adresa v paměti. Mimochodem, protože typ pointer je přirozeně převeditelný na integer (oba zabírají 4 byte), snese kompilátor přetypování integer(vyraz typu pointer), viz dále.

Poznámka pro zvídavé: Všiměte si, že za každou položkou, která má nenulový počet dětí, následuje mezera. V té se nachází prvky dynamického pole alokované procedurou SetLength(Deti,...). Protože ta je volána hned po příslušném new nachází se mezera hned za příslušným záznamem a kolečka by vlastně měla ležet v této oblasti. Podobně je to i s řetězci obsahujícími jména, ve skutečnosti je každý rámeček v grafu složen za dvou: prvního s dvěma ukazateli (na jméno a na seznam dětí) a ten je vždy následován druhým s polem znaků řetězce (a za ním by pak mohl ležet rámeček s kolečky tedy ukazateli na děti).

Cvičení: Rozmyslete si, jak by vypadala deklarace záznamu tObcan obsahující jméno, rok narození, ukazatel na otce, ukazatel na matku, seznam (dyn. pole) ukazatelů na děti. Samozřejmě ukazatele na otce, matku i děti by byly typu ^tObcan. Jak by pak vypadala reference (designátor), jíž bychom z proměnné Matka : tObcan zjistili rok narození otce jejího prvního dítěte ?

Hlavním rysem dynamických proměnných je, že i když v programu deklarujeme jen dvě tři proměnné typu ukazatel na něco, pokud dynamické proměnné vhodně pospojujeme, tak aby vytvářely souvislý graf (řekněme lineární řetězec či strom) můžeme vybudovat strukturu s tisíci záznamy. Běžné operace, jako je přidání či ubrání v takovéto struktuře se ale velmi odlišují od toho, co jsme viděli u lineárních struktur v poli a nebudeme se jimi zabývat. Protože tak ale lze v některých případech podstatně zmenšit časovou náročnost těchto operací, patří operace na všelijak pospojovaných dynamických datových strukturách mezi základní dovednosti informatiků. V [Deplhi6 Help] se píše: Moreover, some advanced programming techniques require the use of pointers.

Díky dynamickým polím vynecháme povídání o procedurách GetMem/FreeMem, které umožňují přidělit proměnné určené množství paměti. Třeba u variantního záznamu se tak dá šetřit pamětí, přidělit jí jen tolik kolik je třeba, ale pak si zase musíme dávat pozor přui dalším užití takové proměnné. Nejčastějším použitím ale bývalo přidělení omezeného množství paměti proměnné typu pole, jehož horní mez byla v definici typu nastavena přehnaně vysoko a deklarování proměnné takového typu bylo neúnosné, když se nakonec použilo jen malé procento položek na počátku a tak se deklaroval jen ukazatel na takovou proměnnou a místo New (které by přidělilo paměť pro kompletní proměnnou) se přes GetMem požádalo jen o potřebné množství paměti. Díky dynamickým polím (zázračné funkci SetLength) ale nemusíme takováto nouzová řešení dnes používat.

Ukazatel nemusí ukazovat jen na haldu, můžeme použít funkci addr nebo operátor @.

var p : ^integer;
    x,y : integer;
begin
  p := @y ;
  if p=addr(y) then x := p^ ; {velmi složitě zapsáno x:=y}
end.

Proto může nějaká dynamická datová struktura vyrůstat z položky uložené v globální proměnné a přitom i na tu se můžeme v případě potřeby odkázat ukazatelem, když potřebujeme odkaz zpět (ukazatel z potomka na rodiče). Naopak, pracujeme-li s objemnými datovými strukturami můžeme záměrně pracovat s dynamickými proměnnými a do pole, seznamu, fronty, zásobníku atp. ukládat jen ukazatele. Snížíme tak mj. čas potřebný na kopírovnání dat z/do pole do/z proměnné pro práci, i když bychom dokázali program napsat bez použití ukazatelů..

Charakter typu ukazatel na něco odráží způsob, jímž probíhá adresace paměti na nejnižší úrovni. Jakkoli v dřívějších PC (a v dnešních vysoce (cenově) optimalizovaných jednoúčelových osmi či šestnácti bitových počítačích) odrážely ukazatele složitý způsob práce s pamětí, je dnes typ ukazatel na něco interně totožný s typem integer, přesněji s jeho neoznaménkovanou versí (pro nás tedy typem longword). Samozřejmě to, že jde o 32 (a ne třeba 64 bitů) je dáno velikostí trubek a šuplíků procesoru a jim na míru šitým překladačem jazyka Pascal. Námi používaná verse jazyka Pascal je 32-bitová a tak ukazatel může nabývat 4 294 967 296 různých hodnot. Obyčejný program má omezen rozsah povolených adres ze kterých smí číst či na ně psát, takže aktuální velikost povolené oblasti paměti je až o 50% menší. Navíc nemusíme mít dost peněz na nákup fyzické paměti, takže třeba ani ty 2GB nám nemusí být dostupné. V následující tabulce je příklad přiřazení adres v rozsahu 0..2GB různým funkcím paměti při běhu programu (konkrétní čísla nejsou důležitá).

Pozn. K čemu to je užitečné vědět? Vidíme, třeba, že zásobník má maximální velikost 1MB. Pokud bychom psali program s velkou potřebou lokální paměti procedur a funkcí, můžeme ale tuto hodnotu změnit. A protože o výsledné poslepování programu z jednotlivých procedur, modulů, globálních dat a zásobníku se stará část překladače zvaná linker, pokud chcete změnit maximální velikost zásobníku, musíte hledat v nastavení projektu sekci linker a tam velikost zásobníku (stack size).