Determining which data structure to use for storing data involves trade-offs between how much memory they require and how long different operations, such as insertions, deletions, or searches take. In C#, using a linear array is the fastest way to enumerate all of the objects in a collection. However, the use of an array or list can have multiple drawbacks. For example, Arrays and lists in C# can have frustrating size limits as objects in the CLR, regardless of system architecture, cannot be over 2 GB in size*. Similarly, while a good data-structure for enumerations, lists and arrays are slower than other alternatives for searching.<\/p>
I recently had a dataset for which the abilities to search, enumerate and hold over 2 GB of data from the collection were desirable. These criteria naturally make a tree like data structure appealing. However, in a high level language like C# where performance can often heavily depend on which run-time optimizations the virtual machine utilizes, determining the actual performance hit incurred by using a tree as compared to a list during an enumeration is more accurately answered with empirical data than Big O notation.<\/p>
So, I tested how enumeration performance varies between a balanced binary tree and a list. <\/strong>Since the tree was being enumerated by using the yield <\/font>statement when a relevant node was found, I compared three methods. One where a class containing a binary tree is enumerated with a yield, one where a class containing a list is enumerated with a yield statement (that is the class enumerates its internal list and yields each element), and one where that same class is enumerated by simply passing out the original List object. In all cases enumerating 220 <\/sup>objects in total. Here is the time comparison.<\/p> .110 seconds<\/font><\/p><\/td><\/tr> List with yield statement<\/font><\/p><\/td> .055 seconds<\/font><\/p><\/td><\/tr> List without yield statement.<\/font><\/p><\/td> .016 seconds<\/font><\/p><\/td><\/tr><\/tbody><\/table> These values do not vary substantially based on the order of operations or repeated trials. So, yowza, an order of magnitude difference in enumerating the objects, which seemed far more severe than I would have imagined (I was expecting about 3X). It appears much of this is due to the method call and overhead of the yield statement. The two methods using the list are logically identical in code, but it seems the compiler can\u2019t quite figure that out, leading to a 5X drop in performance. Out of curiosity, I also compared to a dictionaries enumeration speed which took about twice as long as the fast list method, but which ran out of memory with a higher number of elements pretty readily.<\/p> My take home on this, is to <\/em>only use arrays and lists in C# if the enumeration speed of a collection appears limiting<\/strong>. It appears traversal of trees in the language is very slow, so trees are not generally recommended when the operations per node are fast.<\/p> <\/p> *This may change on newer version of the MS CLR<\/font><\/p> Code Below<\/p>
Method<\/font><\/h3><\/td>
Time<\/font><\/h3><\/td><\/tr>
Balanced binary tree with yield statement<\/font><\/td> using<\/span> System;\r\nusing<\/span> System.Collections.Generic;\r\nusing<\/span> System.Linq;\r\nusing<\/span> System.Text;\r\nusing<\/span> System.Threading.Tasks;\r\nusing<\/span> System.Diagnostics;\r\nusing<\/span> System.Globalization;\r\n\r\nnamespace<\/span> TestTreeVersusList\r\n{\r\n class<\/span> Program\r\n {\r\n public<\/span> static<\/span> int<\/span> TreeDepth = 24;\r\n public<\/span> static<\/span> int<\/span> ElementNumber=(int<\/span>)(Math.Pow(2,TreeDepth));\r\n static<\/span> void<\/span> Main(string<\/span>[] args)\r\n {\r\n Stopwatch sw = new<\/span> Stopwatch();\r\n ulong<\/span> val = 0;\r\n \/\/\/\/now for the list<\/span>\r\n val = 0;\r\n ListEnumerator le = new<\/span> ListEnumerator();\r\n sw.Reset();\r\n sw.Start();\r\n foreach<\/span> (node num in<\/span> le.GetNodes())\r\n {\r\n val += num.value<\/span>;\r\n }\r\n sw.Stop();\r\n Console.WriteLine(\"Time Taken For List with yield: \"<\/span> + sw.Elapsed.TotalSeconds.ToString() + \" seconds\"<\/span>);\r\n\r\n sw.Reset();\r\n sw.Start();\r\n foreach<\/span> (node num in<\/span> le.curList)\r\n {\r\n val += num.value<\/span>;\r\n }\r\n sw.Stop();\r\n Console.WriteLine(\"Time Taken For List without yield: \"<\/span> + sw.Elapsed.TotalSeconds.ToString() + \" seconds\"<\/span>);\r\n le = null<\/span>;\r\n\r\n \/\/create a tree and a list<\/span>\r\n BinaryTreeEnumerator tree = new<\/span> BinaryTreeEnumerator();\r\n sw.Reset();\r\n sw.Start();\r\n val = 0;\r\n foreach<\/span> (node num in<\/span> tree.GetNodes())\r\n {\r\n val += num.value<\/span>;\r\n }\r\n sw.Stop();\r\n Console.WriteLine(\"Time Taken For Tree: \"<\/span> + sw.Elapsed.TotalSeconds.ToString() + \" seconds\"<\/span>);\r\n tree = null<\/span>;\r\n DictionaryEnumerator dict = new<\/span> DictionaryEnumerator();\r\n sw.Reset();\r\n sw.Start();\r\n val = 0;\r\n foreach<\/span> (var kv in<\/span> dict.dict)\/\/.dict)<\/span>\r\n {\r\n val=kv;\r\n \/\/val = kv.Key;<\/span>\r\n }\r\n sw.Stop();\r\n Console.WriteLine(\"Time Taken For Dictionary: \"<\/span> + sw.Elapsed.TotalSeconds.ToString() + \" seconds\"<\/span>);\r\n dict = null<\/span>;\r\n }\r\n }\r\n class<\/span> node\r\n {\r\n public<\/span> ulong<\/span> value<\/span>;\r\n public<\/span> object<\/span> o;\r\n public<\/span> node Left;\r\n public<\/span> node Right;\r\n }\r\n class<\/span> BinaryTreeEnumerator\r\n {\r\n node root;\r\n int<\/span> nodeCount;\r\n public<\/span> IEnumerable<node> GetNodes()\r\n {\r\n Stack<node> traversalStack = new<\/span> Stack<node>(2 * Program.TreeDepth);\r\n traversalStack.Push(this<\/span>.root);\r\n while<\/span> (traversalStack.Count > 0)\r\n {\r\n node current;\r\n current = traversalStack.Pop();\r\n if<\/span> (current != null<\/span>)\r\n {\r\n if<\/span> (current.value<\/span> != 0)\r\n {\r\n traversalStack.Push(current.Right);\r\n traversalStack.Push(current.Left);\r\n }\r\n yield<\/span> return<\/span> current;\r\n }\r\n }\r\n \/\/traversalStack.TrimExcess();<\/span>\r\n }\r\n \/\/Just make a binary tree with a bunch of elements<\/span>\r\n public<\/span> BinaryTreeEnumerator()\r\n {\r\n this<\/span>.root = new<\/span> node() { value<\/span> = 1, o = null<\/span> };\r\n node current;\r\n Queue<node> traversalStack = new<\/span> Queue<node>(2*Program.TreeDepth);\r\n traversalStack.Enqueue(this<\/span>.root);\r\n while<\/span> (traversalStack.Count > 0 && nodeCount < Program.ElementNumber)\r\n { \r\n current = traversalStack.Dequeue();\r\n if<\/span> (current.value<\/span> != 0)\r\n {\r\n current.Left = new<\/span> node() { value<\/span> = 1, o = null<\/span> };\r\n current.Right = new<\/span> node() { value<\/span> = 1, o = null<\/span> };\r\n nodeCount += 2;\r\n traversalStack.Enqueue(current.Right);\r\n traversalStack.Enqueue(current.Left);\r\n }\r\n }\r\n }\r\n }\r\n class<\/span> ListEnumerator\r\n {\r\n public<\/span> List<node> curList;\r\n public<\/span> ListEnumerator()\r\n {\r\n curList = new<\/span> List<node>(Program.ElementNumber);\r\n for<\/span>(int<\/span> i=0;i<Program.ElementNumber;i++)\r\n {\r\n curList.Add(new<\/span> node(){value<\/span>=1,o=null<\/span>});\r\n }\r\n }\r\n public<\/span> IEnumerable<node> GetNodes()\r\n {\r\n foreach<\/span> (node n in<\/span> curList)\r\n {\r\n yield<\/span> return<\/span> n;\r\n }\r\n }\r\n }\r\n class<\/span> DictionaryEnumerator\r\n {\r\n public<\/span> Dictionary<ulong<\/span>,node> dict = new<\/span> Dictionary<ulong<\/span>,node>();\r\n public<\/span> DictionaryEnumerator()\r\n {\r\n for<\/span> (ulong<\/span> i = 0; i < (ulong<\/span>)Program.ElementNumber; i++)\r\n {\r\n dict[i] = new<\/span> node() { value<\/span> = i, o = null<\/span> };\r\n }\r\n }\r\n }\r\n}\r\n<\/pre>\r\n