Алгоритми/Ада Имплементација
Увод
уредиДобродошли у Ада имплементације из викикњиге "Алгоритми". Уколико нисте упознати са Ада програмирањем, ево неколико правила:
- Сви примери су потпуно функционални са свим потребним улазним и излазним операцијама. Међутим, само код које треба да имплементира алгоритам је копиран у текст - цели примери су доступни преко веза за download-овање. (Приметити да то може да траје и до 48 сати док се ЦВС ажурира).
- Ретко користимо предефинисане типове у коду у примерима, али дефинишемо специјалне типове који су погодни за конкретне алгоритме.
- Ада допушта коришћење подразумеваних параметра функције; међутим, ми увек попунимо и именујемо све параметре, како би читалац могао да види које су му опције доступне.
- Ретко користимо пречице- као кад користимо атрибуте Image или Value за String <=> Integer конверзије.
Сва ова правила доприносе да код буде више разградив него што је потребно. Међутим, надамо се да је док такође зато и размуљив.
Поглавље 1: Увод
уредиСледећи потпрограми су имплементације примера из одељка Осмислити алгоритам.
Снизити
уредиПример Ада кода се не додаје на низ као алгоритми. Зато, креирамо празан низ жељене дужине, а онда мењамо места карактерима.
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;
Да ли би приступ додавању био могућ са Ада имплементацијом? Не, али би био значајно комплекснији и спорији.
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;
Поглавље 6: Динамичко програмирање
уредиФибоначијев низ
уредиСледећи кодови су имплементације примера Фибоначијев низ.
Једноставна имплементација
уреди...
Да израчунате негативне вредности Фибоначијевог низа није потребно, тако да смо дефинисали integer тип који почиње у 0. Са дефинисаним integer типом се може израчунати чак до Fib (87). Fib (88) ће резултирати Constraint_Error.
type Integer_Type is range 0 .. 999_999_999_999_999_999;
Можда приметите да не постоји једнакост за тврђење (n >= 0) из оригиналног примера. Ада ће тестирати тачност параметра пре позива функције.
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;
...
Кеширане имплементације
уреди...
За ову имплементацију нам треба посебан кеширани тип који може да складишти -1 као "не израчунат".
type Cache_Type is range -1 .. 999_999_999_999_999_999;
Прави тип за израчунавање фибоначијевих бројева наставља да почиње са 0. Пошто је подтип од кешираног типа , Ада ће аутоматски конвертовати између два. (валидност конверзије је - наравно - проверена)
subtype Integer_Type is Cache_Type range
0 .. Cache_Type'Last;
Да бисмо знали колико је велики кеш, треба прво прочитати праву вредност са командне линије.
Value : constant Integer_Type :=
Integer_Type'Value (Ada.Command_Line.Argument (1));
Кеширани низ почиње са елементом 2 с'обзиром да су Fib (0) и Fib (1) константе и завршава са вредношћу коју желимо да израчунамо.
type Cache_Array is
array (Integer_Type range 2 .. Value) of Cache_Type;
Кеш је инициализован на прву валидну вредност кешираног типа - а то је -1.
F : Cache_Array := (others => Cache_Type'First);
Из чега следи алгоритам:
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;
...
Ова имплементације је верна оригиналној из ове књиге. Међутим, у Ада имплементацији је то мало другачије:
када користите мало већи низ који такође складишти елементе 0 и 1 и инициализује их на тачне вредности
type Cache_Array is
array (Integer_Type range 0 .. Value) of Cache_Type;
F : Cache_Array :=
(0 => 0,
1 => 1,
others => Cache_Type'First);
и онда можете да уклоните први if.
if N = 0 or else N = 1 then return N; elsif F (N) /= Cache_Type'First then
Ово ће запамтити око 45% времена извшења (измерено на Linux i686), док вам треба само још два елемента у кешираном низу.
Имплементације оптимизације меморије
уредиОва верзија исто изгледа као и оригинална у ВикиКоду.
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;
Нешездесетчетворобитни цели бројеви
уредиВаш Ада компајлер нема подршку за 64-битне целе бројеве? Онда можете уместо тога да користите децималне бројеве. То резултира спорији програм (три пута спорији), али ће резултат бити исти.
Следећи пример показује како да дефинишете погодан децимални тип. Експериментишите са цифрама и опсезима параметара док не добијете оптимални излаз од Ада компејлера.
type Integer_Type is delta 1.0 digits 18 range
0.0 .. 999_999_999_999_999_999.0;
Требало би да знате да бројеви са покретним зарезом су погодни за израчунавање фибоначијевих бројева. Неће пријавити услов грешке када је израчунати број превише велик - уместо тога, изгубиће прецизност, што доводи до тога да резултат губи суштину.