OLD | NEW |
| (Empty) |
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), se
e www.w3.org" /> | |
7 <title>Priority Queue Text Push 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>push</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">wickland96thirt
y</a> ]) into | |
16 a container using <tt>push</tt> . It measures the average time | |
17 for <tt>push</tt> as a function of the number of values | |
18 pushed.</p> | |
19 <p>(The test was executed with <a href="http://gcc.gnu.org/viewcvs/*checkout*/tr
unk/libstdc%2B%2B-v3/testsuite/performance/ext/pb_ds/priority_queue_text_push_ti
ming.cc"><tt>priority_queue_text_push_timing_test</tt></a> | |
20 thirty_years_among_the_dead_preproc.txt 200 200 2100)</p> | |
21 <h2><a name="purpose" id="purpose">Purpose</a></h2> | |
22 <p>The test checks the effect of different underlying | |
23 data structures (see <a href="pq_design.html#pq_imp">Design::Priority | |
24 Queues::Implementations</a>).</p> | |
25 <h2><a name="results" id="results">Results</a></h2> | |
26 <p>Figures <a href="#NPG">NPG</a>, <a href="#NPM">NPM</a>, and | |
27 <a href="#NPL">NPL</a> show the results for the native priority | |
28 queues and <tt>pb_ds</tt> 's priority queues in <a href="pq_performance_test
s.html#gcc"><u>g++</u></a>, <a href="pq_performance_tests.html#msvc"><u>msvc++</
u></a>, and | |
29 <a href="pq_performance_tests.html#local"><u>local</u></a>, | |
30 respectively; Figures <a href="#NBRG">NBRG</a>, <a href="#NBRM">NBRM</a>, an
d <a href="#NBRL">NBRL</a> shows the | |
31 results for the binary-heap based native priority queues and | |
32 <tt>pb_ds</tt>'s pairing-heap priority queues in <a href="pq_performance_tes
ts.html#gcc"><u>g++</u></a>, <a href="pq_performance_tests.html#msvc"><u>msvc++<
/u></a>, and | |
33 <a href="pq_performance_tests.html#local"><u>local</u></a>, | |
34 respectively</p> | |
35 <div id="NPG_res_div"> | |
36 <div id="NPG_gcc"> | |
37 <div id="NPG_priority_queue_text_push_timing_test"> | |
38 <div id="NPG_pq"> | |
39 <div id="NPG_Native_and__tt_pb_ds_455tt__priority_queue__tt_push_455tt__timing_t
est"><div style="border-style: dotted; border-width: 1px; border-color: lightgra
y"><h6 class="c1"><a name="NPG" id="NPG"><img src="priority_queue_text_push_timi
ng_test_gcc.png" alt="no image" /></a></h6>NPG: Native and <tt>pb ds</tt> priori
ty 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> | |
40 <ol> | |
41 <li> | |
42 n_pq_vector- | |
43 <tt>std::priority_queue</tt> adapting <tt>std::vector</tt></li> | |
44 <li> | |
45 n_pq_deque- | |
46 <tt>std::priority_queue</tt> adapting <tt>std::deque</tt></li> | |
47 <li> | |
48 binary_heap- | |
49 <a href="priority_queue.html"><tt>priority_queue</tt></a> | |
50 with <tt>Tag</tt> = <a href="binary_heap_tag.html"><tt>binary_heap_tag</tt></a> | |
51 </li> | |
52 <li> | |
53 rc_binomial_heap- | |
54 <a href="priority_queue.html"><tt>priority_queue</tt></a> | |
55 with <tt>Tag</tt> = <a href="rc_binomial_heap_tag.html"><tt>rc_binomial_heap_ta
g</tt></a> | |
56 </li> | |
57 <li> | |
58 thin_heap- | |
59 <a href="priority_queue.html"><tt>priority_queue</tt></a> | |
60 with <tt>Tag</tt> = <a href="thin_heap_tag.html"><tt>thin_heap_tag</tt></a> | |
61 </li> | |
62 <li> | |
63 binomial_heap- | |
64 <a href="priority_queue.html"><tt>priority_queue</tt></a> | |
65 with <tt>Tag</tt> = <a href="binomial_heap_tag.html"><tt>binomial_heap_tag</tt>
</a> | |
66 </li> | |
67 <li> | |
68 pairing_heap- | |
69 <a href="priority_queue.html"><tt>priority_queue</tt></a> | |
70 with <tt>Tag</tt> = <a href="pairing_heap_tag.html"><tt>pairing_heap_tag</tt></
a> | |
71 </li> | |
72 </ol> | |
73 </div><div style="width: 100%; height: 20px"></div></div> | |
74 </div> | |
75 </div> | |
76 </div> | |
77 </div> | |
78 <div id="NPM_res_div"> | |
79 <div id="NPM_msvc"> | |
80 <div id="NPM_priority_queue_text_push_timing_test"> | |
81 <div id="NPM_pq"> | |
82 <div id="NPM_Native_and__tt_pb_ds_455tt__priority_queue__tt_push_455tt__timing_t
est"><div style="border-style: dotted; border-width: 1px; border-color: lightgra
y"><h6 class="c1"><a name="NPM" id="NPM"><img src="priority_queue_text_push_timi
ng_test_msvc.png" alt="no image" /></a></h6>NPM: Native and <tt>pb ds</tt> prior
ity queue <tt>push</tt> timing test - <a href="pq_performance_tests.html#msvc">m
svc++</a><p>In the above figure, the names in the legends have the following mea
ning:</p> | |
83 <ol> | |
84 <li> | |
85 n_pq_deque- | |
86 <tt>std::priority_queue</tt> adapting <tt>std::deque</tt></li> | |
87 <li> | |
88 rc_binomial_heap- | |
89 <a href="priority_queue.html"><tt>priority_queue</tt></a> | |
90 with <tt>Tag</tt> = <a href="rc_binomial_heap_tag.html"><tt>rc_binomial_heap_ta
g</tt></a> | |
91 </li> | |
92 <li> | |
93 binary_heap- | |
94 <a href="priority_queue.html"><tt>priority_queue</tt></a> | |
95 with <tt>Tag</tt> = <a href="binary_heap_tag.html"><tt>binary_heap_tag</tt></a> | |
96 </li> | |
97 <li> | |
98 binomial_heap- | |
99 <a href="priority_queue.html"><tt>priority_queue</tt></a> | |
100 with <tt>Tag</tt> = <a href="binomial_heap_tag.html"><tt>binomial_heap_tag</tt>
</a> | |
101 </li> | |
102 <li> | |
103 n_pq_vector- | |
104 <tt>std::priority_queue</tt> adapting <tt>std::vector</tt></li> | |
105 <li> | |
106 pairing_heap- | |
107 <a href="priority_queue.html"><tt>priority_queue</tt></a> | |
108 with <tt>Tag</tt> = <a href="pairing_heap_tag.html"><tt>pairing_heap_tag</tt></
a> | |
109 </li> | |
110 <li> | |
111 thin_heap- | |
112 <a href="priority_queue.html"><tt>priority_queue</tt></a> | |
113 with <tt>Tag</tt> = <a href="thin_heap_tag.html"><tt>thin_heap_tag</tt></a> | |
114 </li> | |
115 </ol> | |
116 </div><div style="width: 100%; height: 20px"></div></div> | |
117 </div> | |
118 </div> | |
119 </div> | |
120 </div> | |
121 <div id="NPL_res_div"> | |
122 <div id="NPL_local"> | |
123 <div id="NPL_priority_queue_text_push_timing_test"> | |
124 <div id="NPL_pq"> | |
125 <div id="NPL_Native_and__tt_pb_ds_455tt__priority_queue__tt_push_455tt__timing_t
est"><div style = "border-style: dotted; border-width: 1px; border-color: lightg
ray"><h6 class="c1"><a name="NPL" id= "NPL"><img src="priority_queue_text_push_t
iming_test_local.png" alt="no image" /></a></h6>NPL: Native and <tt>pb ds</tt> p
riority queue <tt>push</tt> timing test - <a href = "pq_performance_tests.html#l
ocal">local</a></div><div style = "width: 100%; height: 20px"></div></div> | |
126 </div> | |
127 </div> | |
128 </div> | |
129 </div> | |
130 <div id="NBRG_res_div"> | |
131 <div id="NBRG_gcc"> | |
132 <div id="NBRG_pairing_priority_queue_text_push_timing_test"> | |
133 <div id="NBRG_pq"> | |
134 <div id="NBRG_Native_and__tt_pb_ds_455tt__pairing_priority_queue__tt_push_455tt_
_timing_test"><div style="border-style: dotted; border-width: 1px; border-color:
lightgray"><h6 class="c1"><a name="NBRG" id="NBRG"><img src="pairing_priority_q
ueue_text_push_timing_test_gcc.png" alt="no image" /></a></h6>NBRG: Native and <
tt>pb ds</tt> pairing priority queue <tt>push</tt> timing test - <a href="pq_per
formance_tests.html#gcc">g++</a><p>In the above figure, the names in the legends
have the following meaning:</p> | |
135 <ol> | |
136 <li> | |
137 n_pq_vector- | |
138 <tt>std::priority_queue</tt> adapting <tt>std::vector</tt></li> | |
139 <li> | |
140 n_pq_deque- | |
141 <tt>std::priority_queue</tt> adapting <tt>std::deque</tt></li> | |
142 <li> | |
143 thin_heap- | |
144 <a href="priority_queue.html"><tt>priority_queue</tt></a> | |
145 with <tt>Tag</tt> = <a href="thin_heap_tag.html"><tt>thin_heap_tag</tt></a> | |
146 </li> | |
147 <li> | |
148 pairing_heap- | |
149 <a href="priority_queue.html"><tt>priority_queue</tt></a> | |
150 with <tt>Tag</tt> = <a href="pairing_heap_tag.html"><tt>pairing_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="NBRM_res_div"> | |
159 <div id="NBRM_msvc"> | |
160 <div id="NBRM_pairing_priority_queue_text_push_timing_test"> | |
161 <div id="NBRM_pq"> | |
162 <div id="NBRM_Native_and__tt_pb_ds_455tt__pairing_priority_queue__tt_push_455tt_
_timing_test"><div style="border-style: dotted; border-width: 1px; border-color:
lightgray"><h6 class="c1"><a name="NBRM" id="NBRM"><img src="pairing_priority_q
ueue_text_push_timing_test_msvc.png" alt="no image" /></a></h6>NBRM: Native and
<tt>pb ds</tt> pairing priority queue <tt>push</tt> timing test - <a href="pq_pe
rformance_tests.html#msvc">msvc++</a><p>In the above figure, the names in the le
gends have the following meaning:</p> | |
163 <ol> | |
164 <li> | |
165 n_pq_deque- | |
166 <tt>std::priority_queue</tt> adapting <tt>std::deque</tt></li> | |
167 <li> | |
168 n_pq_vector- | |
169 <tt>std::priority_queue</tt> adapting <tt>std::vector</tt></li> | |
170 <li> | |
171 pairing_heap- | |
172 <a href="priority_queue.html"><tt>priority_queue</tt></a> | |
173 with <tt>Tag</tt> = <a href="pairing_heap_tag.html"><tt>pairing_heap_tag</tt></
a> | |
174 </li> | |
175 <li> | |
176 thin_heap- | |
177 <a href="priority_queue.html"><tt>priority_queue</tt></a> | |
178 with <tt>Tag</tt> = <a href="thin_heap_tag.html"><tt>thin_heap_tag</tt></a> | |
179 </li> | |
180 </ol> | |
181 </div><div style="width: 100%; height: 20px"></div></div> | |
182 </div> | |
183 </div> | |
184 </div> | |
185 </div> | |
186 <div id="NBRL_res_div"> | |
187 <div id="NBRL_local"> | |
188 <div id="NBRL_pairing_priority_queue_text_push_timing_test"> | |
189 <div id="NBRL_pq"> | |
190 <div id="NBRL_Native_and__tt_pb_ds_455tt__pairing_priority_queue__tt_push_455tt_
_timing_test"><div style = "border-style: dotted; border-width: 1px; border-colo
r: lightgray"><h6 class="c1"><a name="NBRL" id= "NBRL"><img src="pairing_priorit
y_queue_text_push_timing_test_local.png" alt="no image" /></a></h6>NBRL: Native
and <tt>pb ds</tt> pairing priority queue <tt>push</tt> timing test - <a href =
"pq_performance_tests.html#local">local</a></div><div style = "width: 100%; heig
ht: 20px"></div></div> | |
191 </div> | |
192 </div> | |
193 </div> | |
194 </div> | |
195 <h2><a name="observations" id="observations">Observations</a></h2> | |
196 <p>Pairing heaps (<a href="priority_queue.html"><tt>priority_queue</tt></a> with | |
197 <tt>Tag</tt> = <a href="pairing_heap_tag.html"><tt>pairing_heap_tag</tt></a>
) | |
198 are the most suited for sequences of <tt>push</tt> and | |
199 <tt>pop</tt> operations of non-primitive types (<i>e.g.</i> | |
200 <tt>std::string</tt>s). (see also <a href="priority_queue_text_push_pop_timing_t
est.html">Priority Queue | |
201 Text <tt>push</tt> and <tt>pop</tt> Timing Test</a>.) They are | |
202 less constrained than binomial heaps, <i>e.g.</i>, and since | |
203 they are node-based, they outperform binary heaps. (See | |
204 <a href="priority_queue_random_int_push_timing_test.html">Priority | |
205 Queue Random Integer <tt>push</tt> Timing Test</a> for the case | |
206 of primitive types.)</p> | |
207 <p>The STL's priority queues do not seem to perform well in | |
208 this case: the <tt>std::vector</tt> implementation needs to | |
209 perform a logarithmic sequence of string operations for each | |
210 operation, and the deque implementation is possibly hampered by | |
211 its need to manipulate a relatively-complex type (deques | |
212 support a <i>O(1)</i> <tt>push_front</tt>, even though it is | |
213 not used by <tt>std::priority_queue</tt>.)</p> | |
214 <p><a href="pq_performance_tests.html#pq_observations">Priority-Queue | |
215 Performance Tests::Observations</a> discusses this further and | |
216 summarizes.</p> | |
217 </div> | |
218 </body> | |
219 </html> | |
OLD | NEW |