AvlDictionary Documentation

AvlDictionary<TKey,TValue> is an open source C# Avl-Tree based generic IDictionary<TKey,TValue> implementation. In order to use AvlDictionary<TKey,TValue> copy AvlDictionary.cs to your solution and use the AVL-Tree based generic AvlDictionary<TKey,TValue> like you use the hash based generic Dictionary<TKey,TValue>.

License:

 AvlDictionary.cs - 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: https://www.mission-base.com/.

---

Comparing the Performance of AvlDictionary to Built-In .NET Dictionaries

I ran some tests comparing the time and memory performance of AvlDictionary<TKey,TValue> to the performance of the built-in .NET IDictionary<TKey,TValue> implementations Dictionary<TKey,TValue>, SortedDictionary<TKey,TValue> and SortedList<TKey,TValue>

For the tests I prepared an array of 100000 key-value pairs of type string. The keys were the strings 'k0', 'k1', ... 'k99999' and the values the strings 'v0', 'v1', ... 'v99999'. I used the array for different tests in random, sorted and reversed order.

---

Additional memory needed for adding 100000 key-value pairs in random order via Add (KeyValuePair<TKey,TValue> item)

AvlDirectory needs slightly more than Dictionary and SortedDictionary, SortedList needs less memory.

---

Adding 100000 key-value pairs in random order via Add (KeyValuePair<TKey,TValue> item)

AvlDirectory is slightly better than SortedDictionary, SortedList really needs a long time.

---

Adding 100000 key-value pairs in sorted order via Add (KeyValuePair<TKey,TValue> item)

AvlDirectory is slightly better than SortedDictionary and on par with SortedList.

---

Adding 100000 key-value pairs in reversed order via Add (KeyValuePair<TKey,TValue> item)

AvlDirectory is significantly better than SortedDictionary, SortedList really needs a long time.

---

Adding 100000 key-value pairs in random order via this [TKey key] [get, set]

AvlDirectory is significantly better than SortedDictionary, SortedList really needs a long time.

---

Removing 100000 key-value pairs in random order

AvlDirectory is slightly better than SortedDictionary, SortedList really needs a long time.

---

Removing 100000 key-value pairs in reverse sorted order

AvlDirectory is better than SortedDictionary and slightly better than SortedList.

---

Looking up 100000 keys random order

AvlDirectory is better than SortedDictionary and slightly worse than SortedList.

---

Looking up 1000 values in random order

For this O(N) operation AvlDirectory is better than SortedDictionary and worse than SortedList.

---

The tests were created by using Program.cs, the raw test output looks like TestResult.txt.

Conclusion: I do not understand what the .NET built in type SortedList list is good for at all and I would prefer AvlDirectory over the built in type SortedDictionary. However the built in type Dictionary is either awesome or it cheats with the test outputs :-).