February 8, 2010 at 3:30 pm
· Filed under .NET, C#
When dealing with tree structures, it’s helpful to be able to visit all nodes. Here’s an extension method that makes traversing tree structures easier (in this case, in preorder, depth-first).
internal static class TreeTraverse
{
public static IEnumerable<T> PreorderTraverse<T>(this T node, Func<T, IEnumerable<T>> childrenFor)
{
yield return node;
var childNodes = childrenFor(node);
if (childNodes != null)
{
foreach (var childNode in childNodes.SelectMany(n => n.PreorderTraverse(childrenFor)))
{
yield return childNode;
}
}
}
}
This extension method allows you to treat any type as the root node of a tree, providing you can define a sensible childrenFor method for it.
Example usage:
var root = new Node
{
Name = "root",
Children = new List<Node>()
{
new Node
{
Name = "root > child A",
Children = new List<Node>()
{
new Node
{
Name = "root > child A > child AA"
}
}
},
new Node
{
Name = "root > child B"
}
}
};
foreach (var node in root.PreorderTraverse(n => n.Children))
{
Console.WriteLine(node.Name);
}
Where Node is defined as:
class Node
{
public string Name { get; set; }
public IEnumerable<Node> Children { get; set; }
}
To use PreorderTraverse on an IEnumerable<T> you can combine with SelectMany, as in fact the PreorderTraverse extension method does.
Permalink
February 3, 2010 at 4:00 am
· Filed under .NET, C#
More specifically, lambda expressions… Let’s say you have a method, the body of which will execute based on the value of a flag (myFlag in the example here):
public void MyConditionalMethod(string format, params object[] args)
{
if (myFlag)
{
DoSomething(string.Format(format, args));
}
}
Ideally, in scenarios where myFlag is false we’d like a call to this method, such as the following, to have limited overhead:
MyConditionalMethod("{0}, {1}", param0, param1);
If param0 and/or param1 are value-types, this call will incur the overhead of boxing regardless of the value of myFlag. Obviously, things get worse as we pass more value-types as parameters.
One approach to addressing this problem is through the use of lambda expressions; the lambda expression is only executed if the flag is set. Here’s a version of MyConditionalMethod modified accordingly:
public void MyConditionalMethod(Func<string> getString)
{
if (myFlag)
{
DoSomething(getString());
}
}
A call to the modified method looks like this:
MyConditionalMethod(() => string.Format("{0}, {1}", param0, param1));
Here are some rough performance numbers (with compiler optimizations on) to illustrate the potential advantages of this approach:
|
Min (ns) |
Max (ns) |
Median (ns) |
Standard (1000 iterations, 10 samples) |
74.396 |
434.688 |
147.888 |
with lambda (1000 iterations, 10 samples) |
5.692 |
11.687 |
5.692 |
This technique can be used in tracing or other scenarios where these methods may be called frequently throughout your code and it can have a significant performance benefit in the aggregate.
Permalink