Рекурсия по таблице О_о

Программирование на Атлантисе (VIP, FCOM, ARD), FastReport

Модераторы: m0p3e, edward_K, Модераторы

Ответить
Masygreen
Местный житель
Сообщения: 1089
Зарегистрирован: 04 сен 2008, 11:27
Откуда: Москва
Контактная информация:

Рекурсия по таблице О_о

Сообщение Masygreen »

Собственно сабж.. как сделать правильно??
Пример фейса ниже - смысл раскрутить формулу вычисления статьи затрат. Все бы хорошо но при рекурсии каждый раз сбрасывается _loop rcTable и получаем бесконечность ... :(
Надо как то заставить функцию ProcessSum открывать новый курсор в rcTable ...

Код: Выделить всё

interface MyInterface;
create view
  from rcTable
  ;

function ProcessSum(_prparent:comp;_prLivel:integer):double;
var _vSum:double;
{
 _loop   rcTable where ((_prparent==rcTable._Parent))
 { 
  _vSum := _vSum + ProcessSum(rcTable._Node,_prLivel+1);
 }
ProcessSum := _vSum;
}

HandleEvent
cmInit:
 {
   _loop VarTable
   {
     ProcessSum(VarTable._nRec,1);
  }
   CloseInterface(cmDefault);
   stop;
 }
 end; //HandleEvent
end.
Время ведет!
Masygreen
Местный житель
Сообщения: 1089
Зарегистрирован: 04 сен 2008, 11:27
Откуда: Москва
Контактная информация:

Re: Рекурсия по таблице О_о

Сообщение Masygreen »

походу сам себе ответил

Код: Выделить всё

external _loop
Время ведет!
Vik
Местный житель
Сообщения: 370
Зарегистрирован: 28 сен 2006, 15:43
Откуда: Санкт-Петербург
Контактная информация:

Re: Рекурсия по таблице О_о

Сообщение Vik »

Не надо никаких externel, есть PushPos и PopPos
n0where
Местный житель
Сообщения: 499
Зарегистрирован: 30 дек 2010, 08:16

Re: Рекурсия по таблице О_о

Сообщение n0where »

Vik писал(а):Не надо никаких externel, есть PushPos и PopPos
Разве это подходит под рекурсию?

PushPos и PopPos ведь можно использовать лишь для сохранения текущей позиции в буфер, причем только в 1 буфер. Рекурсия понимает под собой же вызов несколько раз процедуры, функции он сохранит только 2ой вызов (вложенный). а остальные (вложенные) заменит.

не прокатит же.
хороший программист — это человек, который переходя улицу с односторонним движением смотрит в обе стороны
Алексей
Местный житель
Сообщения: 2896
Зарегистрирован: 24 июн 2005, 12:12
Откуда: Иркутская область

Re: Рекурсия по таблице О_о

Сообщение Алексей »

зачем параметр prLivel:integer ? чтобы знать уровень вложенности? а зачем? вы же нигде это не используете.

я делал рекурсивные функции и у меня всё работало, правда она просто шла до дна и доставала значение последнего уровня.
глядя ваш код не совсем понимаю что хотите делать. суммировать какие-то значения или что?
galover
Местный житель
Сообщения: 794
Зарегистрирован: 16 ноя 2007, 13:52

Re: Рекурсия по таблице О_о

Сообщение galover »

Push и PopPos будут работать 100%. Сам ими пользуюсь при рекурсиях. Работают они по принципу стека, т.е. запоминать можно более одной позиции. Вот в этой теме http://www.tyumbit.ru/gal_forum/viewtop ... 14&start=0 есть еще наглядный пример от Screw (внизу обсуждения) как заменить рекурсию (обход в глубину) на итерации (обход в ширину).
Последний раз редактировалось galover 22 апр 2011, 10:47, всего редактировалось 1 раз.
Vik
Местный житель
Сообщения: 370
Зарегистрирован: 28 сен 2006, 15:43
Откуда: Санкт-Петербург
Контактная информация:

Re: Рекурсия по таблице О_о

Сообщение Vik »

n0where писал(а):Разве это подходит под рекурсию?
Естественно, подходит. Если бы сам не использовал, не написал бы. И я в курсе, что такое рекурсия, не надо мне объяснять, как она работает. Почитайте в документации про эти процедуры)
Masygreen
Местный житель
Сообщения: 1089
Зарегистрирован: 04 сен 2008, 11:27
Откуда: Москва
Контактная информация:

Re: Рекурсия по таблице О_о

Сообщение Masygreen »

Алексей писал(а):зачем параметр prLivel:integer ? чтобы знать уровень вложенности? а зачем? вы же нигде это не используете.

я делал рекурсивные функции и у меня всё работало, правда она просто шла до дна и доставала значение последнего уровня.
глядя ваш код не совсем понимаю что хотите делать. суммировать какие-то значения или что?
надо надо .. только в другом месте - естественно функции гораздо больше .. это так пример краткий для понятия сути задачи...
Время ведет!
Masygreen
Местный житель
Сообщения: 1089
Зарегистрирован: 04 сен 2008, 11:27
Откуда: Москва
Контактная информация:

Re: Рекурсия по таблице О_о

Сообщение Masygreen »

Vik писал(а):Не надо никаких externel, есть PushPos и PopPos
подскажите чем PushPos и PopPos лучше externel?
это тоже первое что мне в голову пришло, но потом отбросит т.к. подумал, что как и в случае с _loop в каждом следующем вызове позиции будут сбрасываться....
Время ведет!
Masygreen
Местный житель
Сообщения: 1089
Зарегистрирован: 04 сен 2008, 11:27
Откуда: Москва
Контактная информация:

Re: Рекурсия по таблице О_о

Сообщение Masygreen »

Почитал про вариант с маркерами .. выгода я так понимаю только в скорости . Мне это не важно .. у меня таблица больше 100 элементов ни когда не будет ...
Время ведет!
Vik
Местный житель
Сообщения: 370
Зарегистрирован: 28 сен 2006, 15:43
Откуда: Санкт-Петербург
Контактная информация:

Re: Рекурсия по таблице О_о

Сообщение Vik »

Masygreen писал(а):подскажите чем PushPos и PopPos лучше externel?
В общем, почему-то были необоснованные подозрения, что с external будет медленнее работать, но как только что выяснил, подозрения эти не оправдались. Написал на скорую руку небольшой тест:

Код: Выделить всё

Interface RecursionTest;
var
 _start : time;
 _stop  : time;
 times  : array[1..4] of time;

Create view
var
 vw_cPar: comp;
from
 Catalogs
,Catalogs Catalogs1
where
((
   vw_cPar == Catalogs1.cParent
))
;
function startTest(p_sTitle: string): void;
{
   _start := Cur_Time;
   WriteMessageLog(''#13'============ START : ' + p_sTitle + ' ============')
}
function stopTest(): time;
{
   _stop := Cur_Time;
   WriteMessageLog(''#13'============ END ============')
   NextVisual;
   result := Sub_Time(_stop, _start);
}
function recursion1(p_cPar: comp; p_sPad: string): void;
{
  _loop Catalogs where ((p_cPar == catalogs.cParent))
   {
      WriteMessageLog(p_sPad + catalogs.Name)
      PushPos(#Catalogs)
      recursion1(catalogs.Nrec, p_sPad + ' ')
      PopPos(#Catalogs)
   }
}
function recursion2(p_cPar: comp; p_sPad: string): void;
{
  external _loop Catalogs where ((p_cPar == catalogs.cParent))
   {
      WriteMessageLog(p_sPad + catalogs.Name)
      recursion2(catalogs.Nrec, p_sPad + ' ')
   }
}
function recursion3(p_cPar: comp; p_sPad: string): void;
var cCur: comp
{
  cCur := vw_cPar := p_cPar
  _loop Catalogs1
   {
      WriteMessageLog(p_sPad + catalogs1.Name)
      PushPos(#Catalogs1)
      recursion3(catalogs1.Nrec, p_sPad + ' ')
      vw_cPar := cCur;
      PopPos(#Catalogs1)
   }
}
function recursion4(p_cPar: comp; p_sPad: string): void;
var cCur: comp
{
  cCur := vw_cPar := p_cPar
  external _loop Catalogs1
   {
      WriteMessageLog(p_sPad + catalogs1.Name)
      recursion4(catalogs1.Nrec, p_sPad + ' ')
      vw_cPar := cCur;
   }
}
HandleEvent
  cmInit :
  {
     OpenMessageLog('e:\garbage\log\recursion.log', mfLog2Stream)
     var cStartNode: comp;

     //cStartNode := comp(471);
     cStartNode := comp(0);

     StartNewVisual(vtIndicatorVisual, vfTimer, 'Печать иерархии Catalogs', 4)

     startTest('Recursion1');
     recursion1(cStartNode, '');
     times[1] := stopTest();

     startTest('Recursion2');
     recursion2(cStartNode, '');
     times[2] := stopTest();

     startTest('Recursion3');
     recursion3(cStartNode, '');
     times[3] := stopTest();

     startTest('Recursion4');
     recursion4(cStartNode, '');
     times[4] := stopTest();

     var i : integer;

     for (i := 1; i <= 4; i++)
      {
        WriteMessageLog('Тест №' + i + ': ' + timeToStr(times[i], 'HH:MM:SS:SSS'))
      }

     CloseMessageLog ;
     StopVisual('',0);
  }
end;
End.  


Результаты трех прогонов получились такие:

Код: Выделить всё

Прогон 1
11:51:31 ¦ Тест №1: 00:00:06:29
11:51:31 ¦ Тест №2: 00:00:04:48
11:51:31 ¦ Тест №3: 00:00:05:95
11:51:31 ¦ Тест №4: 00:00:04:30
Прогон 2
11:52:16 ¦ Тест №1: 00:00:06:31
11:52:16 ¦ Тест №2: 00:00:04:50
11:52:16 ¦ Тест №3: 00:00:05:98
11:52:16 ¦ Тест №4: 00:00:04:22
Прогон 3
11:52:57 ¦ Тест №1: 00:00:06:36
11:52:57 ¦ Тест №2: 00:00:04:31
11:52:57 ¦ Тест №3: 00:00:05:94
11:52:57 ¦ Тест №4: 00:00:03:99
Так что зря я вас попутал, с external даже быстрее получается) А вод подцепки лучше все-таки во вьюху перенести.
edward_K
Заслуженный деятель интернет-сообщества
Сообщения: 5187
Зарегистрирован: 29 мар 2005, 17:49
Откуда: SPB galaxy spb

Re: Рекурсия по таблице О_о

Сообщение edward_K »

надо на своем выборе адреса попробовать - sterr все таки покруче будет catalogs.
Vik
Местный житель
Сообщения: 370
Зарегистрирован: 28 сен 2006, 15:43
Откуда: Санкт-Петербург
Контактная информация:

Re: Рекурсия по таблице О_о

Сообщение Vik »

Catalogs - первая таблица с иерархией и более-менее ощутимым числом записей, которая пришла в голову. Sterr у меня в три раза меньше.
Den
Местный житель
Сообщения: 1842
Зарегистрирован: 29 мар 2005, 17:49
Откуда: Ярославская область ОАО "Часовой завод Чайка" г. Углич
Контактная информация:

Re: Рекурсия по таблице О_о

Сообщение Den »

Обход без рекурсии и маркеров n-го узла деревянной таблицы :

Код: Выделить всё

Interface tree_example;
create view
var curNode, curParent:Comp;
  curnestlevel,nestLevel:Longint;
  from katpodr
      ,katpodr katpodr1 ;


Function GetNextNode(AParent:COMP; var ANode:COMP; var ANestLevel:Longint):boolean;
//Предполагается, что таблица ("TableAlias") упорядочена по CREC+.....
var curParent, curNode:COMP;
{

  Result:=False ;
  if ANode=0 {
                if GetFirst fastfirstrow katpodr where ((AParent==katpodr.cpodr)) =tsok
                {
                  ANode:=katpodr.NRec;
                  ANestLevel:=0;
                  Result:=True;
                  Exit;
                }
             }
  else 
    if GetFirst fastfirstrow katpodr where ((ANode==katpodr.cpodr))=tsok
    {
      ANode:=katpodr.NRec;
      ANestLevel:=ANestLevel+1;
      Result:=True;
      Exit;
    } 
    else
    {
      curNode:=ANode;
      curNestLevel:=ANestLevel;
      While (Result=False) do
      { 
        if GetFirst fastfirstrow katpodr where ((curNode==katpodr.nrec))<>tsOK
        {
          break;
        }
        curParent:=katpodr.cpodr;
        if GetNext fastfirstrow katpodr where ((curParent==katpodr.cpodr))=tsok
        {
          ANode:=katpodr.NRec;
          ANestLevel:=curNestLevel;
          Result:=True;
          break;
        }
        else
        {
          curNode:=curParent;
          curNestLevel:=curNestLevel-1;
          if (curNode = 0) OR (curNode = AParent) 
          {
            Result:=False;
            break;
          }
          else
          {
            Continue;
          }
        };
      }
      if (Result=False) {
        ANode:=0;
      }
    }
}


HandleEvent
CmInit: {
// n-ый просматриваемый узел
          curParent:=comp(16);
          curNode:=0;
          While (True = GetNextNode(curParent, curNode, nestLevel)) 
          do {
               if getfirst katpodr1 where ((curNode==nrec))=tsok {}
               logstrtofile('c:\debug\podrier.log',katpodr1.name+' NREC='+curNode+' на уровне '+nestLevel+' от родителя с NREC='+curParent);
             }
         }
end;
end.

Ответить