r3 - 24 May 2006 - 16:10:53 - Luba ParmyonovaYou are here: TWiki >  Refaldevel Web > FuturePlans > RecIter

Перевод рекурсии в итерацию

Суть подхода такова:

если рекурсия выражает идею простого цикла можно использовать $iter. Так будет и эффективнее, и читабельней.

Правило эквивалентного преобразования Рефал-Плюс-программ.

Пусть имеем Рефал Плюс код:

$func F ARGS = e;

   F ARGS =
      { /*
         * ... тело, развилки, пути ... несколько (i = 1..N) веток ...
         * ... которые заканчиваются так (рекурсия):
         */
               = Е_left_i <F E_parms_i> E_right_i;
        /*        
         * ... или так (конец рекурсии, результат):
         */
               = E_res_i;
        /*
         * ...
         */
      };

где Е* - выражения без вызовов функций, ARGS - жесткое образцовое.

Тогда эквивалентное итерационное определение функции:

   F ARGS =
      T ( ) ( ) ARGS $iter
      { /*
         * ... тело, развилки, пути ... несколько (i = 1..N) веток ...
         * ... которые заканчиваются так (продолжаем итерацию):
         */
               = T (e.R_left Е_left_i) (E_right_i e.R_right) E_parms_i;
        /*       
         * ... или так (конец итерации, результат):
         */
               = F (e.R_left E_res_i e.R_right) () ARGS;
        /*
         * ...
         */
      } :: s.GoOn (e.R_left) (e.R_right) ARGS,
      s.GoOn : F
      = e.R_left;
Здесь s.GoOn, e.R_left, e.R_right - свежие (уникальные) переменные.

Для программы "алгебра полиномов" (реализованы операции с полиномами "+", "*", "^", подстановка полинома в полином вместо переменной) было проделано обратное преобразование, чтобы убедиться в эффективности преобразования, по следующей схеме: пусть в теле функции имеется:

e.Expr-In $iter e.Body :: e.Format-Out, e.Pattern, e.Res
эта конструкция заменялась на следующую функцию:
$func Rec-Iter e.Format-Out = Format(e.Rest);

Rec-Iter e.Format-Out, {
    e.Pattern = e.Rest;
    e.Body :: e.Format-Out, <Rec-Iter e.Format-Out>;
вместо конструкции $iter в исходной функции подставляется вызов этой функции
<Rec-Iter e.Expr-In>

В результате тестовых прогонов рекурсивной (pol_rec) и итерационной (polinom) версии программы на трех входных файлах, каждый из которых содержит поток "трехадресных команд" над полиномами (программа читает и исполняет этот поток команд и на стандартный вывод выдает протокол и результаты вычислений) было получено следующее время работы:

для входного файла p-test.txt:
pol_rec: 0.26 сек.
polinom: 0.06 сек.

для входного файла p-test2.txt:
pol_rec: 17.57 сек.
polinom: 0.27 сек.

для входного файла p-test3.txt:
pol_rec: 81.69 сек.
polinom: 0.52 сек.

Требуется написать функцию, выполняющую преобразование рекурсивных функций в AS рефала в итерационные функции в AS.

Edit | WYSIWYG | Attach | Printable | Raw View | Backlinks: Web, All Webs | History: r3 < r2 < r1 | More topic actions
 
R+

This site is powered by the TWiki collaboration platformCopyright © by the contributing authors. All material on this collaboration platform is the property of the contributing authors.
Ideas, requests, problems regarding TWiki? Send feedback