Tree Order Statistics Timing Test (original) (raw)

Description

This test creates a container, inserts random integers into the the container, and then checks the order-statistics of the container's values. (If the container is one of pb_ds 's trees, it does this with the order_of_key method oftree_order_statistics_node_update ; otherwise, it uses the find method andstd::distance .) It measures the average time for such queries as a function of the number of values inserted.

(The test was executed with tree_order_statistics_timing_test 200 200 2100)

Purpose

The test checks the performance difference of policies based on node-invariant as opposed to a external functions. (seeDesign::Associative Containers::Tree-Based Containers::Node Invariants .)

Results

Figures NTG, NTM, andNTL show the results for the native and tree-based containers in g++, msvc++, andlocal, respectively.

NTL: Native and tree-based container order-statistics queries - local

Observations

In this test, the native red-black tree can support order-statistics queries only externally, by performing afind (alternatively, lower_bound orupper_bound ) and then using std::distance . This is clearly linear, and it is not that surprising that the cost is high.

pb_ds 's tree-based containers use in this test theorder_of_key method of tree_order_statistics_node_update. This method has only linear complexity in the length of the root-node path. Unfortunately, the average path of a splay tree (tree with Tag = splay_tree_tag ) can be higher than logarithmic; the longest path of a red-black tree (tree with Tag = rb_tree_tag ) is logarithmic in the number of elements. Consequently, the splay tree has worse performance than the red-black tree.