libstdc++-v3/docs/html/ext/pb_ds/pq_performance_tests.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 Performance Tests</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 Performance Tests</h1>
  13 <h2><a name="settings" id="settings">Settings</a></h2>
  14 <p>This section describes performance tests and their results.
  15     In the following, <a href="#gcc"><u>g++</u></a>, <a href="#msvc"><u>msvc++</u></a>, and <a href="#local"><u>local</u></a> (the build used for generating this
  16     documentation) stand for three different builds:</p>
  17 <div id="gcc_settings_div">
  18 <div class="c1">
  19 <h3><a name="gcc" id="gcc"><u>g++</u></a></h3>
  20 <ul>
  21 <li>CPU speed - cpu MHz : 2660.644</li>
  22 <li>Memory - MemTotal: 484412 kB</li>
  23 <li>Platform -
  24           Linux-2.6.12-9-386-i686-with-debian-testing-unstable</li>
  25 <li>Compiler - g++ (GCC) 4.0.2 20050808 (prerelease)
  26           (Ubuntu 4.0.1-4ubuntu9) Copyright (C) 2005 Free Software
  27           Foundation, Inc. This is free software; see the source
  28           for copying conditions. There is NO warranty; not even
  29           for MERCHANTABILITY or FITNESS FOR A PARTICULAR
  30           PURPOSE.</li>
  31 </ul>
  32 </div>
  33 <div class="c2"></div>
  34 </div>
  35 <div id="msvc_settings_div">
  36 <div class="c1">
  37 <h3><a name="msvc" id="msvc"><u>msvc++</u></a></h3>
  38 <ul>
  39 <li>CPU speed - cpu MHz : 2660.554</li>
  40 <li>Memory - MemTotal: 484412 kB</li>
  41 <li>Platform - Windows XP Pro</li>
  42 <li>Compiler - Microsoft (R) 32-bit C/C++ Optimizing
  43           Compiler Version 13.10.3077 for 80x86 Copyright (C)
  44           Microsoft Corporation 1984-2002. All rights
  45           reserved.</li>
  46 </ul>
  47 </div>
  48 <div class="c2"></div>
  49 </div>
  50 <div id="local_settings_div"><div style = "border-style: dotted; border-width: 1px; border-color: lightgray"><h3><a name = "local"><u>local</u></a></h3><ul>
  51 <li>CPU speed - cpu MHz         : 2250.000</li>
  52 <li>Memory - MemTotal:      2076248 kB</li>
  53 <li>Platform - Linux-2.6.16-1.2133_FC5-i686-with-redhat-5-Bordeaux</li>
  54 <li>Compiler - g++ (GCC) 4.1.1 20060525 (Red Hat 4.1.1-1)
  55 Copyright (C) 2006 Free Software Foundation, Inc.
  56 This is free software; see the source for copying conditions.  There is NO
  57 warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
  58 </li>
  59 </ul>
  60 </div><div style = "width: 100%; height: 20px"></div></div>
  61 <h2><a name="pq_tests" id="pq_tests">Tests</a></h2>
  62 <ol>
  63 <li><a href="priority_queue_text_push_timing_test.html">Priority Queue
  64       Text <tt>push</tt> Timing Test</a></li>
  65 <li><a href="priority_queue_text_push_pop_timing_test.html">Priority
  66       Queue Text <tt>push</tt> and <tt>pop</tt> Timing
  67       Test</a></li>
  68 <li><a href="priority_queue_random_int_push_timing_test.html">Priority
  69       Queue Random Integer <tt>push</tt> Timing Test</a></li>
  70 <li><a href="priority_queue_random_int_push_pop_timing_test.html">Priority
  71       Queue Random Integer <tt>push</tt> and <tt>pop</tt> Timing
  72       Test</a></li>
  73 <li><a href="priority_queue_text_pop_mem_usage_test.html">Priority Queue
  74       Text <tt>pop</tt> Memory Use Test</a></li>
  75 <li><a href="priority_queue_text_join_timing_test.html">Priority Queue
  76       Text <tt>join</tt> Timing Test</a></li>
  77 <li><a href="priority_queue_text_modify_up_timing_test.html">Priority
  78       Queue Text <tt>modify</tt> Timing Test - I</a></li>
  79 <li><a href="priority_queue_text_modify_down_timing_test.html">Priority
  80       Queue Text <tt>modify</tt> Timing Test - II</a></li>
  81 </ol>
  82 <h2><a name="pq_observations" id="pq_observations">Observations</a></h2>
  83 <h3><a name="pq_observations_cplx" id="pq_observations_cplx">Underlying Data Structures
  84     Complexity</a></h3>
  85 <p>The following table shows the complexities of the different
  86     underlying data structures in terms of orders of growth. It is
  87     interesting to note that this table implies something about the
  88     constants of the operations as well (see <a href="#pq_observations_amortized_push_pop">Amortized <tt>push</tt>
  89     and <tt>pop</tt> operations</a>).</p>
  90 <table class="c1" width="100%" border="1" summary="pq complexities">
  91 <tr>
  92 <td align="left"></td>
  93 <td align="left"><tt>push</tt></td>
  94 <td align="left"><tt>pop</tt></td>
  95 <td align="left"><tt>modify</tt></td>
  96 <td align="left"><tt>erase</tt></td>
  97 <td align="left"><tt>join</tt></td>
  98 </tr>
  99 <tr>
 100 <td align="left">
 101 <p><tt>std::priority_queue</tt></p>
 102 </td>
 103 <td align="left">
 104 <p><i>&Theta;(n)</i> worst</p>
 105 <p><i>&Theta;(log(n))</i> amortized</p>
 106 </td>
 107 <td align="left">
 108 <p class="c1">&Theta;(log(n)) Worst</p>
 109 </td>
 110 <td align="left">
 111 <p><i>Theta;(n log(n))</i> Worst</p>
 112 <p><sub><a href="#std_mod1">[std note 1]</a></sub></p>
 113 </td>
 114 <td align="left">
 115 <p class="c3">&Theta;(n log(n))</p>
 116 <p><sub><a href="#std_mod2">[std note 2]</a></sub></p>
 117 </td>
 118 <td align="left">
 119 <p class="c3">&Theta;(n log(n))</p>
 120 <p><sub><a href="#std_mod1">[std note 1]</a></sub></p>
 121 </td>
 122 </tr>
 123 <tr>
 124 <td align="left">
 125 <p><a href="priority_queue.html"><tt>priority_queue</tt></a></p>
 126 <p>with <tt>Tag</tt> =</p>
 127 <p><a href="pairing_heap_tag.html"><tt>pairing_heap_tag</tt></a></p>
 128 </td>
 129 <td align="left">
 130 <p class="c1">O(1)</p>
 131 </td>
 132 <td align="left">
 133 <p><i>&Theta;(n)</i> worst</p>
 134 <p><i>&Theta;(log(n))</i> amortized</p>
 135 </td>
 136 <td align="left">
 137 <p><i>&Theta;(n)</i> worst</p>
 138 <p><i>&Theta;(log(n))</i> amortized</p>
 139 </td>
 140 <td align="left">
 141 <p><i>&Theta;(n)</i> worst</p>
 142 <p><i>&Theta;(log(n))</i> amortized</p>
 143 </td>
 144 <td align="left">
 145 <p class="c1">O(1)</p>
 146 </td>
 147 </tr>
 148 <tr>
 149 <td align="left">
 150 <p><a href="priority_queue.html"><tt>priority_queue</tt></a></p>
 151 <p>with <tt>Tag</tt> =</p>
 152 <p><a href="binary_heap_tag.html"><tt>binary_heap_tag</tt></a></p>
 153 </td>
 154 <td align="left">
 155 <p><i>&Theta;(n)</i> worst</p>
 156 <p><i>&Theta;(log(n))</i> amortized</p>
 157 </td>
 158 <td align="left">
 159 <p><i>&Theta;(n)</i> worst</p>
 160 <p><i>&Theta;(log(n))</i> amortized</p>
 161 </td>
 162 <td align="left">
 163 <p class="c1">&Theta;(n)</p>
 164 </td>
 165 <td align="left">
 166 <p class="c1">&Theta;(n)</p>
 167 </td>
 168 <td align="left">
 169 <p class="c1">&Theta;(n)</p>
 170 </td>
 171 </tr>
 172 <tr>
 173 <td align="left">
 174 <p><a href="priority_queue.html"><tt>priority_queue</tt></a></p>
 175 <p>with <tt>Tag</tt> =</p>
 176 <p><a href="binomial_heap_tag.html"><tt>binomial_heap_tag</tt></a></p>
 177 </td>
 178 <td align="left">
 179 <p><i>&Theta;(log(n))</i> worst</p>
 180 <p><i>O(1)</i> amortized</p>
 181 </td>
 182 <td align="left">
 183 <p class="c1">&Theta;(log(n))</p>
 184 </td>
 185 <td align="left">
 186 <p class="c1">&Theta;(log(n))</p>
 187 </td>
 188 <td align="left">
 189 <p class="c1">&Theta;(log(n))</p>
 190 </td>
 191 <td align="left">
 192 <p class="c1">&Theta;(log(n))</p>
 193 </td>
 194 </tr>
 195 <tr>
 196 <td align="left">
 197 <p><a href="priority_queue.html"><tt>priority_queue</tt></a></p>
 198 <p>with <tt>Tag</tt> =</p>
 199 <p><a href="rc_binomial_heap_tag.html"><tt>rc_binomial_heap_tag</tt></a></p>
 200 </td>
 201 <td align="left">
 202 <p class="c1">O(1)</p>
 203 </td>
 204 <td align="left">
 205 <p class="c1">&Theta;(log(n))</p>
 206 </td>
 207 <td align="left">
 208 <p class="c1">&Theta;(log(n))</p>
 209 </td>
 210 <td align="left">
 211 <p class="c1">&Theta;(log(n))</p>
 212 </td>
 213 <td align="left">
 214 <p class="c1">&Theta;(log(n))</p>
 215 </td>
 216 </tr>
 217 <tr>
 218 <td align="left">
 219 <p><a href="priority_queue.html"><tt>priority_queue</tt></a></p>
 220 <p>with <tt>Tag</tt> =</p>
 221 <p><a href="thin_heap_tag.html"><tt>thin_heap_tag</tt></a></p>
 222 </td>
 223 <td align="left">
 224 <p class="c1">O(1)</p>
 225 </td>
 226 <td align="left">
 227 <p><i>&Theta;(n)</i> worst</p>
 228 <p><i>&Theta;(log(n))</i> amortized</p>
 229 </td>
 230 <td align="left">
 231 <p><i>&Theta;(log(n))</i> worst</p>
 232 <p><i>O(1)</i> amortized,</p>or
 233
 234           <p><i>&Theta;(log(n))</i> amortized</p>
 235 <p><sub><a href="#thin_heap_note">[thin_heap_note]</a></sub></p>
 236 </td>
 237 <td align="left">
 238 <p><i>&Theta;(n)</i> worst</p>
 239 <p><i>&Theta;(log(n))</i> amortized</p>
 240 </td>
 241 <td align="left">
 242 <p class="c1">&Theta;(n)</p>
 243 </td>
 244 </tr>
 245 </table>
 246 <p><sub><a name="std_mod1" id="std_mod1">[std note 1]</a> This
 247     is not a property of the algorithm, but rather due to the fact
 248     that the STL's priority queue implementation does not support
 249     iterators (and consequently the ability to access a specific
 250     value inside it). If the priority queue is adapting an
 251     <tt>std::vector</tt>, then it is still possible to reduce this
 252     to <i>&Theta;(n)</i> by adapting over the STL's adapter and
 253     using the fact that <tt>top</tt> returns a reference to the
 254     first value; if, however, it is adapting an
 255     <tt>std::deque</tt>, then this is impossible.</sub></p>
 256 <p><sub><a name="std_mod2" id="std_mod2">[std note 2]</a> As
 257     with <a href="#std_mod1">[std note 1]</a>, this is not a
 258     property of the algorithm, but rather the STL's implementation.
 259     Again, if the priority queue is adapting an
 260     <tt>std::vector</tt> then it is possible to reduce this to
 261     <i>&Theta;(n)</i>, but with a very high constant (one must call
 262     <tt>std::make_heap</tt> which is an expensive linear
 263     operation); if the priority queue is adapting an
 264     <tt>std::dequeu</tt>, then this is impossible.</sub></p>
 265 <p><sub><a name="thin_heap_note" id="thin_heap_note">[thin_heap_note]</a> A thin heap has
 266     <i>&amp;Theta(log(n))</i> worst case <tt>modify</tt> time
 267     always, but the amortized time depends on the nature of the
 268     operation: I) if the operation increases the key (in the sense
 269     of the priority queue's comparison functor), then the amortized
 270     time is <i>O(1)</i>, but if II) it decreases it, then the
 271     amortized time is the same as the worst case time. Note that
 272     for most algorithms, I) is important and II) is not.</sub></p>
 273 <h3><a name="pq_observations_amortized_push_pop" id="pq_observations_amortized_push_pop">Amortized <tt>push</tt>
 274     and <tt>pop</tt> operations</a></h3>
 275 <p>In many cases, a priority queue is needed primarily for
 276     sequences of <tt>push</tt> and <tt>pop</tt> operations. All of
 277     the underlying data structures have the same amortized
 278     logarithmic complexity, but they differ in terms of
 279     constants.</p>
 280 <p>The table above shows that the different data structures are
 281     "constrained" in some respects. In general, if a data structure
 282     has lower worst-case complexity than another, then it will
 283     perform slower in the amortized sense. Thus, for example a
 284     redundant-counter binomial heap (<a href="priority_queue.html"><tt>priority_queue</tt></a> with
 285     <tt>Tag</tt> = <a href="rc_binomial_heap_tag.html"><tt>rc_binomial_heap_tag</tt></a>)
 286     has lower worst-case <tt>push</tt> performance than a binomial
 287     heap (<a href="priority_queue.html"><tt>priority_queue</tt></a>
 288     with <tt>Tag</tt> = <a href="binomial_heap_tag.html"><tt>binomial_heap_tag</tt></a>),
 289     and so its amortized <tt>push</tt> performance is slower in
 290     terms of constants.</p>
 291 <p>As the table shows, the "least constrained" underlying
 292     data structures are binary heaps and pairing heaps.
 293     Consequently, it is not surprising that they perform best in
 294     terms of amortized constants.</p>
 295 <ol>
 296 <li>Pairing heaps seem to perform best for non-primitive
 297       types (<i>e.g.</i>, <tt>std::string</tt>s), as shown by
 298       <a href="priority_queue_text_push_timing_test.html">Priority
 299       Queue Text <tt>push</tt> Timing Test</a> and <a href="priority_queue_text_push_pop_timing_test.html">Priority
 300       Queue Text <tt>push</tt> and <tt>pop</tt> Timing
 301       Test</a></li>
 302 <li>binary heaps seem to perform best for primitive types
 303       (<i>e.g.</i>, <tt><b>int</b></tt>s), as shown by <a href="priority_queue_random_int_push_timing_test.html">Priority
 304       Queue Random Integer <tt>push</tt> Timing Test</a> and
 305       <a href="priority_queue_random_int_push_pop_timing_test.html">Priority
 306       Queue Random Integer <tt>push</tt> and <tt>pop</tt> Timing
 307       Test</a>.</li>
 308 </ol>
 309 <h3><a name="pq_observations_graph" id="pq_observations_graph">Graph Algorithms</a></h3>
 310 <p>In some graph algorithms, a decrease-key operation is
 311     required [<a href="references.html#clrs2001">clrs2001</a>];
 312     this operation is identical to <tt>modify</tt> if a value is
 313     increased (in the sense of the priority queue's comparison
 314     functor). The table above and <a href="priority_queue_text_modify_up_timing_test.html">Priority Queue
 315     Text <tt>modify</tt> Timing Test - I</a> show that a thin heap
 316     (<a href="priority_queue.html"><tt>priority_queue</tt></a> with
 317     <tt>Tag</tt> = <a href="thin_heap_tag.html"><tt>thin_heap_tag</tt></a>)
 318     outperforms a pairing heap (<a href="priority_queue.html"><tt>priority_queue</tt></a> with
 319     <tt>Tag</tt> =<tt>Tag</tt> = <a href="pairing_heap_tag.html"><tt>pairing_heap_tag</tt></a>),
 320     but the rest of the tests show otherwise.</p>
 321 <p>This makes it difficult to decide which implementation to
 322     use in this case. Dijkstra's shortest-path algorithm, for
 323     example, requires <i>&Theta;(n)</i> <tt>push</tt> and
 324     <tt>pop</tt> operations (in the number of vertices), but
 325     <i>O(n<sup>2</sup>)</i> <tt>modify</tt> operations, which can
 326     be in practice <i>&Theta;(n)</i> as well. It is difficult to
 327     find an <i>a-priori</i> characterization of graphs in which the
 328     <u>actual</u> number of <tt>modify</tt> operations will dwarf
 329     the number of <tt>push</tt> and <tt>pop</tt> operations.</p>
 330 </div>
 331 </body>
 332 </html>