1<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN"
2    "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
3
4<html xmlns="http://www.w3.org/1999/xhtml" xml:lang="en" lang="en">
5<head>
6<meta name="generator" content="HTML Tidy for Linux/x86 (vers 12 April 2005), see www.w3.org" />
7<title>Priority Queue Text Join Timing Test</title>
8<meta http-equiv="Content-Type" content="text/html; charset=us-ascii" />
9</head>
10<body>
11<div id="page">
12<h1>Priority Queue Text <tt>join</tt> Timing Test</h1>
13<h2><a name="description" id="description">Description</a></h2>
14<p>This test inserts a number of values with keys from an
15    arbitrary text ([ <a href="references.html#wickland96thirty">wickland96thirty</a> ]) into
16    two containers, then merges the containers. It uses
17    <tt>join</tt> for <tt>pb_ds</tt>'s priority queues; for the
18    STL's priority queues, it successively pops values from one
19    container and pushes them into the other. The test measures the
20    average time as a function of the number of values.</p>
21<p>(The test was executed with <a href="http://gcc.gnu.org/viewcvs/*checkout*/trunk/libstdc%2B%2B-v3/testsuite/performance/ext/pb_ds/priority_queue_text_join_timing.cc"><tt>priority_queue_text_join_timing_test</tt></a>
22    thirty_years_among_the_dead_preproc.txt 200 200 2100)</p>
23<h2><a name="purpose" id="purpose">Purpose</a></h2>
24<p>The test checks the effect of different underlying
25    data structures (see <a href="pq_design.html#pq_imp">Design::Priority
26    Queues::Implementations</a>).</p>
27<h2><a name="results" id="results">Results</a></h2>
28<p>Figures <a href="#NPG">NPG</a>, <a href="#NPM">NPM</a>, and
29    <a href="#NPL">NPL</a> show the results for the native priority
30    queues and <tt>pb_ds</tt> 's priority queues in <a href="pq_performance_tests.html#gcc"><u>g++</u></a>, <a href="pq_performance_tests.html#msvc"><u>msvc</u></a>, and <a href="pq_performance_tests.html#local"><u>local</u></a>,
31    respectively.</p>
32<div id="NPG_res_div">
33<div id="NPG_gcc">
34<div id="NPG_priority_queue_text_join_timing_test">
35<div id="NPG_pq">
36<div id="NPG_Native_tree_and__tt_pb_ds_455tt__priority_queue__tt_push_455tt__timing_test"><div style="border-style: dotted; border-width: 1px; border-color: lightgray"><h6 class="c1"><a name="NPG" id="NPG"><img src="priority_queue_text_join_timing_test_gcc.png" alt="no image" /></a></h6>NPG: Native tree and <tt>pb ds</tt> priority queue <tt>push</tt> timing test - <a href="pq_performance_tests.html#gcc">g++</a><p>In the above figure, the names in the legends have the following meaning:</p>
37<ol>
38<li>
39n_pq_deque-
40<tt>std::priority_queue</tt> adapting <tt>std::deque</tt></li>
41<li>
42n_pq_vector-
43<tt>std::priority_queue</tt> adapting <tt>std::vector</tt></li>
44<li>
45binary_heap-
46<a href="priority_queue.html"><tt>priority_queue</tt></a>
47 with <tt>Tag</tt> = <a href="binary_heap_tag.html"><tt>binary_heap_tag</tt></a>
48</li>
49<li>
50thin_heap-
51<a href="priority_queue.html"><tt>priority_queue</tt></a>
52 with <tt>Tag</tt> = <a href="thin_heap_tag.html"><tt>thin_heap_tag</tt></a>
53</li>
54<li>
55rc_binomial_heap-
56<a href="priority_queue.html"><tt>priority_queue</tt></a>
57 with <tt>Tag</tt> = <a href="rc_binomial_heap_tag.html"><tt>rc_binomial_heap_tag</tt></a>
58</li>
59<li>
60pairing_heap-
61<a href="priority_queue.html"><tt>priority_queue</tt></a>
62 with <tt>Tag</tt> = <a href="pairing_heap_tag.html"><tt>pairing_heap_tag</tt></a>
63</li>
64<li>
65binomial_heap-
66<a href="priority_queue.html"><tt>priority_queue</tt></a>
67 with <tt>Tag</tt> = <a href="binomial_heap_tag.html"><tt>binomial_heap_tag</tt></a>
68</li>
69</ol>
70</div><div style="width: 100%; height: 20px"></div></div>
71</div>
72</div>
73</div>
74</div>
75<div id="NPM_res_div">
76<div id="NPM_msvc">
77<div id="NPM_priority_queue_text_join_timing_test">
78<div id="NPM_pq">
79<div id="NPM_Native_tree_and__tt_pb_ds_455tt__priority_queue__tt_push_455tt__timing_test"><div style="border-style: dotted; border-width: 1px; border-color: lightgray"><h6 class="c1"><a name="NPM" id="NPM"><img src="priority_queue_text_join_timing_test_msvc.png" alt="no image" /></a></h6>NPM: Native tree and <tt>pb ds</tt> priority queue <tt>push</tt> timing test - <a href="pq_performance_tests.html#msvc">msvc++</a><p>In the above figure, the names in the legends have the following meaning:</p>
80<ol>
81<li>
82n_pq_deque-
83<tt>std::priority_queue</tt> adapting <tt>std::deque</tt></li>
84<li>
85n_pq_vector-
86<tt>std::priority_queue</tt> adapting <tt>std::vector</tt></li>
87<li>
88binary_heap-
89<a href="priority_queue.html"><tt>priority_queue</tt></a>
90 with <tt>Tag</tt> = <a href="binary_heap_tag.html"><tt>binary_heap_tag</tt></a>
91</li>
92<li>
93thin_heap-
94<a href="priority_queue.html"><tt>priority_queue</tt></a>
95 with <tt>Tag</tt> = <a href="thin_heap_tag.html"><tt>thin_heap_tag</tt></a>
96</li>
97<li>
98rc_binomial_heap-
99<a href="priority_queue.html"><tt>priority_queue</tt></a>
100 with <tt>Tag</tt> = <a href="rc_binomial_heap_tag.html"><tt>rc_binomial_heap_tag</tt></a>
101</li>
102<li>
103pairing_heap-
104<a href="priority_queue.html"><tt>priority_queue</tt></a>
105 with <tt>Tag</tt> = <a href="pairing_heap_tag.html"><tt>pairing_heap_tag</tt></a>
106</li>
107<li>
108binomial_heap-
109<a href="priority_queue.html"><tt>priority_queue</tt></a>
110 with <tt>Tag</tt> = <a href="binomial_heap_tag.html"><tt>binomial_heap_tag</tt></a>
111</li>
112</ol>
113</div><div style="width: 100%; height: 20px"></div></div>
114</div>
115</div>
116</div>
117</div>
118<div id="NPL_res_div">
119<div id="NPL_local">
120<div id="NPL_priority_queue_text_join_timing_test">
121<div id="NPL_pq">
122<div id="NPL_Native_tree_and__tt_pb_ds_455tt__priority_queue__tt_push_455tt__timing_test"><div style = "border-style: dotted; border-width: 1px; border-color: lightgray"><h6 class="c1"><a name="NPL" id= "NPL"><img src="priority_queue_text_join_timing_test_local.png" alt="no image" /></a></h6>NPL: Native tree and <tt>pb ds</tt> priority queue <tt>push</tt> timing test - <a href = "pq_performance_tests.html#local">local</a></div><div style = "width: 100%; height: 20px"></div></div>
123</div>
124</div>
125</div>
126</div>
127<h2><a name="observations" id="observations">Observations</a></h2>
128<p>In this test the node-based heaps perform <tt>join</tt> in
129    either logarithmic or constant time. The binary heap requires
130    linear time, since the well-known heapify algorithm [<a href="references.html#clrs2001">clrs2001</a>] is linear.</p>
131<p>It would be possible to apply the heapify algorithm to the
132    STL containers, if they would support iteration (which they
133    don't). Barring iterators, it is still somehow possible to
134    perform linear-time merge on a <tt>std::vector</tt>-based STL
135    priority queue, using <tt>top()</tt> and <tt>size()</tt> (since
136    they are enough to expose the underlying array), but this is
137    impossible for a <tt>std::deque</tt>-based STL priority queue.
138    Without heapify, the cost is super-linear.</p>
139</div>
140</body>
141</html>
142