From 3f4a00a7c37d4269eb3518665b8bc733e46fef12 Mon Sep 17 00:00:00 2001 From: glisse Date: Tue, 28 Mar 2017 17:37:28 +0000 Subject: Replace list with vector, save 30% of the running time... git-svn-id: svn+ssh://scm.gforge.inria.fr/svnroot/gudhi/branches/bottleneck-glisse@2265 636b058d-ea47-450e-bf9e-a15bfbe3eedb Former-commit-id: 92ba2895af0715166924abdc1600f20665c76af4 --- src/Bottleneck_distance/include/gudhi/Graph_matching.h | 12 +++++++----- 1 file changed, 7 insertions(+), 5 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 eed3e5ea..2278d858 100644 --- a/src/Bottleneck_distance/include/gudhi/Graph_matching.h +++ b/src/Bottleneck_distance/include/gudhi/Graph_matching.h @@ -26,7 +26,7 @@ #include #include -#include +#include namespace Gudhi { @@ -53,7 +53,7 @@ class Graph_matching { /** \internal \brief Given a point from V, provides its matched point in U, null_point_index() if there isn't. */ std::vector v_to_u; /** \internal \brief All the unmatched points in U. */ - std::list unmatched_in_u; + std::vector unmatched_in_u; /** \internal \brief Provides a Layered_neighbors_finder dividing the graph in layers. Basically a BFS. */ Layered_neighbors_finder layering() const; @@ -83,7 +83,7 @@ inline bool Graph_matching::multi_augment() { if (max_depth < 0 || (unmatched_in_u.size() > rn && max_depth >= rn)) return false; bool successful = false; - std::vector tries(unmatched_in_u.cbegin(), unmatched_in_u.cend()); + std::vector tries(unmatched_in_u); for (auto it = tries.cbegin(); it != tries.cend(); it++) // 'augment' has side-effects which have to be always executed, don't change order successful = augment(layered_nf, *it, max_depth) || successful; @@ -123,7 +123,7 @@ inline bool Graph_matching::augment(Layered_neighbors_finder & layered_nf, int u } inline Layered_neighbors_finder Graph_matching::layering() const { - std::vector u_vertices(unmatched_in_u.cbegin(), unmatched_in_u.cend()); + std::vector u_vertices(unmatched_in_u); std::vector v_vertices; Neighbors_finder nf(*gp, r); for (int v_point_index = 0; v_point_index < gp->size(); ++v_point_index) @@ -156,7 +156,9 @@ inline Layered_neighbors_finder Graph_matching::layering() const { } inline void Graph_matching::update(std::vector& path) { - unmatched_in_u.remove(path.front()); + //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()); 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