From fc91de9f736c13f38d096fc1da78c688e7992fe7 Mon Sep 17 00:00:00 2001 From: glisse Date: Wed, 11 Nov 2015 21:25:38 +0000 Subject: Make annotations_in_boundary a vector, sorted once after construction, with entries sharing the same annotation accumulated as we go. git-svn-id: svn+ssh://scm.gforge.inria.fr/svnroot/gudhi/branches/annotations_in_boundary@909 636b058d-ea47-450e-bf9e-a15bfbe3eedb Former-commit-id: 34b2ae74dc017c18a90e08caee6f707b6b0d4cc2 --- .../include/gudhi/Persistent_cohomology.h | 33 ++++++++++++++-------- 1 file changed, 22 insertions(+), 11 deletions(-) (limited to 'src/Persistent_cohomology/include') diff --git a/src/Persistent_cohomology/include/gudhi/Persistent_cohomology.h b/src/Persistent_cohomology/include/gudhi/Persistent_cohomology.h index d096792f..3875afc6 100644 --- a/src/Persistent_cohomology/include/gudhi/Persistent_cohomology.h +++ b/src/Persistent_cohomology/include/gudhi/Persistent_cohomology.h @@ -431,9 +431,13 @@ class Persistent_cohomology { std::map & map_a_ds, Simplex_handle sigma, int dim_sigma) { // traverses the boundary of sigma, keeps track of the annotation vectors, - // with multiplicity, in a map. - std::map annotations_in_boundary; - std::pair::iterator, bool> result_insert_bound; + // with multiplicity. +#if 0 + std::vector> annotations_in_boundary; +#else + static std::vector> annotations_in_boundary; + annotations_in_boundary.clear(); +#endif int sign = 1 - 2 * (dim_sigma % 2); // \in {-1,1} provides the sign in the // alternate sum in the boundary. Simplex_key key; @@ -445,22 +449,29 @@ class Persistent_cohomology { // Find its annotation vector curr_col = ds_repr_[dsets_.find_set(key)]; if (curr_col != NULL) { // and insert it in annotations_in_boundary with multyiplicative factor "sign". - result_insert_bound = annotations_in_boundary.insert(std::pair(curr_col, sign)); - if (!(result_insert_bound.second)) { - result_insert_bound.first->second += sign; - } + annotations_in_boundary.emplace_back(curr_col, sign); } } sign = -sign; } + std::sort(annotations_in_boundary.begin(),annotations_in_boundary.end(),[](auto&a,auto&b){return a.first // to represent a sparse vector. std::pair::iterator, bool> result_insert_a_ds; - for (auto ann_ref : annotations_in_boundary) { - if (ann_ref.second != coeff_field_.additive_identity()) { // For all columns in the boundary, - for (auto cell_ref : ann_ref.first->col_) { // insert every cell in map_a_ds with multiplicity - Arith_element w_y = coeff_field_.times(cell_ref.coefficient_, ann_ref.second); // coefficient * multiplicity + auto ann_it = annotations_in_boundary.begin(); + while (ann_it != annotations_in_boundary.end()) { + auto col = ann_it->first; + int coef = ann_it->second; + for (;;) { + if (++ann_it == annotations_in_boundary.end() || ann_it->first != col) + break; + coef += ann_it->second; + } + // The following test is just a heuristic, it is not required, and it is fine that is misses p == 0. + if (coef != coeff_field_.additive_identity()) { // For all columns in the boundary, + for (auto cell_ref : col->col_) { // insert every cell in map_a_ds with multiplicity + Arith_element w_y = coeff_field_.times(cell_ref.coefficient_, coef); // coefficient * multiplicity if (w_y != coeff_field_.additive_identity()) { // if != 0 result_insert_a_ds = map_a_ds.insert(std::pair(cell_ref.key_, w_y)); -- cgit v1.2.3 From ccf7f9e5b8840f57c68dec83e2153c3cc5804b61 Mon Sep 17 00:00:00 2001 From: glisse Date: Fri, 13 Nov 2015 20:07:20 +0000 Subject: Clean-up. git-svn-id: svn+ssh://scm.gforge.inria.fr/svnroot/gudhi/branches/annotations_in_boundary@912 636b058d-ea47-450e-bf9e-a15bfbe3eedb Former-commit-id: f5652acf2ed5eb6f11428d2907963b5d1a1359be --- .../include/gudhi/Persistent_cohomology.h | 29 +++++++++++----------- 1 file changed, 15 insertions(+), 14 deletions(-) (limited to 'src/Persistent_cohomology/include') diff --git a/src/Persistent_cohomology/include/gudhi/Persistent_cohomology.h b/src/Persistent_cohomology/include/gudhi/Persistent_cohomology.h index 3875afc6..2d6a85c1 100644 --- a/src/Persistent_cohomology/include/gudhi/Persistent_cohomology.h +++ b/src/Persistent_cohomology/include/gudhi/Persistent_cohomology.h @@ -431,13 +431,14 @@ class Persistent_cohomology { std::map & map_a_ds, Simplex_handle sigma, int dim_sigma) { // traverses the boundary of sigma, keeps track of the annotation vectors, - // with multiplicity. -#if 0 - std::vector> annotations_in_boundary; -#else - static std::vector> annotations_in_boundary; - annotations_in_boundary.clear(); -#endif + // with multiplicity. We used to sum the coefficients directly in + // annotations_in_boundary by using a map, we now do it later. + typedef std::pair annotation_t; + std::vector annotations_in_boundary; + /* A small speed boost is possible with the following non-thread-safe: + static std::vector> annotations_in_boundary; + annotations_in_boundary.clear(); + */ int sign = 1 - 2 * (dim_sigma % 2); // \in {-1,1} provides the sign in the // alternate sum in the boundary. Simplex_key key; @@ -454,18 +455,18 @@ class Persistent_cohomology { } sign = -sign; } - std::sort(annotations_in_boundary.begin(),annotations_in_boundary.end(),[](auto&a,auto&b){return a.first // to represent a sparse vector. std::pair::iterator, bool> result_insert_a_ds; - auto ann_it = annotations_in_boundary.begin(); - while (ann_it != annotations_in_boundary.end()) { - auto col = ann_it->first; + for (auto ann_it = annotations_in_boundary.begin(); ann_it != annotations_in_boundary.end(); /**/) { + Column* col = ann_it->first; int coef = ann_it->second; - for (;;) { - if (++ann_it == annotations_in_boundary.end() || ann_it->first != col) - break; + while (++ann_it != annotations_in_boundary.end() && ann_it->first == col) { coef += ann_it->second; } // The following test is just a heuristic, it is not required, and it is fine that is misses p == 0. -- cgit v1.2.3 From 32a6d46672102e17f7ae09fe130382aa7e487884 Mon Sep 17 00:00:00 2001 From: glisse Date: Fri, 13 Nov 2015 20:14:03 +0000 Subject: Rename variable. git-svn-id: svn+ssh://scm.gforge.inria.fr/svnroot/gudhi/branches/annotations_in_boundary@913 636b058d-ea47-450e-bf9e-a15bfbe3eedb Former-commit-id: 0afbcbee5739c1649d1c9b968d9f0748c7d1d219 --- src/Persistent_cohomology/include/gudhi/Persistent_cohomology.h | 8 ++++---- 1 file changed, 4 insertions(+), 4 deletions(-) (limited to 'src/Persistent_cohomology/include') diff --git a/src/Persistent_cohomology/include/gudhi/Persistent_cohomology.h b/src/Persistent_cohomology/include/gudhi/Persistent_cohomology.h index 2d6a85c1..1d8c2ca2 100644 --- a/src/Persistent_cohomology/include/gudhi/Persistent_cohomology.h +++ b/src/Persistent_cohomology/include/gudhi/Persistent_cohomology.h @@ -465,14 +465,14 @@ class Persistent_cohomology { for (auto ann_it = annotations_in_boundary.begin(); ann_it != annotations_in_boundary.end(); /**/) { Column* col = ann_it->first; - int coef = ann_it->second; + int mult = ann_it->second; while (++ann_it != annotations_in_boundary.end() && ann_it->first == col) { - coef += ann_it->second; + mult += ann_it->second; } // The following test is just a heuristic, it is not required, and it is fine that is misses p == 0. - if (coef != coeff_field_.additive_identity()) { // For all columns in the boundary, + if (mult != coeff_field_.additive_identity()) { // For all columns in the boundary, for (auto cell_ref : col->col_) { // insert every cell in map_a_ds with multiplicity - Arith_element w_y = coeff_field_.times(cell_ref.coefficient_, coef); // coefficient * multiplicity + Arith_element w_y = coeff_field_.times(cell_ref.coefficient_, mult); // coefficient * multiplicity if (w_y != coeff_field_.additive_identity()) { // if != 0 result_insert_a_ds = map_a_ds.insert(std::pair(cell_ref.key_, w_y)); -- cgit v1.2.3 From bdb1e5517822d935da93d83c8950cbbd11560698 Mon Sep 17 00:00:00 2001 From: glisse Date: Fri, 13 Nov 2015 20:27:56 +0000 Subject: Using a static variable really helps. git-svn-id: svn+ssh://scm.gforge.inria.fr/svnroot/gudhi/branches/annotations_in_boundary@914 636b058d-ea47-450e-bf9e-a15bfbe3eedb Former-commit-id: 695a6f642399c2646e5a26fac20173fbd57fe160 --- src/Persistent_cohomology/include/gudhi/Persistent_cohomology.h | 8 +++----- 1 file changed, 3 insertions(+), 5 deletions(-) (limited to 'src/Persistent_cohomology/include') diff --git a/src/Persistent_cohomology/include/gudhi/Persistent_cohomology.h b/src/Persistent_cohomology/include/gudhi/Persistent_cohomology.h index 1d8c2ca2..609f40a2 100644 --- a/src/Persistent_cohomology/include/gudhi/Persistent_cohomology.h +++ b/src/Persistent_cohomology/include/gudhi/Persistent_cohomology.h @@ -434,11 +434,9 @@ class Persistent_cohomology { // with multiplicity. We used to sum the coefficients directly in // annotations_in_boundary by using a map, we now do it later. typedef std::pair annotation_t; - std::vector annotations_in_boundary; - /* A small speed boost is possible with the following non-thread-safe: - static std::vector> annotations_in_boundary; - annotations_in_boundary.clear(); - */ + // Danger: not thread-safe! + static std::vector annotations_in_boundary; + annotations_in_boundary.clear(); int sign = 1 - 2 * (dim_sigma % 2); // \in {-1,1} provides the sign in the // alternate sum in the boundary. Simplex_key key; -- cgit v1.2.3