Dictionary Performance Measurements
To rate the performance of the different dictionaries, a small experiment was performed to obtain the time for the following measurements:
- time taken for n insert operations
- time taken for n delete operations
- time taken for n delete-min operations The experiment was performed as follows:
- n items were created and assigned random keys.
- An array pointers to the n items is set up as items were created. This array specifies the same insertion order when timing each dictionary.
- A second array, a2, is set up to point to the same n items, but in a different order. This array specifies the same deletion order when timing each dictionary.
- For each dictionary:
- insert n items in the order specified by a1, and record the time taken.
- delete n items in the order specified by array a2, and record the time taken.
- insert n items in the order specified by a1.
- perform n delete-min operations, and record the time taken.
bst
avl 23
RB
dst rst
find 1.97
1.69
1.87 1.68 0.95
1.09
insert 2.31 2.17
1.95
2.12 1.18 1.45
delete 2.29 2.22
2.15
2.27 1.40 1.57
del-min 0.45 0.53
0.47
0.54 0.82 0.81
BST = binary search tree
AVL = AVL tree
23 = 2-3 tree
RB = red-black tree
DST = digital search tree
The digital search tree is fast but can only store items based upon positive integer keys. For the digital search tree the keys of items are determined using a get_value() function supplied by the user when the dictionary is created. This returns a positive integer that represents the key value of the item. Since an integer key can be determined, nodes in the tree have an integer key field as well as a pointer to the item, which allows future accesses to a nodes key without having to call get_value(). In contrast, the other dictionaries use a compare() function, which compares the value of two items. This is more flexible since an items value is no longer limited to integer keys; for example a string field in the item may represent its value. In this sort of implementation, compare() must be called each time the dictionary needs to compare value of two items. This is slower than accessing an items key directly through integer field in the node, so there is a speed tradeoff for the improved flexibility.
In this above experiment, the items that were inserted into the dictionary had two integer fields - the first filed, data1, was used as the items key, and the second field, data2, held information not used by the dictionary. The get_value() function used by the digital search tree returned the value of an items data1 field, and the compare() function used by the other dictionaries compared the value of two items data1 field.
