1 /*=============================================================================
2 Copyright (c) 2010 Tim Blechmann
3
4 Use, modification and distribution is subject to the Boost Software
5 License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
6 http://www.boost.org/LICENSE_1_0.txt)
7 =============================================================================*/
8
9 #include <iostream>
10 #include <iomanip>
11
12
13 #include "../../../boost/heap/d_ary_heap.hpp"
14 #include "../../../boost/heap/pairing_heap.hpp"
15 #include "../../../boost/heap/fibonacci_heap.hpp"
16 #include "../../../boost/heap/binomial_heap.hpp"
17 #include "../../../boost/heap/skew_heap.hpp"
18
19 #include "heap_benchmarks.hpp"
20
21 using namespace std;
22
23 template <typename benchmark_selector>
run_benchmarks_immutable(void)24 void run_benchmarks_immutable(void)
25 {
26 for (int i = 4; i != max_data; ++i) {
27 for (int j = 0; j != 8; ++j) {
28 int size = 1<<i;
29 if (j%4 == 1)
30 size += 1<<(i-3);
31 if (j%4 == 2)
32 size += 1<<(i-2);
33 if (j%4 == 3)
34 size += (1<<(i-3)) + (1<<(i-2));
35 if (j >= 4)
36 size += (1<<(i-1));
37
38 cout << size << "\t";
39 {
40 typedef typename benchmark_selector::
41 template rebind<boost::heap::d_ary_heap<long, boost::heap::arity<2> > >
42 ::type benchmark_functor;
43 benchmark_functor benchmark(size);
44 double result = run_benchmark(benchmark);
45 cout << result << '\t';
46 }
47
48 {
49 typedef typename benchmark_selector::
50 template rebind<boost::heap::d_ary_heap<long, boost::heap::arity<2>, boost::heap::mutable_<true> > >
51 ::type benchmark_functor;
52 benchmark_functor benchmark(size);
53 double result = run_benchmark(benchmark);
54 cout << result << '\t';
55 }
56
57 {
58 typedef typename benchmark_selector::
59 template rebind<boost::heap::d_ary_heap<long, boost::heap::arity<4> > >
60 ::type benchmark_functor;
61 benchmark_functor benchmark(size);
62 double result = run_benchmark(benchmark);
63 cout << result << '\t';
64 }
65
66 {
67 typedef typename benchmark_selector::
68 template rebind<boost::heap::d_ary_heap<long, boost::heap::arity<4>, boost::heap::mutable_<true> > >
69 ::type benchmark_functor;
70 benchmark_functor benchmark(size);
71 double result = run_benchmark(benchmark);
72 cout << result << '\t';
73 }
74
75 {
76 typedef typename benchmark_selector::
77 template rebind<boost::heap::d_ary_heap<long, boost::heap::arity<8> > >
78 ::type benchmark_functor;
79 benchmark_functor benchmark(size);
80 double result = run_benchmark(benchmark);
81 cout << result << '\t';
82 }
83
84 {
85 typedef typename benchmark_selector::
86 template rebind<boost::heap::d_ary_heap<long, boost::heap::arity<8>, boost::heap::mutable_<true> > >
87 ::type benchmark_functor;
88 benchmark_functor benchmark(size);
89 double result = run_benchmark(benchmark);
90 cout << result << '\t';
91 }
92
93 {
94 typedef typename benchmark_selector::
95 template rebind<boost::heap::binomial_heap<long> >
96 ::type benchmark_functor;
97 benchmark_functor benchmark(size);
98 double result = run_benchmark(benchmark);
99 cout << result << '\t';
100 }
101
102 {
103 typedef typename benchmark_selector::
104 template rebind<boost::heap::fibonacci_heap<long> >
105 ::type benchmark_functor;
106 benchmark_functor benchmark(size);
107 double result = run_benchmark(benchmark);
108 cout << result << '\t';
109 }
110
111 {
112 typedef typename benchmark_selector::
113 template rebind<boost::heap::pairing_heap<long> >
114 ::type benchmark_functor;
115 benchmark_functor benchmark(size);
116 double result = run_benchmark(benchmark);
117 cout << result << '\t';
118 }
119
120 {
121 typedef typename benchmark_selector::
122 template rebind<boost::heap::skew_heap<long> >
123 ::type benchmark_functor;
124 benchmark_functor benchmark(size);
125 double result = run_benchmark(benchmark);
126 cout << result << '\t';
127 }
128
129 {
130 typedef typename benchmark_selector::
131 template rebind<boost::heap::skew_heap<long> >
132 ::type benchmark_functor;
133 benchmark_functor benchmark(size);
134 double result = run_benchmark(benchmark);
135 cout << result << '\t';
136 }
137 cout << endl;
138 }
139 }
140 }
141
142 template <typename benchmark_selector>
run_benchmarks_mutable(void)143 void run_benchmarks_mutable(void)
144 {
145 for (int i = 4; i != max_data; ++i)
146 {
147 for (int j = 0; j != 8; ++j)
148 {
149 int size = 1<<i;
150 if (j%4 == 1)
151 size += 1<<(i-3);
152 if (j%4 == 2)
153 size += 1<<(i-2);
154 if (j%4 == 3)
155 size += (1<<(i-3)) + (1<<(i-2));
156 if (j >= 4)
157 size += (1<<(i-1));
158
159 cout << size << "\t";
160 {
161 typedef typename benchmark_selector::
162 template rebind<boost::heap::d_ary_heap<long, boost::heap::arity<2>, boost::heap::mutable_<true> > >
163 ::type benchmark_functor;
164 benchmark_functor benchmark(size);
165 double result = run_benchmark(benchmark);
166 cout << result << '\t';
167 }
168
169 {
170 typedef typename benchmark_selector::
171 template rebind<boost::heap::d_ary_heap<long, boost::heap::arity<4>, boost::heap::mutable_<true> > >
172 ::type benchmark_functor;
173 benchmark_functor benchmark(size);
174 double result = run_benchmark(benchmark);
175 cout << result << '\t';
176 }
177
178 {
179 typedef typename benchmark_selector::
180 template rebind<boost::heap::d_ary_heap<long, boost::heap::arity<8>, boost::heap::mutable_<true> > >
181 ::type benchmark_functor;
182 benchmark_functor benchmark(size);
183 double result = run_benchmark(benchmark);
184 cout << result << '\t';
185 }
186
187 {
188 typedef typename benchmark_selector::
189 template rebind<boost::heap::binomial_heap<long> >
190 ::type benchmark_functor;
191 benchmark_functor benchmark(size);
192 double result = run_benchmark(benchmark);
193 cout << result << '\t';
194 }
195
196 {
197 typedef typename benchmark_selector::
198 template rebind<boost::heap::fibonacci_heap<long> >
199 ::type benchmark_functor;
200 benchmark_functor benchmark(size);
201 double result = run_benchmark(benchmark);
202 cout << result << '\t';
203 }
204
205 {
206 typedef typename benchmark_selector::
207 template rebind<boost::heap::pairing_heap<long> >
208 ::type benchmark_functor;
209 benchmark_functor benchmark(size);
210 double result = run_benchmark(benchmark);
211 cout << result << '\t';
212 }
213
214 {
215 typedef typename benchmark_selector::
216 template rebind<boost::heap::skew_heap<long, boost::heap::mutable_<true> > >
217 ::type benchmark_functor;
218 benchmark_functor benchmark(size);
219 double result = run_benchmark(benchmark);
220 cout << result << '\t';
221 }
222 cout << endl;
223 }
224 }
225 }
226
main()227 int main()
228 {
229 cout << fixed << setprecision(12);
230
231 cout << "sequential push" << endl;
232 run_benchmarks_immutable<make_sequential_push>();
233
234 cout << endl << "sequential pop" << endl;
235 run_benchmarks_immutable<make_sequential_pop>();
236
237 cout << endl << "sequential increase" << endl;
238 run_benchmarks_mutable<make_sequential_increase>();
239
240 cout << endl << "sequential decrease" << endl;
241 run_benchmarks_mutable<make_sequential_decrease>();
242
243 cout << endl << "merge_and_clear" << endl;
244 run_benchmarks_immutable<make_merge_and_clear>();
245
246 cout << endl << "equivalence" << endl;
247 run_benchmarks_immutable<make_equivalence>();
248 }
249