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: http://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 :-).