timeDSFvariants.cpp
Go to the documentation of this file.
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 
19 #include <gtsam/base/timing.h>
20 #include <gtsam/base/DSFVector.h>
22 #include <gtsam/base/DSFMap.h>
23 
24 #include <fstream>
25 #include <iostream>
26 #include <random>
27 #include <vector>
28 #include <utility>
29 
30 using namespace std;
31 using namespace gtsam;
32 
33 int 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(nm);
60  for (size_t k = 0; k < nm; k++)
61  matches.push_back(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(m.first, 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(m.first, 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(j);
102  for(const Match& m: matches)
103  dsf = dsf.makeUnion(m.first, 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(j);
119  for(const Match& m: matches)
120  dsf.makeUnionInPlace(m.first, 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 }
Matrix3f m
#define tictoc_getNode(variable, label)
Definition: timing.h:276
#define gttic_(label)
Definition: timing.h:245
void tictoc_reset_()
Definition: timing.h:282
void merge(const KEY &x, const KEY &y)
Merge two sets.
Definition: DSFMap.h:87
static std::mt19937 rng
int n
void makeSetInPlace(const KEY &key)
Definition: DSF.h:80
Definition: BFloat16.h:88
static const double ms
#define N
Definition: gksort.c:12
A faster implementation for DSF, which uses vector rather than btree.
void makeUnionInPlace(const KEY &key1, const KEY &key2)
Definition: DSF.h:99
Self makeUnion(const KEY &key1, const KEY &key2) const
Definition: DSF.h:92
Self makeSet(const KEY &key) const
Definition: DSF.h:72
An implementation of Disjoint set forests (see CLR page 446 and up)
int main(int argc, char *argv[])
traits
Definition: chartTesting.h:28
ofstream os("timeSchurFactors.csv")
void merge(const size_t &i1, const size_t &i2)
Merge the sets containing i1 and i2. Does nothing if i1 and i2 are already in the same set...
Definition: DSFVector.cpp:54
Allow for arbitrary type in DSF.
#define gttoc_(label)
Definition: timing.h:250
std::ptrdiff_t j
Timing utilities.
Definition: DSF.h:39


gtsam
Author(s):
autogenerated on Tue Jul 4 2023 02:40:01