Пређи на садржај

Алгоритми/Ада Имплементација

Извор: Викикњиге

Увод

[уреди]

Добродошли у Ада имплементације из викикњиге "Алгоритми". Уколико нисте упознати са Ада програмирањем, ево неколико правила:

  • Сви примери су потпуно функционални са свим потребним улазним и излазним операцијама. Међутим, само код које треба да имплементира алгоритам је копиран у текст - цели примери су доступни преко веза за 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;

Требало би да знате да бројеви са покретним зарезом су погодни за израчунавање фибоначијевих бројева. Неће пријавити услов грешке када је израчунати број превише велик - уместо тога, изгубиће прецизност, што доводи до тога да резултат губи суштину.