libstdc++-v3/docs/html/ext/pb_ds/priority_queue_text_modify_up_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 Modify (Up) 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>modify</tt> Timing Test - I</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     into a container then modifies each one "up" (<i>i.e.,</i> it
  17     makes it larger). It uses <tt>modify</tt> for <tt>pb_ds</tt>'s
  18     priority queues; for the STL's priority queues, it pops values
  19     from a container until it reaches the value that should be
  20     modified, then pushes values back in. It measures the average
  21     time for <tt>modify</tt> as a function of the number of
  22     values.</p>
  23 <p>(The test was executed with <a href="../../../../testsuite/performance/ext/pb_ds/priority_queue_text_modify_timing.cc"><tt>priority_queue_text_modify_up_timing_test</tt></a>
  24     thirty_years_among_the_dead_preproc.txt 200 200 2100 t)</p>
  25 <h2><a name="purpose" id="purpose">Purpose</a></h2>
  26 <p>The test checks the effect of different underlying
  27     data structures (see <a href="pq_design.html#pq_imp">Design::Priority
  28     Queues::Implementations</a>) for graph algorithms settings.
  29     Note that making an arbitrary value larger (in the sense of the
  30     priority queue's comparison functor) corresponds to
  31     decrease-key in standard graph algorithms [<a href="references.html#clrs2001">clrs2001</a>].</p>
  32 <h2><a name="results" id="results">Results</a></h2>
  33 <p>Figures <a href="#NPG">NPG</a>, <a href="#NPM">NPM</a>, and
  34     <a href="#NPL">NPL</a> show the results for the native priority
  35     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
  36     <a href="pq_performance_tests.html#local"><u>local</u></a>,
  37     respectively; Figures <a href="#NRTG">NRTG</a>, <a href="#NRTM">NRTM</a>, and <a href="#NRTL">NRTL</a> show the results
  38     for the pairing heap and thin heaps in <a href="pq_performance_tests.html#gcc"><u>g++</u></a>, <a href="pq_performance_tests.html#msvc"><u>msvc++</u></a>, and
  39     <a href="pq_performance_tests.html#local"><u>local</u></a>,
  40     respectively,</p>
  41 <div id="NPG_res_div">
  42 <div id="NPG_gcc">
  43 <div id="NPG_priority_queue_text_modify_up_timing_test">
  44 <div id="NPG_pq">
  45 <div id="NPG_Native_and__tt_pb_ds_455tt__priority_queue__tt_modify_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_modify_up_timing_test_gcc.png" alt="no image" /></a></h6>NPG: Native and <tt>pb ds</tt> priority queue <tt>modify</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>
  46 <ol>
  47 <li>
  48 n_pq_deque-
  49 <tt>std::priority_queue</tt> adapting <tt>std::deque</tt></li>
  50 <li>
  51 n_pq_vector-
  52 <tt>std::priority_queue</tt> adapting <tt>std::vector</tt></li>
  53 <li>
  54 binary_heap-
  55 <a href="priority_queue.html"><tt>priority_queue</tt></a>
  56  with <tt>Tag</tt> = <a href="binary_heap_tag.html"><tt>binary_heap_tag</tt></a>
  57 </li>
  58 <li>
  59 rc_binomial_heap-
  60 <a href="priority_queue.html"><tt>priority_queue</tt></a>
  61  with <tt>Tag</tt> = <a href="rc_binomial_heap_tag.html"><tt>rc_binomial_heap_tag</tt></a>
  62 </li>
  63 <li>
  64 pairing_heap-
  65 <a href="priority_queue.html"><tt>priority_queue</tt></a>
  66  with <tt>Tag</tt> = <a href="pairing_heap_tag.html"><tt>pairing_heap_tag</tt></a>
  67 </li>
  68 <li>
  69 binomial_heap-
  70 <a href="priority_queue.html"><tt>priority_queue</tt></a>
  71  with <tt>Tag</tt> = <a href="binomial_heap_tag.html"><tt>binomial_heap_tag</tt></a>
  72 </li>
  73 <li>
  74 thin_heap-
  75 <a href="priority_queue.html"><tt>priority_queue</tt></a>
  76  with <tt>Tag</tt> = <a href="thin_heap_tag.html"><tt>thin_heap_tag</tt></a>
  77 </li>
  78 </ol>
  79 </div><div style="width: 100%; height: 20px"></div></div>
  80 </div>
  81 </div>
  82 </div>
  83 </div>
  84 <div id="NPM_res_div">
  85 <div id="NPM_msvc">
  86 <div id="NPM_priority_queue_text_modify_up_timing_test">
  87 <div id="NPM_pq">
  88 <div id="NPM_Native_and__tt_pb_ds_455tt__priority_queue__tt_modify_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_modify_up_timing_test_msvc.png" alt="no image" /></a></h6>NPM: Native and <tt>pb ds</tt> priority queue <tt>modify</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>
  89 <ol>
  90 <li>
  91 n_pq_deque-
  92 <tt>std::priority_queue</tt> adapting <tt>std::deque</tt></li>
  93 <li>
  94 n_pq_vector-
  95 <tt>std::priority_queue</tt> adapting <tt>std::vector</tt></li>
  96 <li>
  97 binary_heap-
  98 <a href="priority_queue.html"><tt>priority_queue</tt></a>
  99  with <tt>Tag</tt> = <a href="binary_heap_tag.html"><tt>binary_heap_tag</tt></a>
 100 </li>
 101 <li>
 102 rc_binomial_heap-
 103 <a href="priority_queue.html"><tt>priority_queue</tt></a>
 104  with <tt>Tag</tt> = <a href="rc_binomial_heap_tag.html"><tt>rc_binomial_heap_tag</tt></a>
 105 </li>
 106 <li>
 107 pairing_heap-
 108 <a href="priority_queue.html"><tt>priority_queue</tt></a>
 109  with <tt>Tag</tt> = <a href="pairing_heap_tag.html"><tt>pairing_heap_tag</tt></a>
 110 </li>
 111 <li>
 112 binomial_heap-
 113 <a href="priority_queue.html"><tt>priority_queue</tt></a>
 114  with <tt>Tag</tt> = <a href="binomial_heap_tag.html"><tt>binomial_heap_tag</tt></a>
 115 </li>
 116 <li>
 117 thin_heap-
 118 <a href="priority_queue.html"><tt>priority_queue</tt></a>
 119  with <tt>Tag</tt> = <a href="thin_heap_tag.html"><tt>thin_heap_tag</tt></a>
 120 </li>
 121 </ol>
 122 </div><div style="width: 100%; height: 20px"></div></div>
 123 </div>
 124 </div>
 125 </div>
 126 </div>
 127 <div id="NPL_res_div">
 128 <div id="NPL_local">
 129 <div id="NPL_priority_queue_text_modify_up_timing_test">
 130 <div id="NPL_pq">
 131 <div id="NPL_Native_and__tt_pb_ds_455tt__priority_queue__tt_modify_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_modify_up_timing_test_local.png" alt="no image" /></a></h6>NPL: Native and <tt>pb ds</tt> priority queue <tt>modify</tt> timing test - <a href = "pq_performance_tests.html#local">local</a></div><div style = "width: 100%; height: 20px"></div></div>
 132 </div>
 133 </div>
 134 </div>
 135 </div>
 136 <div id="NRTG_res_div">
 137 <div id="NRTG_gcc">
 138 <div id="NRTG_priority_queue_text_modify_up_timing_test_pairing_thin">
 139 <div id="NRTG_pq">
 140 <div id="NRTG_Pairing_and_thin__priority_queue__tt_modify_455tt__timing_test"><div style="border-style: dotted; border-width: 1px; border-color: lightgray"><h6 class="c1"><a name="NRTG" id="NRTG"><img src="priority_queue_text_modify_up_timing_test_pairing_thin_gcc.png" alt="no image" /></a></h6>NRTG: Pairing and thin  priority queue <tt>modify</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>
 141 <ol>
 142 <li>
 143 pairing_heap-
 144 <a href="priority_queue.html"><tt>priority_queue</tt></a>
 145  with <tt>Tag</tt> = <a href="pairing_heap_tag.html"><tt>pairing_heap_tag</tt></a>
 146 </li>
 147 <li>
 148 thin_heap-
 149 <a href="priority_queue.html"><tt>priority_queue</tt></a>
 150  with <tt>Tag</tt> = <a href="thin_heap_tag.html"><tt>thin_heap_tag</tt></a>
 151 </li>
 152 </ol>
 153 </div><div style="width: 100%; height: 20px"></div></div>
 154 </div>
 155 </div>
 156 </div>
 157 </div>
 158 <div id="NRTM_res_div">
 159 <div id="NRTM_msvc">
 160 <div id="NRTM_priority_queue_text_modify_up_timing_test_pairing_thin">
 161 <div id="NRTM_pq">
 162 <div id="NRTM_Pairing_and_thin__priority_queue__tt_modify_455tt__timing_test"><div style="border-style: dotted; border-width: 1px; border-color: lightgray"><h6 class="c1"><a name="NRTM" id="NRTM"><img src="priority_queue_text_modify_up_timing_test_pairing_thin_msvc.png" alt="no image" /></a></h6>NRTM: Pairing and thin  priority queue <tt>modify</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>
 163 <ol>
 164 <li>
 165 pairing_heap-
 166 <a href="priority_queue.html"><tt>priority_queue</tt></a>
 167  with <tt>Tag</tt> = <a href="pairing_heap_tag.html"><tt>pairing_heap_tag</tt></a>
 168 </li>
 169 <li>
 170 thin_heap-
 171 <a href="priority_queue.html"><tt>priority_queue</tt></a>
 172  with <tt>Tag</tt> = <a href="thin_heap_tag.html"><tt>thin_heap_tag</tt></a>
 173 </li>
 174 </ol>
 175 </div><div style="width: 100%; height: 20px"></div></div>
 176 </div>
 177 </div>
 178 </div>
 179 </div>
 180 <div id="NRTL_res_div">
 181 <div id="NRTL_local">
 182 <div id="NRTL_priority_queue_text_modify_up_timing_test_pairing_thin">
 183 <div id="NRTL_pq">
 184 <div id="NRTL_Pairing_and_thin__priority_queue__tt_modify_455tt__timing_test"><div style = "border-style: dotted; border-width: 1px; border-color: lightgray"><h6 class="c1"><a name="NRTL" id= "NRTL"><img src="priority_queue_text_modify_up_timing_test_pairing_thin_local.png" alt="no image" /></a></h6>NRTL: Pairing and thin  priority queue <tt>modify</tt> timing test - <a href = "pq_performance_tests.html#local">local</a></div><div style = "width: 100%; height: 20px"></div></div>
 185 </div>
 186 </div>
 187 </div>
 188 </div>
 189 <h2><a name="observations" id="observations">Observations</a></h2>
 190 <p>As noted above, increasing an arbitrary value (in the sense
 191     of the priority queue's comparison functor) is very common in
 192     graph-related algorithms. In this case, a thin heap (<a href="priority_queue.html"><tt>priority_queue</tt></a> with
 193     <tt>Tag</tt> = <a href="thin_heap_tag.html"><tt>thin_heap_tag</tt></a>)
 194     outperforms a pairing heap (<a href="priority_queue.html"><tt>priority_queue</tt></a> with
 195     <tt>Tag</tt> = <a href="pairing_heap_tag.html"><tt>pairing_heap_tag</tt></a>).
 196     Conversely, <a href="priority_queue_text_push_timing_test.html">Priority Queue Text
 197     <tt>push</tt> Timing Test</a>, <a href="priority_queue_text_push_pop_timing_test.html">Priority Queue
 198     Text <tt>push</tt> and <tt>pop</tt> Timing Test</a>, <a href="priority_queue_random_int_push_timing_test.html">Priority
 199     Queue Random Integer <tt>push</tt> Timing Test</a>, and
 200     <a href="priority_queue_random_int_push_pop_timing_test.html">Priority
 201     Queue Random Integer <tt>push</tt> and <tt>pop</tt> Timing
 202     Test</a> show that the situation is reversed for other
 203     operations. It is not clear when to prefer one of these two
 204     different types.</p>
 205 <p>In this test <tt>pb_ds</tt>'s binary heaps effectively
 206     perform modify in linear time. As explained in <a href="pq_design.html#pq_traits">Priority Queue Design::Traits</a>,
 207     given a valid point-type iterator, a binary heap can perform
 208     <tt>modify</tt> logarithmically. The problem is that binary
 209     heaps invalidate their find iterators with each modifying
 210     operation, and so the only way to obtain a valid point-type
 211     iterator is to iterate using a range-type iterator until
 212     finding the appropriate value, then use the range-type iterator
 213     for the <tt>modify</tt> operation.</p>
 214 <p>The explanation for the STL's priority queues' performance
 215     is similar to that in <a href="priority_queue_text_join_timing_test.html">Priority Queue Text
 216     <tt>join</tt> Timing Test</a>.</p>
 217 <p><a href="pq_performance_tests.html#pq_observations">Priority-Queue
 218     Performance Tests::Observations</a> discusses this further and
 219     summarizes.</p>
 220 </div>
 221 </body>
 222 </html>