Algoritmi/Ada Implementacija

Uvod

Dobrodošli u Ada implementacije iz vikiknjige "Algoritmi". Ukoliko niste upoznati sa Ada programiranjem, evo nekoliko pravila:

• Svi primeri su potpuno funkcionalni sa svim potrebnim ulaznim i izlaznim operacijama. Međutim, samo kod koje treba da implementira algoritam je kopiran u tekst - celi primeri su dostupni preko veza za download-ovanje. (Primetiti da to može da traje i do 48 sati dok se CVS ažurira).
• Retko koristimo predefinisane tipove u kodu u primerima, ali definišemo specijalne tipove koji su pogodni za konkretne algoritme.
• Ada dopušta korišćenje podrazumevanih parametra funkcije; međutim, mi uvek popunimo i imenujemo sve parametre, kako bi čitalac mogao da vidi koje su mu opcije dostupne.
• Retko koristimo prečice- kao kad koristimo atribute Image ili Value za String <=> Integer konverzije.

Sva ova pravila doprinose da kod bude više razgradiv nego što je potrebno. Međutim, nadamo se da je dok takođe zato i razmuljiv.

Poglavlje 1: Uvod

Sledeći potprogrami su implementacije primera iz odeljka Osmisliti algoritam.

Sniziti

Primer Ada koda se ne dodaje na niz kao algoritmi. Zato, kreiramo prazan niz željene dužine, a onda menjamo mesta karakterima.

 function To_Lower (C : Character) return Character renames
    Ada.Characters.Handling.To_Lower;

 --  tolower - преводи све алфабет карактере који су велико слово
 function To_Lower (Str : String) return String is
    Result : String (Str'Range);
 begin
    for C in  Str'Range loop
       Result (C) := To_Lower (Str (C));
    end loop;
    return Result;
 end To_Lower;

Da li bi pristup dodavanju bio moguć sa Ada implementacijom? Ne, ali bi bio značajno kompleksniji i sporiji.

Equal_Ignore_Case

--  equal-ignore-case -- враћа true ако су s или t једнаки,
 --  случај који се занемарује
 function Equal_Ignore_Case
   (S    : String;
    T    : String)
    return Boolean
 is
    O : constant Integer := S'First - T'First;
 begin
    if T'Length /= S'Length then
       return False;  --  ако нису истих дужина, онда 
                      --  нису једнаки
    else
       for I in  S'Range loop
          if To_Lower (S (I)) /=
             To_Lower (T (I + O))
          then
             return False;
          end if;
       end loop;
    end if;
    return True;
 end Equal_Ignore_Case;

Poglavlje 6: Dinamičko programiranje

Fibonačijev niz

Sledeći kodovi su implementacije primera Fibonačijev niz.

Jednostavna implementacija

...

Da izračunate negativne vrednosti Fibonačijevog niza nije potrebno, tako da smo definisali integer tip koji počinje u 0. Sa definisanim integer tipom se može izračunati čak do Fib (87). Fib (88) će rezultirati Constraint_Error.

 type Integer_Type is range 0 .. 999_999_999_999_999_999;

Možda primetite da ne postoji jednakost za tvrđenje (n >= 0) iz originalnog primera. Ada će testirati tačnost parametra pre poziva funkcije.

 function Fib (n : Integer_Type) return Integer_Type is
 begin
    if n = 0 then
       return 0;
    elsif n = 1 then
       return 1;
    else
       return Fib (n - 1) + Fib (n - 2);
    end if;
 end Fib;

...

Keširane implementacije

...

Za ovu implementaciju nam treba poseban keširani tip koji može da skladišti -1 kao "ne izračunat".

 type Cache_Type is range -1 .. 999_999_999_999_999_999;

Pravi tip za izračunavanje fibonačijevih brojeva nastavlja da počinje sa 0. Pošto je podtip od keširanog tipa , Ada će automatski konvertovati između dva. (validnost konverzije je - naravno - proverena)

 subtype Integer_Type is Cache_Type range
    0 .. Cache_Type'Last;

Da bismo znali koliko je veliki keš, treba prvo pročitati pravu vrednost sa komandne linije.

 Value : constant Integer_Type :=
    Integer_Type'Value (Ada.Command_Line.Argument (1));

Keširani niz počinje sa elementom 2 s'obzirom da su Fib (0) i Fib (1) konstante i završava sa vrednošću koju želimo da izračunamo.

 type Cache_Array is
    array (Integer_Type range 2 .. Value) of Cache_Type;

Keš je inicializovan na prvu validnu vrednost keširanog tipa - a to je -1.

 F : Cache_Array := (others => Cache_Type'First);

Iz čega sledi algoritam:

 function Fib (N : Integer_Type) return Integer_Type is
 begin
    if N = 0 or else N = 1 then
       return N;
    elsif F (N) /= Cache_Type'First then
       return F (N);
    else
       F (N) := Fib (N - 1) + Fib (N - 2);
       return F (N);
    end if;
 end Fib;

...

Ova implementacije je verna originalnoj iz ove knjige. Međutim, u Ada implementaciji je to malo drugačije:

kada koristite malo veći niz koji takođe skladišti elemente 0 i 1 i inicializuje ih na tačne vrednosti

 type Cache_Array is
    array (Integer_Type range 0 .. Value) of Cache_Type;

 F : Cache_Array :=
    (0      => 0,
     1      => 1,
     others => Cache_Type'First);

i onda možete da uklonite prvi if.

   if N = 0 or else N = 1 then
       return N;
    elsif F (N) /= Cache_Type'First then

Ovo će zapamtiti oko 45% vremena izvšenja (izmereno na Linux i686), dok vam treba samo još dva elementa u keširanom nizu.

Implementacije optimizacije memorije

Ova verzija isto izgleda kao i originalna u VikiKodu.

 type Integer_Type is range 0 .. 999_999_999_999_999_999;

 function Fib (N : Integer_Type) return Integer_Type is
    U : Integer_Type := 0;
    V : Integer_Type := 1;
 begin
    for I in  2 .. N loop
       Calculate_Next : declare
          T : constant Integer_Type := U + V;
       begin
          U := V;
          V := T;
       end Calculate_Next;
    end loop;
    return V;
 end Fib;

Nešezdesetčetvorobitni celi brojevi

Vaš Ada kompajler nema podršku za 64-bitne cele brojeve? Onda možete umesto toga da koristite decimalne brojeve. To rezultira sporiji program (tri puta sporiji), ali će rezultat biti isti.

Sledeći primer pokazuje kako da definišete pogodan decimalni tip. Eksperimentišite sa ciframa i opsezima parametara dok ne dobijete optimalni izlaz od Ada kompejlera.

 type Integer_Type is delta 1.0 digits 18 range
    0.0 .. 999_999_999_999_999_999.0;

Trebalo bi da znate da brojevi sa pokretnim zarezom su pogodni za izračunavanje fibonačijevih brojeva. Neće prijaviti uslov greške kada je izračunati broj previše velik - umesto toga, izgubiće preciznost, što dovodi do toga da rezultat gubi suštinu.