/* Program.cs - For testing the C# implementation of an AVL tree based generic IDictionary interface. Copyright (C) 2009 Peter Graf This file is part of PBL - The Program Base Library. PBL is free software. This library is free software; you can redistribute it and/or modify it under the terms of the GNU Lesser General Public License as published by the Free Software Foundation; either version 2.1 of the License, or (at your option) any later version. This library is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public License for more details. You should have received a copy of the GNU Lesser General Public License along with this library; if not, write to the Free Software Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA For more information on the Program Base Library or Peter Graf, please see: http://www.mission-base.com/. $Log: Program.cs,v $ Revision 1.2 2009/11/26 19:01:53 peter Added header */ using System; using System.Collections.Generic; using System.Linq; using System.Text; using System.Runtime.Serialization.Formatters.Binary; using System.IO; using System.Xml.Serialization; namespace Com.Mission_Base.Pbl { /// /// A simple test program fór an AvlDictionary<TKey,TValue>. /// class Program { static void BasicTest(string[] args) { AvlDictionary d = new AvlDictionary(); d.CopyTo(new KeyValuePair[1], 0); d.CopyTo(new Array[1], 0); d.Add("0", "0"); d.Add("1", "1"); d.Add("2", "2"); d.Add("3", "3"); d.Add("4", "4"); d.Add("5", "5"); d.Add("6", "6"); d.Add("7", "7"); if (d.ContainsKey("a")) { d.Remove("a"); } if (d.Contains(new KeyValuePair("", ""))) { d.Add(new KeyValuePair("", "")); d.Remove(new KeyValuePair("", "")); } KeyValuePair pair = new KeyValuePair("", ""); d["0"] = "00"; d["a"] = "a"; d.Remove("0"); d.Remove("a"); if (d.Count <= 0) { d.Remove("a"); d.Clear(); } foreach (string key in d.Keys) { if (d.ContainsKey(key)) { continue; } string v = d[key]; } for (IEnumerator en = d.Keys.GetEnumerator(); en.MoveNext(); ) { string key = en.Current; string v = d[key]; } for (IEnumerator en = d.Values.GetEnumerator(); en.MoveNext(); ) { string v = en.Current; if (!d.Values.Contains(v)) { break; } } for (IEnumerator> en = d.GetEnumerator(); en.MoveNext(); ) { string key = en.Current.Key; string v = en.Current.Value; if (!v.Equals(d[key])) { break; } } Dictionary dict = new Dictionary(); dict.Add("0", "0"); dict.Add("1", "1"); dict.Add("2", "2"); dict.Add("3", "3"); dict.Add("4", "4"); dict.Add("5", "5"); dict.Add("6", "6"); dict.Add("7", "7"); if (dict.Keys.Count <= 0) { dict.Remove("a"); dict.Clear(); } AvlDictionary d2 = new AvlDictionary(dict); foreach (string key in d2.Keys.Reverse()) { string v = d2[key]; if (d2.Values.Contains(v)) { d2.Remove(key); } } BinaryFormatter bf = new BinaryFormatter(); FileStream fs = new FileStream("c:\\output.bin", FileMode.Create); bf.Serialize(fs, d); fs.Close(); FileStream input = new FileStream("c:\\output.bin", FileMode.Open); AvlDictionary d3 = (AvlDictionary)bf.Deserialize(input); input.Close(); } static KeyValuePair[] shuffle(KeyValuePair[] data) { Random r = new Random(data.Length); for( int i = 0; i < data.Length; i++ ) { int other = r.Next(data.Length); KeyValuePair tmp = data[i]; data[i] = data[other]; data[other] = tmp; } return data; } static ICollection> AddPairTest(string tag, ICollection> collection, KeyValuePair[] data) { System.GC.Collect(); long startMemory = System.GC.GetTotalMemory(true); DateTime start = DateTime.Now; for (int i = 0; i < data.Length; i++) { collection.Add(data[i]); } DateTime end = DateTime.Now; System.GC.Collect(); long endMemory = System.GC.GetTotalMemory(true); if (!string.IsNullOrEmpty(tag)) { Console.WriteLine(string.Format("{1}: added {0} pairs in {2} ms, memory change {3} bytes", collection.Count, tag, (end.Ticks - start.Ticks) / 10000, endMemory - startMemory)); } return collection; } static ICollection> AddKeyValueTest(string tag, IDictionary dictionary, KeyValuePair[] data) { System.GC.Collect(); long startMemory = System.GC.GetTotalMemory(true); DateTime start = DateTime.Now; for (int i = 0; i < data.Length; i++) { dictionary.Add(data[i].Key, data[i].Value); } DateTime end = DateTime.Now; System.GC.Collect(); long endMemory = System.GC.GetTotalMemory(true); Console.WriteLine(string.Format("{1}: added {0} key-values in {2} ms, memory change {3} bytes", dictionary.Count, tag, (end.Ticks - start.Ticks) / 10000, endMemory - startMemory)); return dictionary; } static ICollection> ContainsKeyTest(string tag, IDictionary dictionary, KeyValuePair[] data) { System.GC.Collect(); long startMemory = System.GC.GetTotalMemory(true); DateTime start = DateTime.Now; int i = 0; for (; i < data.Length; i++) { if (!dictionary.ContainsKey(data[i].Key)) { break; } } DateTime end = DateTime.Now; System.GC.Collect(); long endMemory = System.GC.GetTotalMemory(true); Console.WriteLine(string.Format("{1}: found {0} keys in {2} ms, memory change {3} bytes", i, tag, (end.Ticks - start.Ticks) / 10000, endMemory - startMemory)); return dictionary; } static ICollection> ContainsPairTest(string tag, IDictionary dictionary, KeyValuePair[] data) { System.GC.Collect(); long startMemory = System.GC.GetTotalMemory(true); DateTime start = DateTime.Now; int i = 0; for (; i < data.Length; i++) { if (!dictionary.Contains(data[i])) { break; } } DateTime end = DateTime.Now; System.GC.Collect(); long endMemory = System.GC.GetTotalMemory(true); Console.WriteLine(string.Format("{1}: found {0} pairs in {2} ms, memory change {3} bytes", i, tag, (end.Ticks - start.Ticks) / 10000, endMemory - startMemory)); return dictionary; } static ICollection> ContainsValueTest(string tag, IDictionary dictionary, KeyValuePair[] data) { System.GC.Collect(); long startMemory = System.GC.GetTotalMemory(true); DateTime start = DateTime.Now; int i = 0; for (; i < data.Length; i++) { if (!dictionary.Values.Contains(data[(i * data.Length / 1000) % data.Length].Value)) { break; } if( i >= 1000 ) { break; } } DateTime end = DateTime.Now; System.GC.Collect(); long endMemory = System.GC.GetTotalMemory(true); Console.WriteLine(string.Format("{1}: found {0} values in {2} ms, memory change {3} bytes", i, tag, (end.Ticks - start.Ticks) / 10000, endMemory - startMemory)); return dictionary; } static ICollection> AddIndexedKeyValueTest(string tag, IDictionary dictionary, KeyValuePair[] data) { System.GC.Collect(); long startMemory = System.GC.GetTotalMemory(true); DateTime start = DateTime.Now; for (int i = 0; i < data.Length; i++) { dictionary[data[i].Key] = data[i].Value; } DateTime end = DateTime.Now; System.GC.Collect(); long endMemory = System.GC.GetTotalMemory(true); Console.WriteLine(string.Format("{1}: added {0} items via 'd[key] = value' in {2} ms, memory change {3} bytes", dictionary.Count, tag, (end.Ticks - start.Ticks) / 10000, endMemory - startMemory)); return dictionary; } static ICollection> RemoveKeyTest(string tag, IDictionary dictionary, KeyValuePair[] data) { int count = dictionary.Count; System.GC.Collect(); long startMemory = System.GC.GetTotalMemory(true); DateTime start = DateTime.Now; for (int i = 0; i < data.Length; i++) { dictionary.Remove(data[i].Key); } DateTime end = DateTime.Now; System.GC.Collect(); long endMemory = System.GC.GetTotalMemory(true); Console.WriteLine(string.Format("{1}: removed {0} items in {2} ms, memory change {3} bytes", count - dictionary.Count, tag, (end.Ticks - start.Ticks) / 10000, endMemory - startMemory)); return dictionary; } static ICollection> UpdateIndexedKeyValueTest(string tag, IDictionary dictionary, KeyValuePair[] data) { System.GC.Collect(); long startMemory = System.GC.GetTotalMemory(true); DateTime start = DateTime.Now; for (int i = 0; i < data.Length; i++) { dictionary[data[i].Key] = data[i].Value; } DateTime end = DateTime.Now; System.GC.Collect(); long endMemory = System.GC.GetTotalMemory(true); Console.WriteLine(string.Format("{1}: updated {0} items via 'd[key] = value' in {2} ms, memory change {3} bytes", data.Length, tag, (end.Ticks - start.Ticks) / 10000, endMemory - startMemory)); return dictionary; } static void SpeedTest(string[] args) { Console.WriteLine("Starting SpeedTest setup"); System.GC.Collect(); long startMemory = System.GC.GetTotalMemory(true); DateTime start = DateTime.Now; KeyValuePair[] data = new KeyValuePair[100000]; for (int i = 0; i < data.Length; i++) { string s = i.ToString(); data[i] = new KeyValuePair("k" + s, "v" + s); } data = shuffle(data); DateTime end = DateTime.Now; System.GC.Collect(); long endMemory = System.GC.GetTotalMemory(true); Console.WriteLine(string.Format("Setup of {0} items done in {1} ms, memory change {2} bytes", data.Length, (end.Ticks - start.Ticks) / 10000, endMemory - startMemory)); Console.WriteLine(""); AvlDictionary avlDictionary = (AvlDictionary)AddPairTest("AvlDictionary (random input)", new AvlDictionary(), data); KeyValuePair[] sortedData = avlDictionary.ToArray(); KeyValuePair[] reversedData = avlDictionary.Reverse().ToArray(); Dictionary dictionary = (Dictionary)AddPairTest("Dictionary (random input)", new Dictionary(), data); SortedDictionary sortedDictionary = (SortedDictionary)AddPairTest("SortedDictionary (random input)", new SortedDictionary(), data); SortedList sortedList = (SortedList)AddPairTest("SortedList (random input)", new SortedList(), data); Console.WriteLine(""); avlDictionary = (AvlDictionary)AddPairTest("AvlDictionary (sorted input)", new AvlDictionary(), sortedData); dictionary = (Dictionary)AddPairTest("Dictionary (sorted input)", new Dictionary(), sortedData); sortedDictionary = (SortedDictionary)AddPairTest("SortedDictionary (sorted input)", new SortedDictionary(), sortedData); sortedList = (SortedList)AddPairTest("SortedList (sorted input)", new SortedList(), sortedData); Console.WriteLine(""); avlDictionary = (AvlDictionary)AddPairTest("AvlDictionary (reverse sorted input)", new AvlDictionary(), reversedData); dictionary = (Dictionary)AddPairTest("Dictionary (reverse sorted input)", new Dictionary(), reversedData); sortedDictionary = (SortedDictionary)AddPairTest("SortedDictionary (reverse sorted input)", new SortedDictionary(), reversedData); sortedList = (SortedList)AddPairTest("SortedList (reverse sorted input)", new SortedList(), reversedData); Console.WriteLine(""); avlDictionary = (AvlDictionary)AddIndexedKeyValueTest("AvlDictionary (random input)", new AvlDictionary(), data); dictionary = (Dictionary)AddIndexedKeyValueTest("Dictionary (random input)", new Dictionary(), data); sortedDictionary = (SortedDictionary)AddIndexedKeyValueTest("SortedDictionary (random input)", new SortedDictionary(), data); sortedList = (SortedList)AddIndexedKeyValueTest("SortedList (random input)", new SortedList(), data); Console.WriteLine(""); avlDictionary = (AvlDictionary)AddIndexedKeyValueTest("AvlDictionary (sorted input)", new AvlDictionary(), sortedData); dictionary = (Dictionary)AddIndexedKeyValueTest("Dictionary (sorted input)", new Dictionary(), sortedData); sortedDictionary = (SortedDictionary)AddIndexedKeyValueTest("SortedDictionary (sorted input)", new SortedDictionary(), sortedData); sortedList = (SortedList)AddIndexedKeyValueTest("SortedList (sorted input)", new SortedList(), sortedData); Console.WriteLine(""); avlDictionary = (AvlDictionary)UpdateIndexedKeyValueTest("AvlDictionary (random input)", avlDictionary, data); dictionary = (Dictionary)UpdateIndexedKeyValueTest("Dictionary (random input)", dictionary, data); sortedDictionary = (SortedDictionary)UpdateIndexedKeyValueTest("SortedDictionary (random input)", sortedDictionary, data); sortedList = (SortedList)UpdateIndexedKeyValueTest("SortedList (random input)", sortedList, data); Console.WriteLine(""); avlDictionary = (AvlDictionary)UpdateIndexedKeyValueTest("AvlDictionary (sorted input)", avlDictionary, sortedData); dictionary = (Dictionary)UpdateIndexedKeyValueTest("Dictionary (sorted input)", dictionary, sortedData); sortedDictionary = (SortedDictionary)UpdateIndexedKeyValueTest("SortedDictionary (sorted input)", sortedDictionary, sortedData); sortedList = (SortedList)UpdateIndexedKeyValueTest("SortedList (sorted input)", sortedList, sortedData); Console.WriteLine(""); avlDictionary = (AvlDictionary)AddKeyValueTest("AvlDictionary (random input)", new AvlDictionary(), data); dictionary = (Dictionary)AddKeyValueTest("Dictionary (random input)", new Dictionary(), data); sortedDictionary = (SortedDictionary)AddKeyValueTest("SortedDictionary (random input)", new SortedDictionary(), data); sortedList = (SortedList)AddKeyValueTest("SortedList (random input)", new SortedList(), data); Console.WriteLine(""); avlDictionary = (AvlDictionary)AddKeyValueTest("AvlDictionary (sorted input)", new AvlDictionary(), sortedData); dictionary = (Dictionary)AddKeyValueTest("Dictionary (sorted input)", new Dictionary(), sortedData); sortedDictionary = (SortedDictionary)AddKeyValueTest("SortedDictionary (sorted input)", new SortedDictionary(), sortedData); sortedList = (SortedList)AddKeyValueTest("SortedList (sorted input)", new SortedList(), sortedData); Console.WriteLine(""); avlDictionary = (AvlDictionary)AddPairTest("", new AvlDictionary(), sortedData); avlDictionary = (AvlDictionary)RemoveKeyTest("AvlDictionary (random input)", avlDictionary, data); dictionary = (Dictionary)AddPairTest("", new Dictionary(), sortedData); dictionary = (Dictionary)RemoveKeyTest("Dictionary (random input)", dictionary, data); sortedDictionary = (SortedDictionary)AddPairTest("", new SortedDictionary(), sortedData); sortedDictionary = (SortedDictionary)RemoveKeyTest("SortedDictionary (random input)", sortedDictionary, data); sortedList = (SortedList)AddPairTest("", new SortedList(), sortedData); sortedList = (SortedList)RemoveKeyTest("SortedList (random input)", sortedList, data); Console.WriteLine(""); avlDictionary = (AvlDictionary)AddPairTest("", new AvlDictionary(), data); avlDictionary = (AvlDictionary)RemoveKeyTest("AvlDictionary (sorted input)", avlDictionary, sortedData); dictionary = (Dictionary)AddPairTest("", new Dictionary(), sortedData); dictionary = (Dictionary)RemoveKeyTest("Dictionary (sorted input)", dictionary, sortedData); sortedDictionary = (SortedDictionary)AddPairTest("", new SortedDictionary(), sortedData); sortedDictionary = (SortedDictionary)RemoveKeyTest("SortedDictionary (sorted input)", sortedDictionary, sortedData); sortedList = (SortedList)AddPairTest("", new SortedList(), sortedData); sortedList = (SortedList)RemoveKeyTest("SortedList (sorted input)", sortedList, sortedData); Console.WriteLine(""); avlDictionary = (AvlDictionary)AddPairTest("", new AvlDictionary(), data); avlDictionary = (AvlDictionary)RemoveKeyTest("AvlDictionary (reverse sorted input)", avlDictionary, reversedData); dictionary = (Dictionary)AddPairTest("", new Dictionary(), sortedData); dictionary = (Dictionary)RemoveKeyTest("Dictionary (reverse sorted input", dictionary, reversedData); sortedDictionary = (SortedDictionary)AddPairTest("", new SortedDictionary(), sortedData); sortedDictionary = (SortedDictionary)RemoveKeyTest("SortedDictionary (reverse sorted input)", sortedDictionary, reversedData); sortedList = (SortedList)AddPairTest("", new SortedList(), sortedData); sortedList = (SortedList)RemoveKeyTest("SortedList (reverse sorted input)", sortedList, reversedData); Console.WriteLine(""); avlDictionary = (AvlDictionary)AddPairTest("", new AvlDictionary(), sortedData); avlDictionary = (AvlDictionary)ContainsKeyTest("AvlDictionary (random input)", avlDictionary, data); dictionary = (Dictionary)AddPairTest("", new Dictionary(), sortedData); dictionary = (Dictionary)ContainsKeyTest("Dictionary (random input)", dictionary, data); sortedDictionary = (SortedDictionary)AddPairTest("", new SortedDictionary(), sortedData); sortedDictionary = (SortedDictionary)ContainsKeyTest("SortedDictionary (random input)", sortedDictionary, data); sortedList = (SortedList)AddPairTest("", new SortedList(), sortedData); sortedList = (SortedList)ContainsKeyTest("SortedList (random input)", sortedList, data); Console.WriteLine(""); avlDictionary = (AvlDictionary)ContainsPairTest("AvlDictionary (random input)", avlDictionary, data); dictionary = (Dictionary)ContainsPairTest("Dictionary (random input)", dictionary, data); sortedDictionary = (SortedDictionary)ContainsPairTest("SortedDictionary (random input)", sortedDictionary, data); sortedList = (SortedList)ContainsPairTest("SortedList (random input)", sortedList, data); Console.WriteLine(""); avlDictionary = (AvlDictionary)ContainsValueTest("AvlDictionary (random input)", avlDictionary, data); dictionary = (Dictionary)ContainsValueTest("Dictionary (random input)", dictionary, data); sortedDictionary = (SortedDictionary)ContainsValueTest("SortedDictionary (random input)", sortedDictionary, data); sortedList = (SortedList)ContainsValueTest("SortedList (random input)", sortedList, data); Console.WriteLine(""); } static void Main(string[] args) { SpeedTest(args); } } }