### Bookstore

 Computer Math and Games in Pascal (preview) Lazarus Handbook

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

#### avk

• Sr. Member
• Posts: 276
##### 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

• Sr. Member
• Posts: 256
• 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.

#### avk

• Sr. Member
• Posts: 276
##### 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 »