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