Recent

Author Topic: TTree depth-first traversal  (Read 2280 times)

avk

  • Full Member
  • ***
  • Posts: 141
    • my self-education project
Re: TTree depth-first traversal
« Reply #45 on: September 28, 2019, 02:24:05 pm »
@BrunoK, well, that's what I was talking about. Contrary to popular belief, recursive DFS is faster than its iterative equivalent. The fastest iterative DFS I can write for this case is:
Code: Pascal  [Select]
  1. procedure DfsTraversal(aTree: TIntTree);
  2. var
  3.   Stack, TopNode: PTopNode;
  4.   Next: TTreeNode;
  5.   AllocCount: SizeInt = 32;
  6.   StackTop: SizeInt = 0;
  7. begin
  8.   if not Assigned(aTree.Root) then
  9.     exit;
  10.   Stack := GetMem(AllocCount * SizeOf(TTopNode));
  11.   Stack[StackTop] := TTopNode.Create(aTree.Root);
  12.   while StackTop >= 0 do
  13.     begin
  14.       TopNode := Stack + StackTop;
  15.       if SizeUInt(Succ(TopNode^.ChildPos)) < TopNode^.Node.Children.Size then
  16.         begin
  17.           Inc(TopNode^.ChildPos);
  18.           Next := TopNode^.Node.Children[TopNode^.ChildPos];
  19.           Inc(StackTop);
  20.           if StackTop = AllocCount then
  21.             begin
  22.               AllocCount += AllocCount;
  23.               ReallocMem(Stack, AllocCount * SizeOf(TTopNode));
  24.             end;
  25.           Stack[StackTop] := TTopNode.Create(Next);
  26.         end
  27.       else
  28.         Dec(StackTop);
  29.     end;
  30.   FreeMem(Stack);
  31. end;  
  32.  
But it is still slower than the recursive one (at least on my machine).

BrunoK

  • Full Member
  • ***
  • Posts: 190
  • Retired programmer
Re: TTree depth-first traversal
« Reply #46 on: September 29, 2019, 05:25:31 pm »
@avk : revisited your 2 approaches. They give the same timings on my machine and are the fastest for DFT tree traversal code of any tested in this discussion.

Recursive - what changes is the extraction of Size in the inner procedure for iteration of children.
Code: Pascal  [Select]
  1. procedure TIntTree.DFTRecursive_avk(aTree: TIntTree; Callback: TTreeNodeCallBack
  2.   );
  3.   procedure Dfs(aNode: TIntNode);
  4.   var
  5.     I: SizeInt = 0;
  6.     lSize : Integer;
  7.   begin
  8.     Callback(aNode);
  9.     lSize := aNode.Children.Size;
  10.     while I < lSize do begin
  11.       Dfs(aNode.Children[I]);
  12.       Inc(I);
  13.     end;
  14.   end;
  15. var
  16.   lNode : TIntNode;
  17. begin
  18.   lNode := aTree.Root;
  19.   if Assigned(lNode) then
  20.     Dfs(lNode);
  21. end;
  22.  

Revisited iterative using pointers and hand made inlining. There the use of "with" improves the generated code.
Code: Pascal  [Select]
  1.  
  2. type
  3.   RPileItem = record
  4.     Node:      TIntNode;
  5.     ChildPos:  Integer;
  6.     Size:      Integer;
  7.   end;
  8.   PPileItem = ^RPileItem;
  9.  
  10. procedure TIntTree.DFTIterative_avk(aTree: TIntTree; Callback: TTreeNodeCallBack
  11.   );
  12. var
  13.   lStackAr : array of RPileItem;
  14.   lStackBase, lStackTop: PPileItem;
  15.   lNode : TIntNode;
  16. begin
  17.   lNode := aTree.Root;
  18.   if not Assigned(lNode) then
  19.     exit;
  20.   SetLength(lStackAr, cTreeDepth); // Constant cTreeDepth must be >= aTree.'Depth'
  21.   lStackBase := @lStackAr[0];
  22.   lStackTop := lStackBase - 1;
  23.   repeat
  24.     Callback(lNode); // Callback needed to check that all nodes where visited
  25.     Inc(lStackTop);
  26.     with lStackTop^ do begin
  27.       Node := lNode;
  28.       ChildPos := -1;
  29.       Size := lNode.Children.Size;
  30.     end;
  31.     repeat
  32.       with lStackTop^ do begin
  33.         Inc(ChildPos);
  34.         if ChildPos < Size then begin
  35.           lNode := Node.Children[ChildPos];
  36.           break;
  37.         end
  38.       end;
  39.       Dec(lStackTop);
  40.       if lStackTop < lStackBase then begin
  41.         lNode := nil;
  42.         break;
  43.       end;
  44.     until False;
  45.   until not Assigned(lNode);
  46. end;
  47.  

Lazarus trunk r. 62137/27.10.2019 (+/- patches regarding TScrollBar, IntitalSetupDialog, Options.Environment options, SearchResults).  Lazarus 3.0.6 raw from svn.
FPC 3.0.4 32 bits. (+heaptrc with leaked ClassName+Revisited TList) , Windows 10 Pro x64 (v. 1903 / 18362.418)

avk

  • Full Member
  • ***
  • Posts: 141
    • my self-education project
Re: TTree depth-first traversal
« Reply #47 on: September 30, 2019, 04:47:29 am »
@BrunoK, nice, thank you. It seems that the DFTRecursive_avk can be simplified without losing performance.
Code: Pascal  [Select]
  1. procedure TIntTree.DFTRecursive_avk(aTree: TIntTree; Callback: TTreeNodeCallBack);
  2.   procedure Dfs(aNode: TIntNode);
  3.   var
  4.     I: SizeInt;
  5.   begin
  6.     Callback(aNode);
  7.     for I := 0 to Pred(SizeInt(aNode.Children.Size)) do
  8.       Dfs(aNode.Children[I]);
  9.   end;
  10. begin
  11.   if Assigned(aTree.Root) then
  12.     Dfs(aTree.Root);
  13. end;
  14.  
You can also notice that the above procedures are not completely equivalent, DFTRecursive_avk does not make any assumptions regarding the depth of the tree, but DFTIterative_avk does.
« Last Edit: September 30, 2019, 05:18:02 am by avk »