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. --- .../priority_queue_text_push_pop_timing_test.html | 209 +++++++++++++++++++++ 1 file changed, 209 insertions(+) create mode 100644 libstdc++-v3/doc/html/ext/pb_ds/priority_queue_text_push_pop_timing_test.html (limited to 'libstdc++-v3/doc/html/ext/pb_ds/priority_queue_text_push_pop_timing_test.html') diff --git a/libstdc++-v3/doc/html/ext/pb_ds/priority_queue_text_push_pop_timing_test.html b/libstdc++-v3/doc/html/ext/pb_ds/priority_queue_text_push_pop_timing_test.html new file mode 100644 index 000000000..3c143fe5a --- /dev/null +++ b/libstdc++-v3/doc/html/ext/pb_ds/priority_queue_text_push_pop_timing_test.html @@ -0,0 +1,209 @@ + + + + + +Priority Queue Text Push Pop Timing Test + + + +
+

Priority Queue Text push and pop Timing + Test

+

Description

+

This test inserts a number of values with keys from an + arbitrary text ([ wickland96thirty ]) into + a container using push , then removes them using + pop . It measures the average time for push + as a function of the number of values.

+

(The test was executed with + priority_queue_text_push_pop_timing_test + thirty_years_among_the_dead_preproc.txt 200 200 2100)

+

Purpose

+

The test checks the effect of different underlying + data structures (see Design::Priority + Queues::Implementations).

+

Results

+

Figures NPG, NPM, and + NPL show the results for the native priority + queues and pb_ds 's priority queues in g++, msvc++, and + local, + respectively; Figures NBRG, NBRM, and NBRL show the results + for the native priority queues and pb_ds's pairing + queues in g++, msvc++, and + local, + respectively.

+
+
+
+
+
no image
NPG: Native tree and pb ds priority queue push and pop timing test - g++

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

+
    +
  1. +n_pq_vector- +std::priority_queue adapting std::vector
    2. +
  2. +n_pq_deque- +std::priority_queue adapting std::deque
    3. +
  3. +thin_heap- +priority_queue + with Tag = thin_heap_tag +
    4. +
  4. +rc_binomial_heap- +priority_queue + with Tag = rc_binomial_heap_tag +
    5. +
  5. +binomial_heap- +priority_queue + with Tag = binomial_heap_tag +
    6. +
  6. +binary_heap- +priority_queue + with Tag = binary_heap_tag +
    7. +
  7. +pairing_heap- +priority_queue + with Tag = pairing_heap_tag +
    8. +
+
+
+
+
+
+
+
+
+
+
no image
NPM: Native tree and pb ds priority queue push and pop timing test - msvc++

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

+
    +
  1. +n_pq_deque- +std::priority_queue adapting std::deque
    2. +
  2. +n_pq_vector- +std::priority_queue adapting std::vector
    3. +
  3. +thin_heap- +priority_queue + with Tag = thin_heap_tag +
    4. +
  4. +rc_binomial_heap- +priority_queue + with Tag = rc_binomial_heap_tag +
    5. +
  5. +binomial_heap- +priority_queue + with Tag = binomial_heap_tag +
    6. +
  6. +pairing_heap- +priority_queue + with Tag = pairing_heap_tag +
    7. +
  7. +binary_heap- +priority_queue + with Tag = binary_heap_tag +
    8. +
+
+
+
+
+
+
+
+
+
+
no image
NPL: Native tree and pb ds priority queue push and pop timing test - local
+
+
+
+
+
+
+
+
+
no image
NBRG: Native tree and pb ds pairing priority queue push and pop timing test - g++

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

+
    +
  1. +n_pq_vector- +std::priority_queue adapting std::vector
    2. +
  2. +n_pq_deque- +std::priority_queue adapting std::deque
    3. +
  3. +pairing_heap- +priority_queue + with Tag = pairing_heap_tag +
    4. +
+
+
+
+
+
+
+
+
+
+
no image
NBRM: Native tree and pb ds pairing priority queue push and pop timing test - msvc++

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

+
    +
  1. +n_pq_deque- +std::priority_queue adapting std::deque
    2. +
  2. +n_pq_vector- +std::priority_queue adapting std::vector
    3. +
  3. +pairing_heap- +priority_queue + with Tag = pairing_heap_tag +
    4. +
+
+
+
+
+
+
+
+
+
+
no image
NBRL: Native tree and pb ds pairing priority queue push and pop timing test - local
+
+
+
+
+

Observations

+

These results are very similar to Priority Queue Text + push Timing Test. As stated there, pairing heaps + (priority_queue with + Tag = pairing_heap_tag) + are most suited for push and pop sequences of + non-primitive types such as strings. Observing these two tests, + one can note that a pairing heap outperforms the others in + terms of push operations, but equals binary heaps + (priority_queue with + Tag = binary_heap_tag) if + the number of push and pop operations is + equal. As the number of pop operations is at most + equal to the number of push operations, pairing heaps + are better in this case. See Priority + Queue Random Integer push and pop Timing + Test for a case which is different.

+

Priority-Queue + Performance Tests::Observations discusses this further and + summarizes.

+
+ + -- cgit v1.2.3