Algoritmi/Ada Implementacija
Uvod
[uredi]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
[uredi]Sledeći potprogrami su implementacije primera iz odeljka Osmisliti algoritam.
Sniziti
[uredi]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
[uredi]-- 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
[uredi]Fibonačijev niz
[uredi]Sledeći kodovi su implementacije primera Fibonačijev niz.
Jednostavna implementacija
[uredi]...
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
[uredi]...
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
[uredi]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
[uredi]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.