X-Git-Url: https://oss.titaniummirror.com/gitweb?a=blobdiff_plain;f=libstdc%2B%2B-v3%2Fdoc%2Fhtml%2Fext%2Fpb_ds%2Fpriority_queue_text_join_timing_test.html;fp=libstdc%2B%2B-v3%2Fdoc%2Fhtml%2Fext%2Fpb_ds%2Fpriority_queue_text_join_timing_test.html;h=a4bf576ff52417baa872f0331573044996c3fb63;hb=6fed43773c9b0ce596dca5686f37ac3fc0fa11c0;hp=0000000000000000000000000000000000000000;hpb=27b11d56b743098deb193d510b337ba22dc52e5c;p=msp430-gcc.git diff --git a/libstdc++-v3/doc/html/ext/pb_ds/priority_queue_text_join_timing_test.html b/libstdc++-v3/doc/html/ext/pb_ds/priority_queue_text_join_timing_test.html new file mode 100644 index 00000000..a4bf576f --- /dev/null +++ b/libstdc++-v3/doc/html/ext/pb_ds/priority_queue_text_join_timing_test.html @@ -0,0 +1,141 @@ + + + + + +Priority Queue Text Join Timing Test + + + +
+

Priority Queue Text join Timing Test

+

Description

+

This test inserts a number of values with keys from an + arbitrary text ([ wickland96thirty ]) into + two containers, then merges the containers. It uses + join for pb_ds's priority queues; for the + STL's priority queues, it successively pops values from one + container and pushes them into the other. The test measures the + average time as a function of the number of values.

+

(The test was executed with priority_queue_text_join_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.

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

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. +binary_heap- +priority_queue + with Tag = binary_heap_tag +
    4. +
  4. +thin_heap- +priority_queue + with Tag = thin_heap_tag +
    5. +
  5. +rc_binomial_heap- +priority_queue + with Tag = rc_binomial_heap_tag +
    6. +
  6. +pairing_heap- +priority_queue + with Tag = pairing_heap_tag +
    7. +
  7. +binomial_heap- +priority_queue + with Tag = binomial_heap_tag +
    8. +
+
+
+
+
+
+
+
+
+
+
no image
NPM: Native tree and pb ds priority queue push 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. +binary_heap- +priority_queue + with Tag = binary_heap_tag +
    4. +
  4. +thin_heap- +priority_queue + with Tag = thin_heap_tag +
    5. +
  5. +rc_binomial_heap- +priority_queue + with Tag = rc_binomial_heap_tag +
    6. +
  6. +pairing_heap- +priority_queue + with Tag = pairing_heap_tag +
    7. +
  7. +binomial_heap- +priority_queue + with Tag = binomial_heap_tag +
    8. +
+
+
+
+
+
+
+
+
+
+
no image
NPL: Native tree and pb ds priority queue push timing test - local
+
+
+
+
+

Observations

+

In this test the node-based heaps perform join in + either logarithmic or constant time. The binary heap requires + linear time, since the well-known heapify algorithm [clrs2001] is linear.

+

It would be possible to apply the heapify algorithm to the + STL containers, if they would support iteration (which they + don't). Barring iterators, it is still somehow possible to + perform linear-time merge on a std::vector-based STL + priority queue, using top() and size() (since + they are enough to expose the underlying array), but this is + impossible for a std::deque-based STL priority queue. + Without heapify, the cost is super-linear.

+
+ +