/
mst_benchmark.cpp
61 lines (53 loc) · 2.01 KB
/
mst_benchmark.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#include "benchmark/benchmark.h"
#include "../boruvka/boruvka.hpp"
#include "../graph_utils/graph_utils.hpp"
#include "../kkt/kkt.hpp"
#include "../kruskal/kruskal.hpp"
#include "../prim/prim.hpp"
#include <cmath>
static void bm_boruvka(benchmark::State& state)
{
auto G = build_random_connected_graph(state.range(0), state.range(1));
for (auto _: state)
{ benchmark::DoNotOptimize(boruvka(G, state.range(0))); }
state.SetComplexityN(state.range(0) + state.range(1));
}
static void bm_kkt(benchmark::State& state)
{
auto G = build_random_connected_graph(state.range(0), state.range(1));
auto P = problem(state.range(0), G);
for (auto _: state) { benchmark::DoNotOptimize(kkt(P)); }
state.SetComplexityN(state.range(0) + state.range(1));
}
static void bm_kruskal(benchmark::State& state)
{
auto G = build_random_connected_graph(state.range(0), state.range(1));
for (auto _: state)
{ benchmark::DoNotOptimize(kruskal(G, state.range(0))); }
state.SetComplexityN(state.range(0) + state.range(1));
}
static void bm_prim(benchmark::State& state)
{
auto G = build_random_connected_graph(state.range(0), state.range(1));
for (auto _: state) { benchmark::DoNotOptimize(prim(G, state.range(0))); }
state.SetComplexityN(state.range(0) + state.range(1));
}
static void CustomArguments(benchmark::internal::Benchmark* b)
{
b->Args({10000, 1250000});
b->Args({10000, 2500000});
b->Args({10000, 5000000});
b->Args({10000, 10000000});
b->Args({10000, 20000000});
}
BENCHMARK(bm_boruvka)->Apply(CustomArguments)->Complexity();
BENCHMARK(bm_kkt)->Apply(CustomArguments)->Complexity();
BENCHMARK(bm_kruskal)->Apply(CustomArguments)->Complexity();
BENCHMARK(bm_prim)->Apply(CustomArguments)->Complexity();
/*
BENCHMARK(bm_boruvka)->Ranges({{2048, 2048}, {1 << 13, 1 << 16}})->Complexity();
BENCHMARK(bm_kkt)->Ranges({{2048, 2048}, {1 << 13, 1 << 16}})->Complexity();
BENCHMARK(bm_kruskal)->Ranges({{2048, 2048}, {1 << 13, 1 << 16}})->Complexity();
BENCHMARK(bm_prim)->Ranges({{2048, 2048}, {1 << 13, 1 << 16}})->Complexity();
*/
BENCHMARK_MAIN();