Recent

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

jamie

  • Hero Member
  • *****
  • Posts: 3664
Re: TTree depth-first traversal
« Reply #30 on: September 23, 2019, 11:05:05 pm »
My god, the use of DFT "Discrete Fourier Transfers " is throwing me here, I am sure that isn't what you are referring to ?
The only true wisdom is knowing you know nothing

simone

  • Sr. Member
  • ****
  • Posts: 358
Re: TTree depth-first traversal
« Reply #31 on: September 23, 2019, 11:34:16 pm »
The subject is Depth First Traversal… I abbreviated with the acronym DFT... I removed from my memory continuous and discrete Fourier transforms :D More than twenty years have passed since I last used them!
« Last Edit: September 23, 2019, 11:51:43 pm by simone »
Microsoft Windows 10 64 bit - Lazarus 2.0.10

avk

  • Sr. Member
  • ****
  • Posts: 309
    • my self-education project
Re: TTree depth-first traversal
« Reply #32 on: September 24, 2019, 03:33:09 am »
I'm trying to say that if we want to compare the performance of an iterative and recursive version of some algorithm, these versions should be equivalent, otherwise the comparison does not make sense. Of couse, DepthFirstTraverse does a complete traversal of the tree, without any doubt, but this is a different algorithm.

Indeed in my test I compared a ricorsive DFT algorithm with an iterative  one

For me, equivalence of implementations means that they perform the same steps in the same sequence. Therefore, I imagine an iterative implementation of DFS in a slightly different way:
Code: Pascal  [Select][+][-]
  1. program rec_vs_nonrec;
  2.  
  3. {$mode objfpc}{$H+}
  4. {$MODESWITCH ADVANCEDRECORDS}
  5.  
  6. uses
  7.   SysUtils, DateUtils, gtree, gstack;
  8. type
  9.   TIntTree   = specialize TTree<Integer>;
  10.   TTreeNode  = TIntTree.TTreeNodeType;
  11.   TStack     = specialize TStack<TTreeNode>;
  12.   TChildEnum = TTreeNode.TTreeNodeList.TEnumerator;
  13.  
  14.   TEnumNode = record
  15.     Node: TTreeNode;
  16.     Enum: TChildEnum;
  17.     Visited: Boolean;
  18.     constructor Create(aNode: TTreeNode);
  19.   end;
  20.   PEnumNode  = ^TEnumNode;
  21.   TEnumStack = specialize TStack<TEnumNode>;
  22.  
  23. constructor TEnumNode.Create(aNode: TTreeNode);
  24. begin
  25.   Node := aNode;
  26.   Visited := False;
  27. end;
  28.  
  29. var
  30.   Tree: TIntTree = nil;
  31.   TreeSize, I: Integer;
  32.   StartTime: TDateTime;
  33.  
  34. function GenRandomTree: TIntTree;
  35. var
  36.   NodeStack, ChildStack, Tmp: TStack;
  37.   Node, Child: TTreeNode;
  38.   I, J: Integer;
  39. begin
  40.   Result := TIntTree.Create;
  41.   Result.Root := TTreeNode.Create;
  42.   Inc(TreeSize);
  43.   NodeStack := TStack.Create;
  44.   ChildStack := TStack.Create;
  45.   try
  46.     NodeStack.Push(Result.Root);
  47.     for I := 1 to 10 do
  48.       begin
  49.         while NodeStack.Size > 0 do
  50.           begin
  51.             Node := NodeStack.Top;
  52.             NodeStack.Pop;
  53.             for J := 1 to Random(9)+1 do
  54.               begin
  55.                 Child := TTreeNode.Create;
  56.                 Inc(TreeSize);
  57.                 Node.Children.PushBack(Child);
  58.                 ChildStack.Push(Child);
  59.               end;
  60.           end;
  61.         Tmp := NodeStack;
  62.         NodeStack := ChildStack;
  63.         ChildStack := Tmp;
  64.       end;
  65.   finally
  66.     NodeStack.Free;
  67.     ChildStack.Free;
  68.   end;
  69. end;
  70.  
  71. procedure DfsTraversal(aTree: TIntTree); //iterative
  72. var
  73.   Stack: TEnumStack;
  74.   Next: TTreeNode;
  75.   Curr: PEnumNode;
  76. begin
  77.   if not Assigned(aTree.Root) then
  78.     exit;
  79.   Stack := TEnumStack.Create;
  80.   try
  81.     Stack.Push(TEnumNode.Create(aTree.Root));
  82.     while Stack.Size > 0 do
  83.       begin
  84.         Curr := Stack.TopItem;
  85.         if not Curr^.Visited then
  86.           begin
  87.             Curr^.Visited := True;
  88.             Curr^.Enum := Curr^.Node.Children.GetEnumerator;
  89.           end;
  90.         if Curr^.Enum.MoveNext then
  91.           begin
  92.             Next := Curr^.Enum.Current;
  93.             Stack.Push(TEnumNode.Create(Next));
  94.           end
  95.         else
  96.           begin
  97.             Curr^.Enum.Free;
  98.             Stack.Pop;
  99.           end;
  100.       end;
  101.   finally
  102.     Stack.Free;
  103.   end;
  104. end;
  105.  
  106. procedure DfsTraversalR(aTree: TIntTree);
  107.   procedure Dfs(aNode: TTreeNode);
  108.   var
  109.     Child: TTreeNode;
  110.   begin
  111.     for Child in aNode.Children do
  112.       Dfs(Child);
  113.   end;
  114. begin
  115.   if Assigned(aTree.Root) then
  116.     Dfs(aTree.Root);
  117. end;
  118.  
  119. begin
  120.   Randomize;
  121.   for I := 1 to 10 do
  122.     begin
  123.       TreeSize := 0;
  124.       Tree := GenRandomTree;
  125.       try
  126.         WriteLn('generated new tree with ', TreeSize, ' nodes');
  127.         StartTime := Time;
  128.         DfsTraversal(Tree);
  129.         WriteLn('non-recursive DFS: ', MillisecondsBetween(Time, StartTime), 'ms');
  130.         StartTime := Time;
  131.         DfsTraversalR(Tree);
  132.         WriteLn('recursive DFS:     ', MillisecondsBetween(Time, StartTime), 'ms');
  133.         WriteLn;
  134.       finally
  135.         Tree.Free;
  136.       end;
  137.     end;
  138. end.
  139.  
Accordingly, the comparison results look different:
Code: Text  [Select][+][-]
  1. generated new tree with 13274394 nodes
  2. non-recursive DFS: 1341ms
  3. recursive DFS:     1108ms
  4.  
  5. generated new tree with 18425042 nodes
  6. non-recursive DFS: 1872ms
  7. recursive DFS:     1544ms
  8.  
  9. generated new tree with 18404551 nodes
  10. non-recursive DFS: 2208ms
  11. recursive DFS:     1777ms
  12.  
  13. generated new tree with 6713672 nodes
  14. non-recursive DFS: 692ms
  15. recursive DFS:     567ms
  16.  
  17. generated new tree with 10211120 nodes
  18. non-recursive DFS: 1036ms
  19. recursive DFS:     862ms
  20.  
  21. generated new tree with 12273356 nodes
  22. non-recursive DFS: 1241ms
  23. recursive DFS:     1016ms
  24.  
  25. generated new tree with 22542599 nodes
  26. non-recursive DFS: 2274ms
  27. recursive DFS:     1883ms
  28.  
  29. generated new tree with 24004838 nodes
  30. non-recursive DFS: 2435ms
  31. recursive DFS:     1996ms
  32.  
  33. generated new tree with 566744 nodes
  34. non-recursive DFS: 68ms
  35. recursive DFS:     46ms
  36.  
  37. generated new tree with 5299324 nodes
  38. non-recursive DFS: 532ms
  39. recursive DFS:     436ms
  40.  

simone

  • Sr. Member
  • ****
  • Posts: 358
Re: TTree depth-first traversal
« Reply #33 on: September 24, 2019, 10:45:20 am »
Thanks for your work Avk. I'm not sure that the proposed implementation of iterative DFS is optimal. Moreover, I have tried to compile your code, but I get some compiler errors. Now I'm busy at work and I can't go any further. In the evening I hope to have free time to better study your code and do experiments. Have you tried with larger trees? (for example: N=100000000 node, as in my previous test)?
« Last Edit: September 24, 2019, 11:23:13 am by simone »
Microsoft Windows 10 64 bit - Lazarus 2.0.10

avk

  • Sr. Member
  • ****
  • Posts: 309
    • my self-education project
Re: TTree depth-first traversal
« Reply #34 on: September 24, 2019, 01:37:45 pm »
Oops, excuse me, forgot to mention, to use the enumerator TTreeNode.Children I had to modify the gvector unit a bit:
Code: Pascal  [Select][+][-]
  1. {
  2.    This file is part of the Free Pascal FCL library.
  3.    BSD parts (c) 2011 Vlado Boza
  4.  
  5.    See the file COPYING.FPC, included in this distribution,
  6.    for details about the copyright.
  7.  
  8.    This program is distributed in the hope that it will be useful,
  9.    but WITHOUT ANY WARRANTY;without even the implied warranty of
  10.    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
  11.  
  12. **********************************************************************}
  13. {$mode objfpc}
  14.  
  15. unit gvector;
  16.  
  17. interface
  18.  
  19. type
  20.  
  21.   { TVector }
  22.  
  23.   generic TVector<T> = class
  24.   private
  25.   type
  26.     PT = ^ T;
  27.     TArr = array of T;
  28.   var
  29.     FCapacity:SizeUInt;
  30.     FDataSize:SizeUInt;
  31.     FData:TArr;
  32.  
  33.     procedure SetValue(Position: SizeUInt; const Value: T); inline;
  34.     function GetValue(Position: SizeUInt): T; inline;
  35.     function GetMutable(Position: SizeUInt): PT; inline;
  36.     procedure IncreaseCapacity; inline;
  37.  
  38.   const
  39.     // todo: move these constants to implementation when
  40.     // mantis #0021310 will be fixed.
  41.     SVectorPositionOutOfRange      = 'Vector position out of range';
  42.     SAccessingElementOfEmptyVector = 'Accessing element of empty vector';
  43.  
  44.   type
  45.     TVectorEnumerator = class
  46.     private
  47.       FVector: TVector;
  48.       FPosition: SizeUInt;
  49.       FFirstDone: Boolean;
  50.       function GetCurrent: T; inline;
  51.     public
  52.       constructor Create(AVector: TVector);
  53.       function GetEnumerator: TVectorEnumerator; inline;
  54.       function MoveNext: Boolean; inline;
  55.       property Current: T read GetCurrent;
  56.     end;
  57.  
  58.   public
  59.   type
  60.     TEnumerator = TVectorEnumerator;// <-- make TVectorEnumerator public
  61.     constructor Create;
  62.     function Size: SizeUInt; inline;
  63.     procedure PushBack(const Value: T); inline;
  64.     procedure PopBack; inline;
  65.     function IsEmpty: boolean; inline;
  66.     procedure Insert(Position: SizeUInt; const Value: T); inline;
  67.     procedure Erase(Position: SizeUInt); inline;
  68.     procedure Clear; inline;
  69.     function Front: T; inline;
  70.     function Back: T; inline;
  71.     procedure Reserve(Num: SizeUInt);
  72.     procedure Resize(Num: SizeUInt);
  73.  
  74.     function GetEnumerator: TVectorEnumerator; inline;
  75.  
  76.     property Items[i : SizeUInt]: T read getValue write setValue; default;
  77.     property Mutable[i : SizeUInt]: PT read getMutable;
  78. end;
  79.  
And for optimization purposes, I added an extra method to TStack:
Code: Pascal  [Select][+][-]
  1. {
  2.    This file is part of the Free Pascal FCL library.
  3.    BSD parts (c) 2011 Vlado Boza
  4.  
  5.    See the file COPYING.FPC, included in this distribution,
  6.    for details about the copyright.
  7.  
  8.    This program is distributed in the hope that it will be useful,
  9.    but WITHOUT ANY WARRANTY;without even the implied warranty of
  10.    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
  11.  
  12. **********************************************************************}
  13. {$mode objfpc}
  14.  
  15. unit gstack;
  16.  
  17. interface
  18.  
  19. uses gvector;
  20.  
  21. type
  22.  
  23.   { TStack }
  24.  
  25.   generic TStack<T>=class
  26.     private
  27.     type TContainer= specialize TVector<T>;
  28.     var FData:TContainer;
  29.     public
  30.     type
  31.       PItem = ^T;                   //for optimisation
  32.     Procedure Clear;
  33.     procedure Push(x:T);inline;
  34.     procedure Pop();inline;
  35.     function Top():T;inline;
  36.     function TopItem: PItem;inline; //for optimisation
  37.     function Size():longint;inline;
  38.     function IsEmpty():boolean;inline;
  39.     constructor Create;
  40.     destructor Destroy;override;
  41. end;
  42.  
  43. implementation
  44.  
  45. constructor TStack.Create;
  46. begin
  47.   FData:=TContainer.Create;
  48. end;
  49.  
  50. procedure TStack.Clear;
  51. begin
  52.   FData.Clear;
  53. end;
  54.  
  55. destructor TStack.Destroy;
  56. begin
  57.   FData.Destroy;
  58. end;
  59.  
  60. procedure TStack.Push(x:T);inline;
  61. begin
  62.   FData.PushBack(x);
  63. end;
  64.  
  65. procedure TStack.Pop();
  66. begin
  67.   FData.PopBack;
  68. end;
  69.  
  70. function TStack.Top(): T;
  71. begin
  72.   Top:=FData.Back;
  73. end;
  74.  
  75. function TStack.TopItem: PItem;
  76. begin
  77.   Result := FData.Mutable[FData.Size-1];
  78. end;
  79.  
  80. function TStack.Size(): longint;
  81. begin
  82.   Size:=FData.Size;
  83. end;
  84.  
  85. function TStack.IsEmpty(): boolean;
  86. begin
  87.   IsEmpty:=FData.IsEmpty;
  88. end;
  89.  
  90. end.
  91.  
As for the size of the tree, on my machine the swapping begins at about the size of a tree of 65000000, and, accordingly, these results do not seem interesting.

Leledumbo

  • Hero Member
  • *****
  • Posts: 8274
  • Programming + Glam Metal + Tae Kwon Do = Me
Re: TTree depth-first traversal
« Reply #35 on: September 24, 2019, 11:10:58 pm »
The algorithm implemented by Leledumbo is not equivalent to DFS, otherwise this thread would not have arisen.
Feel free to make the correct implementation if you think mine is wrong, but in my understanding it is correct (you can find similar implementations both in theory and practice, here's one example). DFS does not explicitly say how the node at the same level (siblings) must be visited, left-to-right, right-to-left, even random all are correct as long as once you visit a node and you see that node has children, then you must visit the children first before visiting that node's siblings.


avk

  • Sr. Member
  • ****
  • Posts: 309
    • my self-education project
Re: TTree depth-first traversal
« Reply #37 on: September 25, 2019, 01:50:48 pm »
@Leledumbo, sorry for the noise. I'm not saying that your algorithm is wrong, it just has a somewhat embarrassing name, you expect that it has the classic DFS inside.
Let me explain what I mean. Even if we ignore the order of traversal of nodes, the classic DFS can distinguish characteristic points that are extremely useful for various applications of this wonderful algorithm:
Code: Pascal  [Select][+][-]
  1. procedure Dfs(aNode: TTreeNode);
  2. var
  3.   Child: TTreeNode;
  4. begin
  5.   //2. here node visit
  6.   //callback provides pre-order
  7.   for Child in aNode.Children do
  8.     begin
  9.       //1. here node discovered
  10.       Dfs(Child);
  11.     end;
  12.   //3. here node and its subtree done
  13.   //callback provides post-order
  14. end;
  15.  

Try to find point 3 in your algorithm.

The iterative equivalent(DFS-B from your link) might look like this:
Code: Pascal  [Select][+][-]
  1. type
  2.   TIntTree   = specialize TTree<Integer>;
  3.   TTreeNode  = TIntTree.TTreeNodeType;
  4.  
  5.   TTopNode = record
  6.     Node: TTreeNode;
  7.     ChildPos: SizeInt;
  8.     constructor Create(aNode: TTreeNode);
  9.   end;
  10.  
  11.   TStack = specialize TStack<TTopNode>;
  12.  
  13. constructor TTopNode.Create(aNode: TTreeNode);
  14. begin
  15.   Node := aNode;
  16.   ChildPos := -1;
  17. end;
  18.  
  19. procedure DfsTraversal(aTree: TIntTree);
  20. var
  21.   Stack: TStack;
  22.   TopNode: TTopNode;
  23.   Next: TTreeNode;
  24. begin
  25.   if not Assigned(aTree.Root) then
  26.     exit;
  27.   Stack := TStack.Create;
  28.   Stack.Push(TTopNode.Create(aTree.Root));
  29.   while Stack.Size > 0 do
  30.     begin
  31.       TopNode := Stack.Top;
  32.       Stack.Pop;
  33.       if TopNode.ChildPos = -1 then
  34.         begin
  35.           //2. here node visit
  36.         end;
  37.       if Succ(TopNode.ChildPos) < TopNode.Node.Children.Size then
  38.         begin
  39.           Inc(TopNode.ChildPos);
  40.           Next := TopNode.Node.Children[TopNode.ChildPos];
  41.           //1. here node discovered
  42.           Stack.Push(TopNode);
  43.           Stack.Push(TTopNode.Create(Next));
  44.         end
  45.       else
  46.         begin
  47.           //3. here node done
  48.         end;
  49.     end;
  50.   Stack.Free;
  51. end;          
  52.  
 
You yourself decide whether to change anything in the gtree code or not.

...I'm not sure that the proposed implementation of iterative DFS is optimal...
Yes, at least we can get rid of the Visited field in TEnumNode and reduce the number of local variables in the procedure:
Code: Pascal  [Select][+][-]
  1. type
  2.   TEnumNode = record
  3.     Node: TTreeNode;
  4.     Enum: TChildEnum;
  5.     constructor Create(aNode: TTreeNode);
  6.   end;
  7.  
  8. constructor TEnumNode.Create(aNode: TTreeNode);
  9. begin
  10.   Node := aNode;
  11.   Enum := nil;
  12. end;
  13.  
  14. procedure DfsTraversal(aTree: TIntTree); //iterative
  15. var
  16.   Stack: TEnumStack;
  17. begin
  18.   if not Assigned(aTree.Root) then
  19.     exit;
  20.   Stack := TEnumStack.Create;
  21.   Stack.Push(TEnumNode.Create(aTree.Root));
  22.   while Stack.Size > 0 do
  23.     with Stack.TopItem^ do
  24.       begin
  25.         if Enum = nil then
  26.           Enum := Node.Children.GetEnumerator;
  27.         if Enum.MoveNext then
  28.           Stack.Push(TEnumNode.Create(Enum.Current))
  29.         else
  30.           begin
  31.             Enum.Free;
  32.             Stack.Pop;
  33.           end;
  34.       end;
  35.   Stack.Free;
  36. end;
  37.  
But the situation seems to remain the same.

marcov

  • Global Moderator
  • Hero Member
  • *****
  • Posts: 8799
  • FPC developer.
Re: TTree depth-first traversal
« Reply #38 on: September 25, 2019, 03:43:34 pm »
When recursion terminates, all these frames are deallocated, in reverse order. These operation are very expensive, since consume space of stack and time of CPU.

Note that is the case for places where iteration has no dynamically allocated state. As soon as you start to make allocations, this is possibly no longer true. Dynamic allocation on the heap might (and I would bet it is) more expensive than stack.

simone

  • Sr. Member
  • ****
  • Posts: 358
Re: TTree depth-first traversal
« Reply #39 on: September 25, 2019, 04:08:36 pm »
I believe that this issue depends on the allocation strategy adopted by heap implementation (i.e. best fit / first fit). However, I basically agree with your statement
Microsoft Windows 10 64 bit - Lazarus 2.0.10

BrunoK

  • Sr. Member
  • ****
  • Posts: 267
  • Retired programmer
Re: TTree depth-first traversal
« Reply #40 on: September 27, 2019, 03:44:46 pm »
In attachment pgmTreeDepthTrav_2.7z a test program mixing simone and rvk code.

I added 2 custom non recursive style DFT's, one using a home made customized pile and another one using TStack.

Also a slightly modified (far from perfect) random tree generator using TStack (see cMaxNodes,  cTreeDepth, MaxSiblings constants).

Note the non recursive one using TStack seems incredibly slower on Win/CPU64, if anyone has an idea about that I would be interested.

Result for a 20 mega nodes tree on I386 (CPU32) on my system :
Quote
Create random tree
Time Elapsed: 3468
GenRandomTree node count=20000000

Recursive DFT
Time Elapsed: 2437
Visited Nodes=20000000

Recursive DFT, rvk
Time Elapsed: 2421
Visited Nodes=20000000

Iterarive DFT
Time Elapsed: 2890
Visited Nodes=20000000

Procedural DFT, custom pile (bk)
Time Elapsed: 218
Visited Nodes=20000000

Procedural DFT _1, TStack (bk)
Time Elapsed: 797
Visited Nodes=20000000


Don't know if it is correct or even relevant to your discussion, if not, please ignore.



howardpc

  • Hero Member
  • *****
  • Posts: 3553
Re: TTree depth-first traversal
« Reply #41 on: September 27, 2019, 05:42:42 pm »
Nice one BrunoK!
Your RPile record implementation has impressive performance.
I get similar relative times for the various algorithms on my slightly slower 64bit hardware.

I found that enabling range checking or using heaptrc led to immediate errors or crashes, however.


BrunoK

  • Sr. Member
  • ****
  • Posts: 267
  • Retired programmer
Re: TTree depth-first traversal
« Reply #42 on: September 28, 2019, 10:45:06 am »
Edit :
In attachment pgmTreeDepthTrav_2.7z a test program mixing simone and rvk code.
Should read :
In attachment pgmTreeDepthTrav_2.7z a test program mixing simone and avk code.

I found that enabling range checking led to immediate errors or crashes.
Ok. In the RPile.Grow,  I used pointer subtraction for FillChar. The FillChar is not required so you can comment it out or replace the line with :
Code: Pascal  [Select][+][-]
  1. FillChar(Items[lOldCap], SizeOf(RPileItem) * (Capacity-lOldCap), 0);
Useful remark, I'll keep that in mind and when I use pointer subtractions.

or using heaptrc led to immediate errors or crashes, however.
This is absolutely normal if you kept the 20'000'000 nodes generation. Every heaptrc GetMem adds an overhead of ~100 bytes per memory allocation, so you get an OutOfMemory error.

Attachment corrected for Range checking and algorithm attributed to avk.

avk

  • Sr. Member
  • ****
  • Posts: 309
    • my self-education project
Re: TTree depth-first traversal
« Reply #43 on: September 28, 2019, 12:31:39 pm »
@BrunoK, great, but what happens if you compare your DepthFirstTraverseBk with such a recursive procedure?
Code: Pascal  [Select][+][-]
  1. procedure DfsTraversalR(aTree: TIntTree);
  2.   procedure Dfs(aNode: TTreeNode);
  3.   var
  4.     I: SizeInt = -1;
  5.   begin
  6.     while SizeUInt(Succ(I)) < aNode.Children.Size do
  7.      begin
  8.        Inc(I);
  9.        Dfs(aNode.Children[I]);
  10.      end;
  11.   end;
  12. begin
  13.   if Assigned(aTree.Root) then
  14.     Dfs(aTree.Root);
  15. end;  
  16.  

BrunoK

  • Sr. Member
  • ****
  • Posts: 267
  • Retired programmer
Re: TTree depth-first traversal
« Reply #44 on: September 28, 2019, 01:30:09 pm »
@BrunoK, great, but what happens if you compare your DepthFirstTraverseBk with such a recursive procedure?
@avk, your last recursive code is the WINNER, congrats !

Sligtly modified to integerate to the test program in attachement to :
Code: Pascal  [Select][+][-]
  1.  
  2. procedure TIntTree.DepthFirstTraverseRecursive_avk(Node: TTreeNodeType;
  3.     Callback: TTreeNodeCallBack);
  4.   { avk 0 -> slow
  5.   procedure Dfs(aNode: TTreeNode);
  6.   var
  7.     Child: TTreeNode;
  8.   begin
  9.     Callback(aNode);
  10.     for Child in aNode.Children do
  11.       Dfs(Child);
  12.   end;
  13.   }
  14.   { avk 1 -> winnner }
  15.   procedure Dfs(aNode: TTreeNode);
  16.   var
  17.     I: SizeInt = 0;
  18.   begin
  19.     Callback(aNode); // Callback needed to check that all nodes where visited
  20.     while I < aNode.Children.Size do begin
  21.       Dfs(aNode.Children[I]);
  22.       Inc(I);
  23.     end;
  24.   end;
  25. begin
  26.   if Assigned(Node) then
  27.     Dfs(Node);
  28. end;

Test results :
Quote
===================================================================================
I386 -O3   20'000'000 nodes
===================================================================================
Create random tree
Time Elapsed: 3343
GenRandomTree node count=20000000

Recursive DFT
Time Elapsed: 2390
Visited Nodes=20000000

Recursive DFT (avk)
Time Elapsed: 156
Visited Nodes=20000000

Iterarive DFT
Time Elapsed: 2702
Visited Nodes=20000000

Procedural DFT, custom pile (bk)
Time Elapsed: 203
Visited Nodes=20000000

Procedural DFT _1, TStack (bk)
Time Elapsed: 781
Visited Nodes=20000000

===================================================================================
x86_64 -O3   20'000'000 nodes
===================================================================================
Create random tree
Time Elapsed: 5795
GenRandomTree node count=20000000

Recursive DFT
Time Elapsed: 1609
Visited Nodes=20000000

Recursive DFT (avk)
Time Elapsed: 172
Visited Nodes=20000000

Iterarive DFT
Time Elapsed: 1890
Visited Nodes=20000000

Procedural DFT, custom pile (bk)
Time Elapsed: 234
Visited Nodes=20000000

Procedural DFT _1, TStack (bk) skipped because it is catastrophicaly slow in x86_64

===================================================================================
x86_64 -O3    40'000'000 nodes
===================================================================================
Create random tree
Time Elapsed: 11466
GenRandomTree node count=40000000

Recursive DFT
Time Elapsed: 3327
Visited Nodes=40000000

Recursive DFT (avk)
Time Elapsed: 360
Visited Nodes=40000000

Iterarive DFT fails for too many nodes

Procedural DFT, custom pile (bk)
Time Elapsed: 406
Visited Nodes=40000000

Procedural DFT _1, TStack (bk) skipped because it is catastrophicaly slow in x86_64

 

TinyPortal © 2005-2018