From f7b1a4118e6ef5bd3f78f04f6808a77d3079a618 Mon Sep 17 00:00:00 2001 From: glisse Date: Tue, 28 Mar 2017 18:47:45 +0000 Subject: Different strategies to remove points from unmatched_in_u. git-svn-id: svn+ssh://scm.gforge.inria.fr/svnroot/gudhi/branches/bottleneck-glisse@2266 636b058d-ea47-450e-bf9e-a15bfbe3eedb Former-commit-id: 5ff3d02d50ed3f1be537070d2c840f7ba4c6b433 --- src/Bottleneck_distance/include/gudhi/Graph_matching.h | 16 +++++++++++++--- 1 file changed, 13 insertions(+), 3 deletions(-) (limited to 'src/Bottleneck_distance/include') diff --git a/src/Bottleneck_distance/include/gudhi/Graph_matching.h b/src/Bottleneck_distance/include/gudhi/Graph_matching.h index 2278d858..6e024146 100644 --- a/src/Bottleneck_distance/include/gudhi/Graph_matching.h +++ b/src/Bottleneck_distance/include/gudhi/Graph_matching.h @@ -65,6 +65,7 @@ class Graph_matching { inline Graph_matching::Graph_matching(Persistence_graph& g) : gp(&g), r(0.), v_to_u(g.size(), null_point_index()), unmatched_in_u() { + unmatched_in_u.reserve(g.size()); for (int u_point_index = 0; u_point_index < g.size(); ++u_point_index) unmatched_in_u.emplace_back(u_point_index); } @@ -156,9 +157,18 @@ inline Layered_neighbors_finder Graph_matching::layering() const { } inline void Graph_matching::update(std::vector& path) { - //TODO: if we don't care about the order in unmatched_in_u or if an element - //can only appear once in unmatched_in_u, we could remove more efficiently. - unmatched_in_u.erase(std::remove(unmatched_in_u.begin(), unmatched_in_u.end(), path.front()), unmatched_in_u.end()); +#if 0 + // Avoid an expensive erase in the middle of the vector, but break the ordering, so the search needs to be linear. + auto p = std::find(unmatched_in_u.begin(), unmatched_in_u.end(), path.front()); + assert(p != unmatched_in_u.end()); + std::swap(*p, unmatched_in_u.back()); + unmatched_in_u.pop_back(); +#else + // Take advantage of the vector being sorted, but pay an expensive erase to maintain the order. + auto p = std::lower_bound(unmatched_in_u.begin(), unmatched_in_u.end(), path.front()); + assert(p != unmatched_in_u.end() && *p == path.front()); + unmatched_in_u.erase(p); +#endif for (auto it = path.cbegin(); it != path.cend(); ++it) { // Be careful, the iterator is incremented twice each time int tmp = *it; -- cgit v1.2.3