Skip to content

Instantly share code, notes, and snippets.

@ionuttamas
Created November 20, 2015 22:40
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save ionuttamas/25cae27ed0d5fb780b2c to your computer and use it in GitHub Desktop.
Save ionuttamas/25cae27ed0d5fb780b2c to your computer and use it in GitHub Desktop.
Ref vs Queue for tree traversal
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