Created
November 20, 2015 22:40
-
-
Save ionuttamas/25cae27ed0d5fb780b2c to your computer and use it in GitHub Desktop.
Ref vs Queue for tree traversal
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
using System; | |
using System.Collections.Generic; | |
using System.Diagnostics; | |
namespace ConsoleApplication13 | |
{ | |
internal class Node | |
{ | |
public string Value { get; set; } | |
public List<Node> Children { get; set; } | |
public Node() | |
{ | |
Children = new List<Node>(); | |
} | |
} | |
class Program | |
{ | |
static void Main(string[] args) | |
{ | |
const int ITERATIONS = 100000; | |
Node root = GenerateTree(20, 4); | |
Stopwatch watch = new Stopwatch(); | |
watch.Start(); | |
for (int i = 0; i < ITERATIONS; i++) | |
{ | |
GetNodes(root); | |
} | |
Console.WriteLine(watch.ElapsedMilliseconds); | |
watch.Restart(); | |
for (int i = 0; i < ITERATIONS; i++) | |
{ | |
var nodes = new List<Node>(); | |
GetNodes(root, ref nodes); | |
} | |
Console.WriteLine(watch.ElapsedMilliseconds); | |
Console.Read(); | |
} | |
private static Node GenerateTree(int count, int childrenCount) | |
{ | |
if (count == 0) | |
return null; | |
if (count == 1) | |
{ | |
return new Node | |
{ | |
Value = Guid.NewGuid().ToString() | |
}; | |
} | |
var node = new Node | |
{ | |
Value = Guid.NewGuid().ToString() | |
}; | |
for (int i = 0; i < childrenCount; i++) | |
{ | |
node.Children.Add(GenerateTree(count / 2, childrenCount)); | |
} | |
return node; | |
} | |
private static void GetNodes(Node root, ref List<Node> nodes) | |
{ | |
if (root == null) | |
return; | |
nodes.Add(root); | |
nodes.AddRange(root.Children); | |
foreach (var child in root.Children) | |
{ | |
// stack overhead | |
GetNodes(child, ref nodes); | |
} | |
} | |
private static List<Node> GetNodes(Node root) | |
{ | |
Queue<Node> queue = new Queue<Node>(); | |
List<Node> result = new List<Node>(); | |
//very fast ops | |
queue.Enqueue(root); | |
while (queue.Count > 0) | |
{ | |
//very fast ops | |
var node = queue.Dequeue(); | |
result.Add(node); | |
foreach (var child in node.Children) | |
{ | |
queue.Enqueue(child); | |
} | |
} | |
return result; | |
} | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment