From 554fd8c5195424bdbcabf5de30fdc183aba391bd Mon Sep 17 00:00:00 2001 From: upstream source tree Date: Sun, 15 Mar 2015 20:14:05 -0400 Subject: obtained gcc-4.6.4.tar.bz2 from upstream website; verified gcc-4.6.4.tar.bz2.sig; imported gcc-4.6.4 source tree from verified upstream tarball. downloading a git-generated archive based on the 'upstream' tag should provide you with a source tree that is binary identical to the one extracted from the above tarball. if you have obtained the source via the command 'git clone', however, do note that line-endings of files in your working directory might differ from line-endings of the respective files in the upstream repository. --- .../pb_ds/tree_order_statistics_timing_test.html | 118 +++++++++++++++++++++ 1 file changed, 118 insertions(+) create mode 100644 libstdc++-v3/doc/html/ext/pb_ds/tree_order_statistics_timing_test.html (limited to 'libstdc++-v3/doc/html/ext/pb_ds/tree_order_statistics_timing_test.html') diff --git a/libstdc++-v3/doc/html/ext/pb_ds/tree_order_statistics_timing_test.html b/libstdc++-v3/doc/html/ext/pb_ds/tree_order_statistics_timing_test.html new file mode 100644 index 000000000..ef811613e --- /dev/null +++ b/libstdc++-v3/doc/html/ext/pb_ds/tree_order_statistics_timing_test.html @@ -0,0 +1,118 @@ + + + + + +Tree Order Statistics Timing Test + + + +
+

Tree Order-Statistics Timing Test

+

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 of + tree_order_statistics_node_update + ; otherwise, it uses the find method and + std::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. (see + Design::Associative + Containers::Tree-Based Containers::Node Invariants .)

+

Results

+

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

+
+
+
+
+
no image
NTG: Native and tree-based container order-statistics queries - g++

In the above figure, the names in the legends have the following meaning:

+
    +
  1. +n_set- +std::set
    2. +
  2. +splay_tree_ost_set- +tree + with Tag = splay_tree_tag +, and Node_Update = tree_order_statistics_node_update +
    3. +
  3. +rb_tree_ost_set- +tree + with Tag = rb_tree_tag +, and Node_Update = tree_order_statistics_node_update +
    4. +
+
+
+
+
+
+
+
+
+
+
no image
NTM: Native and tree-based container order-statistics queries - msvc++

In the above figure, the names in the legends have the following meaning:

+
    +
  1. +n_set- +std::set
    2. +
  2. +splay_tree_ost_set- +tree + with Tag = splay_tree_tag +, and Node_Update = tree_order_statistics_node_update +
    3. +
  3. +rb_tree_ost_set- +tree + with Tag = rb_tree_tag +, and Node_Update = tree_order_statistics_node_update +
    4. +
+
+
+
+
+
+
+
+
+
+
no image
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 a + find (alternatively, lower_bound or + upper_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 the + order_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.

+
+ + -- cgit v1.2.3