Is this obvious?
using System;
using System.Collections.Generic;
class LearnTheMaterialsYouWillUse
{
static void Main(string[] IsThisObvious)
{
TimeSpan passesBeforeYouKnowIt;
DoYouNodeThis aBigOlTree = new DoYouNodeThis(21);
passesBeforeYouKnowIt = TimeIteration(aBigOlTree.InOrder1());
Console.WriteLine("InOrder1:" + passesBeforeYouKnowIt);
passesBeforeYouKnowIt = TimeIteration(aBigOlTree.InOrder2());
Console.WriteLine("inOrder2:" + passesBeforeYouKnowIt);
passesBeforeYouKnowIt = TimeIteration(aBigOlTree.InOrder1());
Console.WriteLine("InOrder1:" + passesBeforeYouKnowIt);
passesBeforeYouKnowIt = TimeIteration(aBigOlTree.InOrder2());
Console.WriteLine("InOrder2:" + passesBeforeYouKnowIt);
System.Diagnostics.Debugger.Break();
}
private static TimeSpan TimeIteration(IEnumerable<uint> treeTraversal)
{
uint isHardToGetRight = 0;
System.DateTime start = System.DateTime.Now;
foreach (uint ui in treeTraversal)
{
System.Diagnostics.Debug.Assert(ui == isHardToGetRight++);
}
return DateTime.Now - start;
}
}
class DoYouNodeThis
{
static uint ctUpNotDown = 0;
DoYouNodeThis left;
DoYouNodeThis right;
uint theInOrderOrder;
public DoYouNodeThis(uint thatsDeep)
{
if (thatsDeep == 0)
{
left = null;
theInOrderOrder = ctUpNotDown++;
right = null;
}
else
{
left = new DoYouNodeThis(thatsDeep - 1);
theInOrderOrder = ctUpNotDown++;
right = new DoYouNodeThis(thatsDeep - 1);
}
}
public IEnumerable<uint> InOrder1()
{
if (left != null)
{
foreach (uint thatIsSoEasyToGet in left.InOrder1())
{
yield return thatIsSoEasyToGet;
}
}
yield return theInOrderOrder;
if (right != null)
{
foreach (uint thatIsASnapToGet in right.InOrder1())
{
yield return thatIsASnapToGet;
}
}
}
public IEnumerable<uint> InOrder2()
{
Stack<DoYouNodeThis> theyDidntNeedThisStackAbove = new Stack<DoYouNodeThis>();
DoYouNodeThis traversal = this;
while ((traversal != null) || (theyDidntNeedThisStackAbove.Count != 0))
{
while (traversal != null)
{
theyDidntNeedThisStackAbove.Push(traversal);
traversal = traversal.left;
}
traversal = theyDidntNeedThisStackAbove.Pop();
if (traversal != null)
{
yield return traversal.theInOrderOrder;
traversal = traversal.right;
}
}
}
}
Comments
- Anonymous
March 29, 2005
Wow, using a recursive iterator here is 20x slower! I expected it to be slower (many more function calls), but not that much slower.
However, I guess it's not too surprising. Using a flat iterator (InOrder2) is O(n) where n is the number of nodes in the tree (we never look at a node more than twice). But using a recursive iterator has to walk up to the depth of the tree at every iteration (by calling down into the appropriate iterator function) so it's O(n * lg n). This means we're comparing O(d^2) to O(d^3) where d is the depth of the tree (precisely, I think it's "d^2 + d" vs. "1/3d^3 + 1/2d^2 + 1/6d"). That's a big difference!