libstdc++-v3/doc/html/ext/pb_ds/priority_queue_text_join_timing_test.html

   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>
  39 n_pq_deque-
  40 <tt>std::priority_queue</tt> adapting <tt>std::deque</tt></li>
  41 <li>
  42 n_pq_vector-
  43 <tt>std::priority_queue</tt> adapting <tt>std::vector</tt></li>
  44 <li>
  45 binary_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>
  50 thin_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>
  55 rc_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>
  60 pairing_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>
  65 binomial_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>
  82 n_pq_deque-
  83 <tt>std::priority_queue</tt> adapting <tt>std::deque</tt></li>
  84 <li>
  85 n_pq_vector-
  86 <tt>std::priority_queue</tt> adapting <tt>std::vector</tt></li>
  87 <li>
  88 binary_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>
  93 thin_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>
  98 rc_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>
 103 pairing_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>
 108 binomial_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>