--- /dev/null
+<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN"
+ "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
+
+<html xmlns="http://www.w3.org/1999/xhtml" xml:lang="en" lang="en">
+<head>
+<meta name="generator" content="HTML Tidy for Linux/x86 (vers 12 April 2005), see www.w3.org" />
+<title>Priority-Queue Performance Tests</title>
+<meta http-equiv="Content-Type" content="text/html; charset=us-ascii" />
+</head>
+<body>
+<div id="page">
+<h1>Priority-Queue Performance Tests</h1>
+<h2><a name="settings" id="settings">Settings</a></h2>
+<p>This section describes performance tests and their results.
+ 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
+ documentation) stand for three different builds:</p>
+<div id="gcc_settings_div">
+<div class="c1">
+<h3><a name="gcc" id="gcc"><u>g++</u></a></h3>
+<ul>
+<li>CPU speed - cpu MHz : 2660.644</li>
+<li>Memory - MemTotal: 484412 kB</li>
+<li>Platform -
+ Linux-2.6.12-9-386-i686-with-debian-testing-unstable</li>
+<li>Compiler - g++ (GCC) 4.0.2 20050808 (prerelease)
+ (Ubuntu 4.0.1-4ubuntu9) Copyright (C) 2005 Free Software
+ Foundation, Inc. This is free software; see the source
+ for copying conditions. There is NO warranty; not even
+ for MERCHANTABILITY or FITNESS FOR A PARTICULAR
+ PURPOSE.</li>
+</ul>
+</div>
+<div class="c2"></div>
+</div>
+<div id="msvc_settings_div">
+<div class="c1">
+<h3><a name="msvc" id="msvc"><u>msvc++</u></a></h3>
+<ul>
+<li>CPU speed - cpu MHz : 2660.554</li>
+<li>Memory - MemTotal: 484412 kB</li>
+<li>Platform - Windows XP Pro</li>
+<li>Compiler - Microsoft (R) 32-bit C/C++ Optimizing
+ Compiler Version 13.10.3077 for 80x86 Copyright (C)
+ Microsoft Corporation 1984-2002. All rights
+ reserved.</li>
+</ul>
+</div>
+<div class="c2"></div>
+</div>
+<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>
+<li>CPU speed - cpu MHz : 2250.000</li>
+<li>Memory - MemTotal: 2076248 kB</li>
+<li>Platform - Linux-2.6.16-1.2133_FC5-i686-with-redhat-5-Bordeaux</li>
+<li>Compiler - g++ (GCC) 4.1.1 20060525 (Red Hat 4.1.1-1)
+Copyright (C) 2006 Free Software Foundation, Inc.
+This is free software; see the source for copying conditions. There is NO
+warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
+</li>
+</ul>
+</div><div style = "width: 100%; height: 20px"></div></div>
+<h2><a name="pq_tests" id="pq_tests">Tests</a></h2>
+<ol>
+<li><a href="priority_queue_text_push_timing_test.html">Priority Queue
+ Text <tt>push</tt> Timing Test</a></li>
+<li><a href="priority_queue_text_push_pop_timing_test.html">Priority
+ Queue Text <tt>push</tt> and <tt>pop</tt> Timing
+ Test</a></li>
+<li><a href="priority_queue_random_int_push_timing_test.html">Priority
+ Queue Random Integer <tt>push</tt> Timing Test</a></li>
+<li><a href="priority_queue_random_int_push_pop_timing_test.html">Priority
+ Queue Random Integer <tt>push</tt> and <tt>pop</tt> Timing
+ Test</a></li>
+<li><a href="priority_queue_text_pop_mem_usage_test.html">Priority Queue
+ Text <tt>pop</tt> Memory Use Test</a></li>
+<li><a href="priority_queue_text_join_timing_test.html">Priority Queue
+ Text <tt>join</tt> Timing Test</a></li>
+<li><a href="priority_queue_text_modify_up_timing_test.html">Priority
+ Queue Text <tt>modify</tt> Timing Test - I</a></li>
+<li><a href="priority_queue_text_modify_down_timing_test.html">Priority
+ Queue Text <tt>modify</tt> Timing Test - II</a></li>
+</ol>
+<h2><a name="pq_observations" id="pq_observations">Observations</a></h2>
+<h3><a name="pq_observations_cplx" id="pq_observations_cplx">Underlying Data Structures
+ Complexity</a></h3>
+<p>The following table shows the complexities of the different
+ underlying data structures in terms of orders of growth. It is
+ interesting to note that this table implies something about the
+ constants of the operations as well (see <a href="#pq_observations_amortized_push_pop">Amortized <tt>push</tt>
+ and <tt>pop</tt> operations</a>).</p>
+<table class="c1" width="100%" border="1" summary="pq complexities">
+<tr>
+<td align="left"></td>
+<td align="left"><tt>push</tt></td>
+<td align="left"><tt>pop</tt></td>
+<td align="left"><tt>modify</tt></td>
+<td align="left"><tt>erase</tt></td>
+<td align="left"><tt>join</tt></td>
+</tr>
+<tr>
+<td align="left">
+<p><tt>std::priority_queue</tt></p>
+</td>
+<td align="left">
+<p><i>Θ(n)</i> worst</p>
+<p><i>Θ(log(n))</i> amortized</p>
+</td>
+<td align="left">
+<p class="c1">Θ(log(n)) Worst</p>
+</td>
+<td align="left">
+<p><i>Theta;(n log(n))</i> Worst</p>
+<p><sub><a href="#std_mod1">[std note 1]</a></sub></p>
+</td>
+<td align="left">
+<p class="c3">Θ(n log(n))</p>
+<p><sub><a href="#std_mod2">[std note 2]</a></sub></p>
+</td>
+<td align="left">
+<p class="c3">Θ(n log(n))</p>
+<p><sub><a href="#std_mod1">[std note 1]</a></sub></p>
+</td>
+</tr>
+<tr>
+<td align="left">
+<p><a href="priority_queue.html"><tt>priority_queue</tt></a></p>
+<p>with <tt>Tag</tt> =</p>
+<p><a href="pairing_heap_tag.html"><tt>pairing_heap_tag</tt></a></p>
+</td>
+<td align="left">
+<p class="c1">O(1)</p>
+</td>
+<td align="left">
+<p><i>Θ(n)</i> worst</p>
+<p><i>Θ(log(n))</i> amortized</p>
+</td>
+<td align="left">
+<p><i>Θ(n)</i> worst</p>
+<p><i>Θ(log(n))</i> amortized</p>
+</td>
+<td align="left">
+<p><i>Θ(n)</i> worst</p>
+<p><i>Θ(log(n))</i> amortized</p>
+</td>
+<td align="left">
+<p class="c1">O(1)</p>
+</td>
+</tr>
+<tr>
+<td align="left">
+<p><a href="priority_queue.html"><tt>priority_queue</tt></a></p>
+<p>with <tt>Tag</tt> =</p>
+<p><a href="binary_heap_tag.html"><tt>binary_heap_tag</tt></a></p>
+</td>
+<td align="left">
+<p><i>Θ(n)</i> worst</p>
+<p><i>Θ(log(n))</i> amortized</p>
+</td>
+<td align="left">
+<p><i>Θ(n)</i> worst</p>
+<p><i>Θ(log(n))</i> amortized</p>
+</td>
+<td align="left">
+<p class="c1">Θ(n)</p>
+</td>
+<td align="left">
+<p class="c1">Θ(n)</p>
+</td>
+<td align="left">
+<p class="c1">Θ(n)</p>
+</td>
+</tr>
+<tr>
+<td align="left">
+<p><a href="priority_queue.html"><tt>priority_queue</tt></a></p>
+<p>with <tt>Tag</tt> =</p>
+<p><a href="binomial_heap_tag.html"><tt>binomial_heap_tag</tt></a></p>
+</td>
+<td align="left">
+<p><i>Θ(log(n))</i> worst</p>
+<p><i>O(1)</i> amortized</p>
+</td>
+<td align="left">
+<p class="c1">Θ(log(n))</p>
+</td>
+<td align="left">
+<p class="c1">Θ(log(n))</p>
+</td>
+<td align="left">
+<p class="c1">Θ(log(n))</p>
+</td>
+<td align="left">
+<p class="c1">Θ(log(n))</p>
+</td>
+</tr>
+<tr>
+<td align="left">
+<p><a href="priority_queue.html"><tt>priority_queue</tt></a></p>
+<p>with <tt>Tag</tt> =</p>
+<p><a href="rc_binomial_heap_tag.html"><tt>rc_binomial_heap_tag</tt></a></p>
+</td>
+<td align="left">
+<p class="c1">O(1)</p>
+</td>
+<td align="left">
+<p class="c1">Θ(log(n))</p>
+</td>
+<td align="left">
+<p class="c1">Θ(log(n))</p>
+</td>
+<td align="left">
+<p class="c1">Θ(log(n))</p>
+</td>
+<td align="left">
+<p class="c1">Θ(log(n))</p>
+</td>
+</tr>
+<tr>
+<td align="left">
+<p><a href="priority_queue.html"><tt>priority_queue</tt></a></p>
+<p>with <tt>Tag</tt> =</p>
+<p><a href="thin_heap_tag.html"><tt>thin_heap_tag</tt></a></p>
+</td>
+<td align="left">
+<p class="c1">O(1)</p>
+</td>
+<td align="left">
+<p><i>Θ(n)</i> worst</p>
+<p><i>Θ(log(n))</i> amortized</p>
+</td>
+<td align="left">
+<p><i>Θ(log(n))</i> worst</p>
+<p><i>O(1)</i> amortized,</p>or
+
+ <p><i>Θ(log(n))</i> amortized</p>
+<p><sub><a href="#thin_heap_note">[thin_heap_note]</a></sub></p>
+</td>
+<td align="left">
+<p><i>Θ(n)</i> worst</p>
+<p><i>Θ(log(n))</i> amortized</p>
+</td>
+<td align="left">
+<p class="c1">Θ(n)</p>
+</td>
+</tr>
+</table>
+<p><sub><a name="std_mod1" id="std_mod1">[std note 1]</a> This
+ is not a property of the algorithm, but rather due to the fact
+ that the STL's priority queue implementation does not support
+ iterators (and consequently the ability to access a specific
+ value inside it). If the priority queue is adapting an
+ <tt>std::vector</tt>, then it is still possible to reduce this
+ to <i>Θ(n)</i> by adapting over the STL's adapter and
+ using the fact that <tt>top</tt> returns a reference to the
+ first value; if, however, it is adapting an
+ <tt>std::deque</tt>, then this is impossible.</sub></p>
+<p><sub><a name="std_mod2" id="std_mod2">[std note 2]</a> As
+ with <a href="#std_mod1">[std note 1]</a>, this is not a
+ property of the algorithm, but rather the STL's implementation.
+ Again, if the priority queue is adapting an
+ <tt>std::vector</tt> then it is possible to reduce this to
+ <i>Θ(n)</i>, but with a very high constant (one must call
+ <tt>std::make_heap</tt> which is an expensive linear
+ operation); if the priority queue is adapting an
+ <tt>std::dequeu</tt>, then this is impossible.</sub></p>
+<p><sub><a name="thin_heap_note" id="thin_heap_note">[thin_heap_note]</a> A thin heap has
+ <i>&Theta(log(n))</i> worst case <tt>modify</tt> time
+ always, but the amortized time depends on the nature of the
+ operation: I) if the operation increases the key (in the sense
+ of the priority queue's comparison functor), then the amortized
+ time is <i>O(1)</i>, but if II) it decreases it, then the
+ amortized time is the same as the worst case time. Note that
+ for most algorithms, I) is important and II) is not.</sub></p>
+<h3><a name="pq_observations_amortized_push_pop" id="pq_observations_amortized_push_pop">Amortized <tt>push</tt>
+ and <tt>pop</tt> operations</a></h3>
+<p>In many cases, a priority queue is needed primarily for
+ sequences of <tt>push</tt> and <tt>pop</tt> operations. All of
+ the underlying data structures have the same amortized
+ logarithmic complexity, but they differ in terms of
+ constants.</p>
+<p>The table above shows that the different data structures are
+ "constrained" in some respects. In general, if a data structure
+ has lower worst-case complexity than another, then it will
+ perform slower in the amortized sense. Thus, for example a
+ redundant-counter binomial heap (<a href="priority_queue.html"><tt>priority_queue</tt></a> with
+ <tt>Tag</tt> = <a href="rc_binomial_heap_tag.html"><tt>rc_binomial_heap_tag</tt></a>)
+ has lower worst-case <tt>push</tt> performance than a binomial
+ heap (<a href="priority_queue.html"><tt>priority_queue</tt></a>
+ with <tt>Tag</tt> = <a href="binomial_heap_tag.html"><tt>binomial_heap_tag</tt></a>),
+ and so its amortized <tt>push</tt> performance is slower in
+ terms of constants.</p>
+<p>As the table shows, the "least constrained" underlying
+ data structures are binary heaps and pairing heaps.
+ Consequently, it is not surprising that they perform best in
+ terms of amortized constants.</p>
+<ol>
+<li>Pairing heaps seem to perform best for non-primitive
+ types (<i>e.g.</i>, <tt>std::string</tt>s), as shown by
+ <a href="priority_queue_text_push_timing_test.html">Priority
+ Queue Text <tt>push</tt> Timing Test</a> and <a href="priority_queue_text_push_pop_timing_test.html">Priority
+ Queue Text <tt>push</tt> and <tt>pop</tt> Timing
+ Test</a></li>
+<li>binary heaps seem to perform best for primitive types
+ (<i>e.g.</i>, <tt><b>int</b></tt>s), as shown by <a href="priority_queue_random_int_push_timing_test.html">Priority
+ Queue Random Integer <tt>push</tt> Timing Test</a> and
+ <a href="priority_queue_random_int_push_pop_timing_test.html">Priority
+ Queue Random Integer <tt>push</tt> and <tt>pop</tt> Timing
+ Test</a>.</li>
+</ol>
+<h3><a name="pq_observations_graph" id="pq_observations_graph">Graph Algorithms</a></h3>
+<p>In some graph algorithms, a decrease-key operation is
+ required [<a href="references.html#clrs2001">clrs2001</a>];
+ this operation is identical to <tt>modify</tt> if a value is
+ increased (in the sense of the priority queue's comparison
+ functor). The table above and <a href="priority_queue_text_modify_up_timing_test.html">Priority Queue
+ Text <tt>modify</tt> Timing Test - I</a> show that a thin heap
+ (<a href="priority_queue.html"><tt>priority_queue</tt></a> with
+ <tt>Tag</tt> = <a href="thin_heap_tag.html"><tt>thin_heap_tag</tt></a>)
+ outperforms a pairing heap (<a href="priority_queue.html"><tt>priority_queue</tt></a> with
+ <tt>Tag</tt> =<tt>Tag</tt> = <a href="pairing_heap_tag.html"><tt>pairing_heap_tag</tt></a>),
+ but the rest of the tests show otherwise.</p>
+<p>This makes it difficult to decide which implementation to
+ use in this case. Dijkstra's shortest-path algorithm, for
+ example, requires <i>Θ(n)</i> <tt>push</tt> and
+ <tt>pop</tt> operations (in the number of vertices), but
+ <i>O(n<sup>2</sup>)</i> <tt>modify</tt> operations, which can
+ be in practice <i>Θ(n)</i> as well. It is difficult to
+ find an <i>a-priori</i> characterization of graphs in which the
+ <u>actual</u> number of <tt>modify</tt> operations will dwarf
+ the number of <tt>push</tt> and <tt>pop</tt> operations.</p>
+</div>
+</body>
+</html>
projects / msp430-gcc.git / blobdiff