Guest User

Traversal: Iteration vs. Recursion

a guest
Sep 17th, 2013
141
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. using System;
  2. using System.Collections.Generic;
  3. using System.Diagnostics;
  4.  
  5. static class Test
  6. {
  7.     private static void Main()
  8.     {
  9.         var root = new QuadNode();
  10.         root.Split(10); // 1398074 nodes
  11.         root.LinkNodes();
  12.  
  13.         var stopwatch = new Stopwatch();
  14.         const int iterations = 100;
  15.  
  16.         stopwatch.Restart();
  17.         for (int i = 0; i < iterations; i++)
  18.         {
  19.             root.TraverseRecursivly(a => { });
  20.         }
  21.         stopwatch.Stop();
  22.         Console.WriteLine("TraverseRecursivly elapsed time: {0}ms", stopwatch.ElapsedMilliseconds);
  23.  
  24.         stopwatch.Restart();
  25.         for (int i = 0; i < iterations; i++)
  26.         {
  27.             root.TraverseIteratively(a => { });
  28.         }
  29.         stopwatch.Stop();
  30.         Console.WriteLine("TraverseIteratively elapsed time: {0}ms", stopwatch.ElapsedMilliseconds);
  31.  
  32.         Console.ReadKey();
  33.     }
  34. }
  35.  
  36. class QuadNode
  37. {
  38.     private QuadNode topLeft;
  39.     private QuadNode topRight;
  40.     private QuadNode bottomRight;
  41.     private QuadNode bottomLeft;
  42.     private QuadNode next;
  43.  
  44.     public void LinkNodes()
  45.     {
  46.         var queue = new Queue<QuadNode>();
  47.         queue.Enqueue(this);
  48.         QuadNode last = null;
  49.         while (queue.Count > 0)
  50.         {
  51.             var node = queue.Dequeue();
  52.             if (last != null)
  53.                 last.next = node;
  54.  
  55.             if (node.topLeft != null)
  56.                 queue.Enqueue(node.topLeft);
  57.             if (node.topRight != null)
  58.                 queue.Enqueue(node.topRight);
  59.             if (node.bottomRight != null)
  60.                 queue.Enqueue(node.bottomRight);
  61.             if (node.bottomLeft != null)
  62.                 queue.Enqueue(node.bottomLeft);
  63.  
  64.             last = node;
  65.         }
  66.     }
  67.  
  68.     public void Split(int depth)
  69.     {
  70.         if (depth <= 0)
  71.             return;
  72.  
  73.         topLeft = new QuadNode();
  74.         topRight = new QuadNode();
  75.         bottomRight = new QuadNode();
  76.         bottomLeft = new QuadNode();
  77.  
  78.         depth--;
  79.         topLeft.Split(depth);
  80.         topRight.Split(depth);
  81.         bottomRight.Split(depth);
  82.         bottomLeft.Split(depth);
  83.     }
  84.  
  85.     public void TraverseRecursivly(Action<QuadNode> action)
  86.     {
  87.         action(this);
  88.  
  89.         if (topLeft != null)
  90.             topLeft.TraverseRecursivly(action);
  91.         if (topRight != null)
  92.             topRight.TraverseRecursivly(action);
  93.         if (bottomRight != null)
  94.             bottomRight.TraverseRecursivly(action);
  95.         if (bottomLeft != null)
  96.             bottomLeft.TraverseRecursivly(action);
  97.     }
  98.  
  99.     public void TraverseIteratively(Action<QuadNode> action)
  100.     {
  101.         QuadNode node = this;
  102.         while (node != null)
  103.         {
  104.             action(node);
  105.             node = node.next;
  106.         }
  107.     }
  108. }
RAW Paste Data