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

Priority Queue Text modify Timing Test - I

+

Description

+

This test inserts a number of values with keys from an + arbitrary text ([ wickland96thirty ]) into + into a container then modifies each one "up" (i.e., it + makes it larger). It uses modify for pb_ds's + priority queues; for the STL's priority queues, it pops values + from a container until it reaches the value that should be + modified, then pushes values back in. It measures the average + time for modify as a function of the number of + values.

+

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

+

Purpose

+

The test checks the effect of different underlying + data structures (see Design::Priority + Queues::Implementations) for graph algorithms settings. + Note that making an arbitrary value larger (in the sense of the + priority queue's comparison functor) corresponds to + decrease-key in standard graph algorithms [clrs2001].

+

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 NRTG, NRTM, and NRTL show the results + for the pairing heap and thin heaps in g++, msvc++, and + local, + respectively,

+
+
+
+
+
no image
NPG: Native and pb ds priority queue modify 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. +rc_binomial_heap- +priority_queue + with Tag = rc_binomial_heap_tag +
    5. +
  5. +pairing_heap- +priority_queue + with Tag = pairing_heap_tag +
    6. +
  6. +binomial_heap- +priority_queue + with Tag = binomial_heap_tag +
    7. +
  7. +thin_heap- +priority_queue + with Tag = thin_heap_tag +
    8. +
+
+
+
+
+
+
+
+
+
+
no image
NPM: Native and pb ds priority queue modify 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. +rc_binomial_heap- +priority_queue + with Tag = rc_binomial_heap_tag +
    5. +
  5. +pairing_heap- +priority_queue + with Tag = pairing_heap_tag +
    6. +
  6. +binomial_heap- +priority_queue + with Tag = binomial_heap_tag +
    7. +
  7. +thin_heap- +priority_queue + with Tag = thin_heap_tag +
    8. +
+
+
+
+
+
+
+
+
+
+
no image
NPL: Native and pb ds priority queue modify timing test - local
+
+
+
+
+
+
+
+
+
no image
NRTG: Pairing and thin priority queue modify timing test - g++

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

+
    +
  1. +pairing_heap- +priority_queue + with Tag = pairing_heap_tag +
    2. +
  2. +thin_heap- +priority_queue + with Tag = thin_heap_tag +
    3. +
+
+
+
+
+
+
+
+
+
+
no image
NRTM: Pairing and thin priority queue modify timing test - msvc++

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

+
    +
  1. +pairing_heap- +priority_queue + with Tag = pairing_heap_tag +
    2. +
  2. +thin_heap- +priority_queue + with Tag = thin_heap_tag +
    3. +
+
+
+
+
+
+
+
+
+
+
no image
NRTL: Pairing and thin priority queue modify timing test - local
+
+
+
+
+

Observations

+

As noted above, increasing an arbitrary value (in the sense + of the priority queue's comparison functor) is very common in + graph-related algorithms. In this case, a thin heap (priority_queue with + Tag = thin_heap_tag) + outperforms a pairing heap (priority_queue with + Tag = pairing_heap_tag). + Conversely, Priority Queue Text + push Timing Test, Priority Queue + Text push and pop Timing Test, Priority + Queue Random Integer push Timing Test, and + Priority + Queue Random Integer push and pop Timing + Test show that the situation is reversed for other + operations. It is not clear when to prefer one of these two + different types.

+

In this test pb_ds's binary heaps effectively + perform modify in linear time. As explained in Priority Queue Design::Traits, + given a valid point-type iterator, a binary heap can perform + modify logarithmically. The problem is that binary + heaps invalidate their find iterators with each modifying + operation, and so the only way to obtain a valid point-type + iterator is to iterate using a range-type iterator until + finding the appropriate value, then use the range-type iterator + for the modify operation.

+

The explanation for the STL's priority queues' performance + is similar to that in Priority Queue Text + join Timing Test.

+

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

+
+ +