X-Git-Url: https://oss.titaniummirror.com/gitweb/?a=blobdiff_plain;f=libstdc%2B%2B-v3%2Fdoc%2Fhtml%2Fext%2Fpb_ds%2Fpriority_queue_random_int_push_pop_timing_test.html;fp=libstdc%2B%2B-v3%2Fdoc%2Fhtml%2Fext%2Fpb_ds%2Fpriority_queue_random_int_push_pop_timing_test.html;h=903331d9d7d04cd75fd4b10c3e269342bb8619d3;hb=6fed43773c9b0ce596dca5686f37ac3fc0fa11c0;hp=0000000000000000000000000000000000000000;hpb=27b11d56b743098deb193d510b337ba22dc52e5c;p=msp430-gcc.git diff --git a/libstdc++-v3/doc/html/ext/pb_ds/priority_queue_random_int_push_pop_timing_test.html b/libstdc++-v3/doc/html/ext/pb_ds/priority_queue_random_int_push_pop_timing_test.html new file mode 100644 index 00000000..903331d9 --- /dev/null +++ b/libstdc++-v3/doc/html/ext/pb_ds/priority_queue_random_int_push_pop_timing_test.html @@ -0,0 +1,161 @@ + + + + + +Priority Queue Random Int Push Pop Timing Test + + + +
+

Priority Queue Random Integer push and + pop Timing Test

+

Description

+

This test inserts a number of values with i.i.d. integer + keys into a container using push , then removes them + using pop . It measures the average time for + push and pop as a function of the number of + values.

+

(The test was executed with +priority_queue_random_int_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 shows the results for the native + priority queues and pb_ds 's priority queues in + g++, + msvc++, and + local, + respectively.

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

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

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

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

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

Observations

+

Binary heaps are the most suited for sequences of + push and pop operations of primitive types + (e.g. ints). This is explained in + Priority + Queue Random Int push Timing Test . (See Priority Queue + Text push Timing Test for the case of primitive + types.)

+

At first glance it seems that the STL's vector-based + priority queue is approximately on par with pb_ds's + corresponding priority queue. There are two differences + however:

+
    +
  1. The STL's priority queue does not downsize the underlying + vector (or deque) as the priority queue becomes smaller + (see Priority Queue + Text pop Memory Use Test). It is therefore + gaining some speed at the expense of space.
    2. +
  2. From Priority + Queue Random Integer push and pop Timing + Test, it seems that the STL's priority queue is slower in + terms of pus operations. Since the number of + pop operations is at most that of push + operations, the test here is the "best" for the STL's + priority queue.
    3. +
+

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

+
+ +