1/* ----------------------------------------------------------------------------
2
3 * GTSAM Copyright 2010, Georgia Tech Research Corporation,
4 * Atlanta, Georgia 30332-0415
5 * All Rights Reserved
6 * Authors: Frank Dellaert, et al. (see THANKS for the full author list)
7
8 * See LICENSE for the license information
9
10 * -------------------------------------------------------------------------- */
11
12/**
13 * @file timeDSFvariants.cpp
14 * @brief Time different implementations of DSF
15 * @author Frank Dellaert
16 * @date Oct 26, 2013
17 */
18
19#include <gtsam/base/timing.h>
20#include <gtsam/base/DSFVector.h>
21#include <gtsam_unstable/base/DSF.h>
22#include <gtsam/base/DSFMap.h>
23
24#include <fstream>
25#include <iostream>
26#include <random>
27#include <vector>
28#include <utility>
29
30using namespace std;
31using namespace gtsam;
32
33int main(int argc, char* argv[]) {
34
35 // Create CSV file for results
36 ofstream os("dsf-timing.csv");
37 os << "images,points,matches,Base,Map,BTree" << endl;
38
39 // loop over number of images
40 vector<size_t> ms {10, 20, 30, 40, 50, 100, 200, 300, 400, 500, 1000};
41 for(size_t m: ms) {
42 // We use volatile here to make these appear to the optimizing compiler as
43 // if their values are only known at run-time.
44 volatile size_t n = 500; // number of points per image
45 volatile size_t N = m * n; // number of points per image
46
47 volatile double fm = 0.1; // fraction of image pairs matched
48 volatile size_t np = fm * m * m / 2; // number of image pairs
49 volatile double fpm = 0.5; // fraction of points matched
50 volatile size_t nm = fpm * n * np; // number of matches
51
52 cout << "\nTesting with " << (int)m << " images, " << (int)N << " points, " << (int)nm << " matches\n";
53 cout << "Generating " << nm << " matches" << endl;
54 std::mt19937 rng;
55 std::uniform_int_distribution<> rn(0, N - 1);
56
57 typedef pair<size_t, size_t> Match;
58 vector<Match> matches;
59 matches.reserve(n: nm);
60 for (size_t k = 0; k < nm; k++)
61 matches.push_back(x: Match(rn(rng), rn(rng)));
62
63 os << (int)m << "," << (int)N << "," << (int)nm << ",";
64
65 {
66 // DSFBase version
67 double dsftime = 0;
68 gttic_(dsftime);
69 DSFBase dsf(N); // Allow for N keys
70 for(const Match& m: matches)
71 dsf.merge(i1: m.first, i2: m.second);
72 gttoc_(dsftime);
73 tictoc_getNode(dsftimeNode, dsftime);
74 dsftime = dsftimeNode->secs();
75 os << dsftime << ",";
76 cout << "DSFBase: " << dsftime << " s" << endl;
77 tictoc_reset_();
78 }
79
80 {
81 // DSFMap version
82 double dsftime = 0;
83 gttic_(dsftime);
84 DSFMap<size_t> dsf;
85 for(const Match& m: matches)
86 dsf.merge(x: m.first, y: m.second);
87 gttoc_(dsftime);
88 tictoc_getNode(dsftimeNode, dsftime);
89 dsftime = dsftimeNode->secs();
90 os << dsftime << endl;
91 cout << "DSFMap: " << dsftime << " s" << endl;
92 tictoc_reset_();
93 }
94
95 if (false) {
96 // DSF version, functional
97 double dsftime = 0;
98 gttic_(dsftime);
99 DSF<size_t> dsf;
100 for (size_t j = 0; j < N; j++)
101 dsf = dsf.makeSet(key: j);
102 for(const Match& m: matches)
103 dsf = dsf.makeUnion(key1: m.first, key2: m.second);
104 gttoc_(dsftime);
105 tictoc_getNode(dsftimeNode, dsftime);
106 dsftime = dsftimeNode->secs();
107 os << dsftime << endl;
108 cout << "DSF functional: " << dsftime << " s" << endl;
109 tictoc_reset_();
110 }
111
112 if (false) {
113 // DSF version, in place - always slower - use functional !
114 double dsftime = 0;
115 gttic_(dsftime);
116 DSF<size_t> dsf;
117 for (size_t j = 0; j < N; j++)
118 dsf.makeSetInPlace(key: j);
119 for(const Match& m: matches)
120 dsf.makeUnionInPlace(key1: m.first, key2: m.second);
121 gttoc_(dsftime);
122 tictoc_getNode(dsftimeNode, dsftime);
123 dsftime = dsftimeNode->secs();
124 os << dsftime << ",";
125 cout << "DSF in-place: " << dsftime << " s" << endl;
126 tictoc_reset_();
127 }
128
129 }
130
131 return 0;
132
133}
134