Insert-Sort Performance¶
The tests measure the performance of sets and dicts with integer keys. The following implementation are compared:
- banyan_red_black_tree - banyan.SortedSet or banyan.SortedDict with key_type = int or key_type = str and alg = banyan.RED_BLACK_TREE
- banyan_splay_tree - banyan.SortedSet or banyan.SortedDict with key_type = int or key_type = str and alg = banyan.SPLAY_TREE
- banyan_sorted_list - banyan.SortedSet or banyan.SortedDict with key_type = int or key_type = str and alg = banyan.SORTEDLISt
- banyan_red_black_tree_gen - banyan.SortedSet or banyan.SortedDict without key-type specification and alg = banyan.RED_BLACK_TREE
- banyan_splay_tree_gen - banyan.SortedSet or banyan.SortedDict without key-type specification and alg = banyan.SPLAY_TREE
- banyan_sorted_list_gen - banyan.SortedSet or banyan.SortedDict without key-type specification alg = banyan.SORTEDLISt
- bintrees - A bintrees.FastRBTree (V 1.0.1) red-black tree.
- blist - A blist.sortedset (V 1.3.4) BTree
- btrees - A BTrees.OOBTree (V 4.0.5) BTree
- bx - A bx (V 0.7.1) tree
- dict - Python’s (hash-based) dict
- set - Python’s (hash-based) set
Integer Sets¶
The following figures show the running time of inserting integers one by one into a set and iterating in sorted order after every insertion, as a function of the number of integers (see _set_insert_sort.py for the source).
The following figure shows the performance of all the implementations:
The following figure shows the performance of all implementations with similar performance:
As the number of items increases, the cost of sorting incurred by the hash-based implementation grows. This is shown in the following figure, where larger numbers of items were used:
String Sets¶
The following figures show the running time of inserting strings one by one into a set and iterating in sorted order after every insertion, as a function of the number of integers (see _set_insert_sort.py for the source).
The following figure shows the performance of all the implementations:
The following figure shows the performance of all implementations with similar performance:
As the number of items increases, the cost of sorting incurred by the hash-based implementation grows. This is shown in the following figure, where larger numbers of items were used:
Integer Dicts¶
The following figures show the running time of inserting integers one by one into a dict and iterating in sorted order after every insertion, as a function of the number of integers (see _set_insert_sort.py for the source).
The following figure shows the performance of all the implementations:
The following figure shows the performance of all implementations with similar performance:
As the number of items increases, the cost of sorting incurred by the hash-based implementation grows. This is shown in the following figure, where larger numbers of items were used:
String Dicts¶
The following figures show the running time of inserting strings one by one into a dict and iterating in sorted order after every insertion, as a function of the number of integers (see _set_insert_sort.py for the source).
The following figure shows the performance of all the implementations:
The following figure shows the performance of all implementations with similar performance:
As the number of items increases, the cost of sorting incurred by the hash-based implementation grows. This is shown in the following figure, where larger numbers of items were used:
