You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@datasketches.apache.org by al...@apache.org on 2021/11/02 21:17:42 UTC
[datasketches-cpp] branch theta_reset created (now 7ea464f)
This is an automated email from the ASF dual-hosted git repository.
alsay pushed a change to branch theta_reset
in repository https://gitbox.apache.org/repos/asf/datasketches-cpp.git.
at 7ea464f reset sketch and union
This branch includes the following new commits:
new 7ea464f reset sketch and union
The 1 revisions listed above as "new" are entirely new to this
repository and will be described in separate emails. The revisions
listed as "add" were already present in the repository and have only
been added to this reference.
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@datasketches.apache.org
For additional commands, e-mail: commits-help@datasketches.apache.org
[datasketches-cpp] 01/01: reset sketch and union
Posted by al...@apache.org.
This is an automated email from the ASF dual-hosted git repository.
alsay pushed a commit to branch theta_reset
in repository https://gitbox.apache.org/repos/asf/datasketches-cpp.git
commit 7ea464f7974dfbd46c1fb359f3615b48c364cfe5
Author: AlexanderSaydakov <Al...@users.noreply.github.com>
AuthorDate: Tue Nov 2 14:16:14 2021 -0700
reset sketch and union
---
theta/include/theta_helpers.hpp | 15 +++++++++
theta/include/theta_intersection_base_impl.hpp | 10 +++---
theta/include/theta_set_difference_base_impl.hpp | 2 +-
theta/include/theta_sketch.hpp | 16 +++++----
theta/include/theta_sketch_impl.hpp | 11 +++++--
theta/include/theta_union.hpp | 7 +++-
theta/include/theta_union_base.hpp | 4 ++-
theta/include/theta_union_base_impl.hpp | 10 ++++--
theta/include/theta_union_impl.hpp | 13 +++++---
theta/include/theta_update_sketch_base.hpp | 9 +++---
theta/include/theta_update_sketch_base_impl.hpp | 41 ++++++++++++++++++------
theta/test/theta_sketch_test.cpp | 16 +++++++++
theta/test/theta_union_test.cpp | 34 +++++++++++++-------
tuple/include/array_of_doubles_sketch.hpp | 2 +-
tuple/include/array_of_doubles_sketch_impl.hpp | 6 ++--
tuple/include/array_of_doubles_union.hpp | 2 +-
tuple/include/array_of_doubles_union_impl.hpp | 6 ++--
tuple/include/tuple_sketch.hpp | 7 +++-
tuple/include/tuple_sketch_impl.hpp | 11 +++++--
tuple/include/tuple_union.hpp | 7 +++-
tuple/include/tuple_union_impl.hpp | 11 +++++--
tuple/test/array_of_doubles_sketch_test.cpp | 16 +++++++++
tuple/test/tuple_sketch_test.cpp | 10 ++++++
tuple/test/tuple_union_test.cpp | 7 ++++
24 files changed, 208 insertions(+), 65 deletions(-)
diff --git a/theta/include/theta_helpers.hpp b/theta/include/theta_helpers.hpp
index 6852590..76c1c23 100644
--- a/theta/include/theta_helpers.hpp
+++ b/theta/include/theta_helpers.hpp
@@ -49,6 +49,21 @@ public:
}
};
+template<bool dummy>
+class theta_build_helper{
+public:
+ // consistent way of initializing theta from p
+ // avoids multiplication if p == 1 since it might not yield MAX_THETA exactly
+ static uint64_t starting_theta_from_p(float p) {
+ if (p < 1) return static_cast<uint64_t>(theta_constants::MAX_THETA * p);
+ return theta_constants::MAX_THETA;
+ }
+
+ static uint8_t starting_sub_multiple(uint8_t lg_tgt, uint8_t lg_min, uint8_t lg_rf) {
+ return (lg_tgt <= lg_min) ? lg_min : (lg_rf == 0) ? lg_tgt : ((lg_tgt - lg_min) % lg_rf) + lg_min;
+ }
+};
+
} /* namespace datasketches */
#endif
diff --git a/theta/include/theta_intersection_base_impl.hpp b/theta/include/theta_intersection_base_impl.hpp
index 286f0ca..c5eed99 100644
--- a/theta/include/theta_intersection_base_impl.hpp
+++ b/theta/include/theta_intersection_base_impl.hpp
@@ -29,7 +29,7 @@ template<typename EN, typename EK, typename P, typename S, typename CS, typename
theta_intersection_base<EN, EK, P, S, CS, A>::theta_intersection_base(uint64_t seed, const P& policy, const A& allocator):
policy_(policy),
is_valid_(false),
-table_(0, 0, resize_factor::X1, theta_constants::MAX_THETA, seed, allocator, false)
+table_(0, 0, resize_factor::X1, 1, theta_constants::MAX_THETA, seed, allocator, false)
{}
template<typename EN, typename EK, typename P, typename S, typename CS, typename A>
@@ -42,13 +42,13 @@ void theta_intersection_base<EN, EK, P, S, CS, A>::update(SS&& sketch) {
if (is_valid_ && table_.num_entries_ == 0) return;
if (sketch.get_num_retained() == 0) {
is_valid_ = true;
- table_ = hash_table(0, 0, resize_factor::X1, table_.theta_, table_.seed_, table_.allocator_, table_.is_empty_);
+ table_ = hash_table(0, 0, resize_factor::X1, 1, table_.theta_, table_.seed_, table_.allocator_, table_.is_empty_);
return;
}
if (!is_valid_) { // first update, copy or move incoming sketch
is_valid_ = true;
const uint8_t lg_size = lg_size_from_count(sketch.get_num_retained(), theta_update_sketch_base<EN, EK, A>::REBUILD_THRESHOLD);
- table_ = hash_table(lg_size, lg_size, resize_factor::X1, table_.theta_, table_.seed_, table_.allocator_, table_.is_empty_);
+ table_ = hash_table(lg_size, lg_size, resize_factor::X1, 1, table_.theta_, table_.seed_, table_.allocator_, table_.is_empty_);
for (auto& entry: sketch) {
auto result = table_.find(EK()(entry));
if (result.second) {
@@ -83,11 +83,11 @@ void theta_intersection_base<EN, EK, P, S, CS, A>::update(SS&& sketch) {
throw std::invalid_argument(" fewer keys than expected, possibly corrupted input sketch");
}
if (match_count == 0) {
- table_ = hash_table(0, 0, resize_factor::X1, table_.theta_, table_.seed_, table_.allocator_, table_.is_empty_);
+ table_ = hash_table(0, 0, resize_factor::X1, 1, table_.theta_, table_.seed_, table_.allocator_, table_.is_empty_);
if (table_.theta_ == theta_constants::MAX_THETA) table_.is_empty_ = true;
} else {
const uint8_t lg_size = lg_size_from_count(match_count, theta_update_sketch_base<EN, EK, A>::REBUILD_THRESHOLD);
- table_ = hash_table(lg_size, lg_size, resize_factor::X1, table_.theta_, table_.seed_, table_.allocator_, table_.is_empty_);
+ table_ = hash_table(lg_size, lg_size, resize_factor::X1, 1, table_.theta_, table_.seed_, table_.allocator_, table_.is_empty_);
for (uint32_t i = 0; i < match_count; i++) {
auto result = table_.find(EK()(matched_entries[i]));
table_.insert(result.first, std::move(matched_entries[i]));
diff --git a/theta/include/theta_set_difference_base_impl.hpp b/theta/include/theta_set_difference_base_impl.hpp
index 4ab98a8..fbf4cdb 100644
--- a/theta/include/theta_set_difference_base_impl.hpp
+++ b/theta/include/theta_set_difference_base_impl.hpp
@@ -53,7 +53,7 @@ CS theta_set_difference_base<EN, EK, CS, A>::compute(FwdSketch&& a, const Sketch
conditional_back_inserter(entries, key_less_than<uint64_t, EN, EK>(theta)), comparator());
} else { // hash-based
const uint8_t lg_size = lg_size_from_count(b.get_num_retained(), hash_table::REBUILD_THRESHOLD);
- hash_table table(lg_size, lg_size, hash_table::resize_factor::X1, 0, 0, allocator_); // theta and seed are not used here
+ hash_table table(lg_size, lg_size, hash_table::resize_factor::X1, 1, 0, 0, allocator_); // theta and seed are not used here
for (const auto& entry: b) {
const uint64_t hash = EK()(entry);
if (hash < theta) {
diff --git a/theta/include/theta_sketch.hpp b/theta/include/theta_sketch.hpp
index f97d8d1..fa283b8 100644
--- a/theta/include/theta_sketch.hpp
+++ b/theta/include/theta_sketch.hpp
@@ -27,8 +27,6 @@ namespace datasketches {
template<typename Allocator = std::allocator<uint64_t>>
class base_theta_sketch_alloc {
public:
- using Entry = uint64_t;
- using ExtractKey = trivial_extract_key;
virtual ~base_theta_sketch_alloc() = default;
@@ -110,9 +108,8 @@ protected:
template<typename Allocator = std::allocator<uint64_t>>
class theta_sketch_alloc: public base_theta_sketch_alloc<Allocator> {
public:
- using Base = theta_sketch_alloc<Allocator>;
- using Entry = typename Base::Entry;
- using ExtractKey = typename Base::ExtractKey;
+ using Entry = uint64_t;
+ using ExtractKey = trivial_extract_key;
using iterator = theta_iterator<Entry, ExtractKey>;
using const_iterator = theta_const_iterator<Entry, ExtractKey>;
@@ -283,6 +280,11 @@ public:
void trim();
/**
+ * Reset the sketch to the initial empty state
+ */
+ void reset();
+
+ /**
* Converts this sketch to a compact sketch (ordered or unordered).
* @param ordered optional flag to specify if ordered sketch should be produced
* @return compact sketch
@@ -298,8 +300,8 @@ private:
theta_table table_;
// for builder
- update_theta_sketch_alloc(uint8_t lg_cur_size, uint8_t lg_nom_size, resize_factor rf, uint64_t theta,
- uint64_t seed, const Allocator& allocator);
+ update_theta_sketch_alloc(uint8_t lg_cur_size, uint8_t lg_nom_size, resize_factor rf, float p,
+ uint64_t theta, uint64_t seed, const Allocator& allocator);
virtual void print_specifics(std::ostringstream& os) const;
};
diff --git a/theta/include/theta_sketch_impl.hpp b/theta/include/theta_sketch_impl.hpp
index 342a05f..1efb4cd 100644
--- a/theta/include/theta_sketch_impl.hpp
+++ b/theta/include/theta_sketch_impl.hpp
@@ -95,8 +95,8 @@ void theta_sketch_alloc<A>::print_items(std::ostringstream& os) const {
template<typename A>
update_theta_sketch_alloc<A>::update_theta_sketch_alloc(uint8_t lg_cur_size, uint8_t lg_nom_size, resize_factor rf,
- uint64_t theta, uint64_t seed, const A& allocator):
-table_(lg_cur_size, lg_nom_size, rf, theta, seed, allocator)
+ float p, uint64_t theta, uint64_t seed, const A& allocator):
+table_(lg_cur_size, lg_nom_size, rf, p, theta, seed, allocator)
{}
template<typename A>
@@ -211,6 +211,11 @@ void update_theta_sketch_alloc<A>::trim() {
}
template<typename A>
+void update_theta_sketch_alloc<A>::reset() {
+ table_.reset();
+}
+
+template<typename A>
auto update_theta_sketch_alloc<A>::begin() -> iterator {
return iterator(table_.entries_, 1 << table_.lg_cur_size_, 0);
}
@@ -249,7 +254,7 @@ update_theta_sketch_alloc<A>::builder::builder(const A& allocator): theta_base_b
template<typename A>
update_theta_sketch_alloc<A> update_theta_sketch_alloc<A>::builder::build() const {
- return update_theta_sketch_alloc(this->starting_lg_size(), this->lg_k_, this->rf_, this->starting_theta(), this->seed_, this->allocator_);
+ return update_theta_sketch_alloc(this->starting_lg_size(), this->lg_k_, this->rf_, this->p_, this->starting_theta(), this->seed_, this->allocator_);
}
// compact sketch
diff --git a/theta/include/theta_union.hpp b/theta/include/theta_union.hpp
index 8504ffb..d90c53a 100644
--- a/theta/include/theta_union.hpp
+++ b/theta/include/theta_union.hpp
@@ -60,11 +60,16 @@ public:
*/
CompactSketch get_result(bool ordered = true) const;
+ /**
+ * Reset the union to the initial empty state
+ */
+ void reset();
+
private:
State state_;
// for builder
- theta_union_alloc(uint8_t lg_cur_size, uint8_t lg_nom_size, resize_factor rf, uint64_t theta, uint64_t seed, const Allocator& allocator);
+ theta_union_alloc(uint8_t lg_cur_size, uint8_t lg_nom_size, resize_factor rf, float p, uint64_t theta, uint64_t seed, const Allocator& allocator);
};
template<typename A>
diff --git a/theta/include/theta_union_base.hpp b/theta/include/theta_union_base.hpp
index d41f5bd..6da10b2 100644
--- a/theta/include/theta_union_base.hpp
+++ b/theta/include/theta_union_base.hpp
@@ -38,7 +38,7 @@ public:
using resize_factor = typename hash_table::resize_factor;
using comparator = compare_by_key<ExtractKey>;
- theta_union_base(uint8_t lg_cur_size, uint8_t lg_nom_size, resize_factor rf, uint64_t theta, uint64_t seed, const Policy& policy, const Allocator& allocator);
+ theta_union_base(uint8_t lg_cur_size, uint8_t lg_nom_size, resize_factor rf, float p, uint64_t theta, uint64_t seed, const Policy& policy, const Allocator& allocator);
template<typename FwdSketch>
void update(FwdSketch&& sketch);
@@ -47,6 +47,8 @@ public:
const Policy& get_policy() const;
+ void reset();
+
private:
Policy policy_;
hash_table table_;
diff --git a/theta/include/theta_union_base_impl.hpp b/theta/include/theta_union_base_impl.hpp
index 254bc44..ca6367a 100644
--- a/theta/include/theta_union_base_impl.hpp
+++ b/theta/include/theta_union_base_impl.hpp
@@ -28,9 +28,9 @@ namespace datasketches {
template<typename EN, typename EK, typename P, typename S, typename CS, typename A>
theta_union_base<EN, EK, P, S, CS, A>::theta_union_base(uint8_t lg_cur_size, uint8_t lg_nom_size, resize_factor rf,
- uint64_t theta, uint64_t seed, const P& policy, const A& allocator):
+ float p, uint64_t theta, uint64_t seed, const P& policy, const A& allocator):
policy_(policy),
-table_(lg_cur_size, lg_nom_size, rf, theta, seed, allocator),
+table_(lg_cur_size, lg_nom_size, rf, p, theta, seed, allocator),
union_theta_(table_.theta_)
{}
@@ -84,6 +84,12 @@ const P& theta_union_base<EN, EK, P, S, CS, A>::get_policy() const {
return policy_;
}
+template<typename EN, typename EK, typename P, typename S, typename CS, typename A>
+void theta_union_base<EN, EK, P, S, CS, A>::reset() {
+ table_.reset();
+ union_theta_ = table_.theta_;
+}
+
} /* namespace datasketches */
#endif
diff --git a/theta/include/theta_union_impl.hpp b/theta/include/theta_union_impl.hpp
index 1ccf4d4..8618618 100644
--- a/theta/include/theta_union_impl.hpp
+++ b/theta/include/theta_union_impl.hpp
@@ -23,8 +23,8 @@
namespace datasketches {
template<typename A>
-theta_union_alloc<A>::theta_union_alloc(uint8_t lg_cur_size, uint8_t lg_nom_size, resize_factor rf, uint64_t theta, uint64_t seed, const A& allocator):
-state_(lg_cur_size, lg_nom_size, rf, theta, seed, nop_policy(), allocator)
+theta_union_alloc<A>::theta_union_alloc(uint8_t lg_cur_size, uint8_t lg_nom_size, resize_factor rf, float p, uint64_t theta, uint64_t seed, const A& allocator):
+state_(lg_cur_size, lg_nom_size, rf, p, theta, seed, nop_policy(), allocator)
{}
template<typename A>
@@ -39,13 +39,16 @@ auto theta_union_alloc<A>::get_result(bool ordered) const -> CompactSketch {
}
template<typename A>
+void theta_union_alloc<A>::reset() {
+ state_.reset();
+}
+
+template<typename A>
theta_union_alloc<A>::builder::builder(const A& allocator): theta_base_builder<builder, A>(allocator) {}
template<typename A>
auto theta_union_alloc<A>::builder::build() const -> theta_union_alloc {
- return theta_union_alloc(
- this->starting_sub_multiple(this->lg_k_ + 1, this->MIN_LG_K, static_cast<uint8_t>(this->rf_)),
- this->lg_k_, this->rf_, this->starting_theta(), this->seed_, this->allocator_);
+ return theta_union_alloc(this->starting_lg_size(), this->lg_k_, this->rf_, this->p_, this->starting_theta(), this->seed_, this->allocator_);
}
} /* namespace datasketches */
diff --git a/theta/include/theta_update_sketch_base.hpp b/theta/include/theta_update_sketch_base.hpp
index 9d51c62..30be6b8 100644
--- a/theta/include/theta_update_sketch_base.hpp
+++ b/theta/include/theta_update_sketch_base.hpp
@@ -40,8 +40,8 @@ struct theta_update_sketch_base {
using resize_factor = theta_constants::resize_factor;
using comparator = compare_by_key<ExtractKey>;
- theta_update_sketch_base(uint8_t lg_cur_size, uint8_t lg_nom_size, resize_factor rf, uint64_t theta,
- uint64_t seed, const Allocator& allocator, bool is_empty = true);
+ theta_update_sketch_base(uint8_t lg_cur_size, uint8_t lg_nom_size, resize_factor rf, float p,
+ uint64_t theta, uint64_t seed, const Allocator& allocator, bool is_empty = true);
theta_update_sketch_base(const theta_update_sketch_base& other);
theta_update_sketch_base(theta_update_sketch_base&& other) noexcept;
~theta_update_sketch_base();
@@ -75,6 +75,7 @@ struct theta_update_sketch_base {
uint8_t lg_cur_size_;
uint8_t lg_nom_size_;
resize_factor rf_;
+ float p_;
uint32_t num_entries_;
uint64_t theta_;
uint64_t seed_;
@@ -83,6 +84,7 @@ struct theta_update_sketch_base {
void resize();
void rebuild();
void trim();
+ void reset();
static inline uint32_t get_capacity(uint8_t lg_cur_size, uint8_t lg_nom_size);
static inline uint32_t get_stride(uint64_t key, uint8_t lg_size);
@@ -94,7 +96,7 @@ struct theta_update_sketch_base {
template<typename Derived, typename Allocator>
class theta_base_builder {
public:
- // TODO: Redundant and deprecated. Will be removed in next major verison release.
+ // TODO: Redundant and deprecated. Will be removed in next major version release.
using resize_factor = theta_constants::resize_factor;
static const uint8_t MIN_LG_K = theta_constants::MIN_LG_K;
static const uint8_t MAX_LG_K = theta_constants::MAX_LG_K;
@@ -149,7 +151,6 @@ protected:
uint64_t starting_theta() const;
uint8_t starting_lg_size() const;
- static uint8_t starting_sub_multiple(uint8_t lg_tgt, uint8_t lg_min, uint8_t lg_rf);
};
// key extractor
diff --git a/theta/include/theta_update_sketch_base_impl.hpp b/theta/include/theta_update_sketch_base_impl.hpp
index b4a3124..f8c7998 100644
--- a/theta/include/theta_update_sketch_base_impl.hpp
+++ b/theta/include/theta_update_sketch_base_impl.hpp
@@ -24,15 +24,18 @@
#include <sstream>
#include <algorithm>
+#include "theta_helpers.hpp"
+
namespace datasketches {
template<typename EN, typename EK, typename A>
-theta_update_sketch_base<EN, EK, A>::theta_update_sketch_base(uint8_t lg_cur_size, uint8_t lg_nom_size, resize_factor rf, uint64_t theta, uint64_t seed, const A& allocator, bool is_empty):
+theta_update_sketch_base<EN, EK, A>::theta_update_sketch_base(uint8_t lg_cur_size, uint8_t lg_nom_size, resize_factor rf, float p, uint64_t theta, uint64_t seed, const A& allocator, bool is_empty):
allocator_(allocator),
is_empty_(is_empty),
lg_cur_size_(lg_cur_size),
lg_nom_size_(lg_nom_size),
rf_(rf),
+p_(p),
num_entries_(0),
theta_(theta),
seed_(seed),
@@ -52,6 +55,7 @@ is_empty_(other.is_empty_),
lg_cur_size_(other.lg_cur_size_),
lg_nom_size_(other.lg_nom_size_),
rf_(other.rf_),
+p_(other.p_),
num_entries_(other.num_entries_),
theta_(other.theta_),
seed_(other.seed_),
@@ -77,6 +81,7 @@ is_empty_(other.is_empty_),
lg_cur_size_(other.lg_cur_size_),
lg_nom_size_(other.lg_nom_size_),
rf_(other.rf_),
+p_(other.p_),
num_entries_(other.num_entries_),
theta_(other.theta_),
seed_(other.seed_),
@@ -105,6 +110,7 @@ theta_update_sketch_base<EN, EK, A>& theta_update_sketch_base<EN, EK, A>::operat
std::swap(lg_cur_size_, copy.lg_cur_size_);
std::swap(lg_nom_size_, copy.lg_nom_size_);
std::swap(rf_, copy.rf_);
+ std::swap(p_, copy.p_);
std::swap(num_entries_, copy.num_entries_);
std::swap(theta_, copy.theta_);
std::swap(seed_, copy.seed_);
@@ -119,6 +125,7 @@ theta_update_sketch_base<EN, EK, A>& theta_update_sketch_base<EN, EK, A>::operat
std::swap(lg_cur_size_, other.lg_cur_size_);
std::swap(lg_nom_size_, other.lg_nom_size_);
std::swap(rf_, other.rf_);
+ std::swap(p_, other.p_);
std::swap(num_entries_, other.num_entries_);
std::swap(theta_, other.theta_);
std::swap(seed_, other.seed_);
@@ -248,6 +255,28 @@ void theta_update_sketch_base<EN, EK, A>::trim() {
}
template<typename EN, typename EK, typename A>
+void theta_update_sketch_base<EN, EK, A>::reset() {
+ const size_t cur_size = 1ULL << lg_cur_size_;
+ for (size_t i = 0; i < cur_size; ++i) {
+ if (EK()(entries_[i]) != 0) entries_[i].~EN();
+ }
+ const uint8_t starting_lg_size = theta_build_helper<true>::starting_sub_multiple(
+ lg_nom_size_ + 1, theta_constants::MIN_LG_K, static_cast<uint8_t>(rf_));
+ if (starting_lg_size != lg_cur_size_) {
+ allocator_.deallocate(entries_, cur_size);
+ lg_cur_size_ = starting_lg_size;
+ const size_t new_size = 1ULL << starting_lg_size;
+ entries_ = allocator_.allocate(new_size);
+ for (size_t i = 0; i < new_size; ++i) EK()(entries_[i]) = 0;
+ } else {
+ for (size_t i = 0; i < cur_size; ++i) EK()(entries_[i]) = 0;
+ }
+ num_entries_ = 0;
+ theta_ = theta_build_helper<true>::starting_theta_from_p(p_);
+ is_empty_ = true;
+}
+
+template<typename EN, typename EK, typename A>
void theta_update_sketch_base<EN, EK, A>::consolidate_non_empty(EN* entries, size_t size, size_t num) {
// find the first empty slot
size_t i = 0;
@@ -310,18 +339,12 @@ Derived& theta_base_builder<Derived, Allocator>::set_seed(uint64_t seed) {
template<typename Derived, typename Allocator>
uint64_t theta_base_builder<Derived, Allocator>::starting_theta() const {
- if (p_ < 1) return static_cast<uint64_t>(theta_constants::MAX_THETA * p_);
- return theta_constants::MAX_THETA;
+ return theta_build_helper<true>::starting_theta_from_p(p_);
}
template<typename Derived, typename Allocator>
uint8_t theta_base_builder<Derived, Allocator>::starting_lg_size() const {
- return starting_sub_multiple(lg_k_ + 1, MIN_LG_K, static_cast<uint8_t>(rf_));
-}
-
-template<typename Derived, typename Allocator>
-uint8_t theta_base_builder<Derived, Allocator>::starting_sub_multiple(uint8_t lg_tgt, uint8_t lg_min, uint8_t lg_rf) {
- return (lg_tgt <= lg_min) ? lg_min : (lg_rf == 0) ? lg_tgt : ((lg_tgt - lg_min) % lg_rf) + lg_min;
+ return theta_build_helper<true>::starting_sub_multiple(lg_k_ + 1, MIN_LG_K, static_cast<uint8_t>(rf_));
}
// iterator
diff --git a/theta/test/theta_sketch_test.cpp b/theta/test/theta_sketch_test.cpp
index cbcd0a2..c8283de 100644
--- a/theta/test/theta_sketch_test.cpp
+++ b/theta/test/theta_sketch_test.cpp
@@ -67,6 +67,14 @@ TEST_CASE("theta sketch: non empty no retained keys", "[theta_sketch]") {
REQUIRE(compact_sketch.get_estimate() == 0.0);
REQUIRE(compact_sketch.get_lower_bound(1) == 0.0);
REQUIRE(compact_sketch.get_upper_bound(1) > 0);
+
+ update_sketch.reset();
+ REQUIRE(update_sketch.is_empty());
+ REQUIRE_FALSE(update_sketch.is_estimation_mode());
+ REQUIRE(update_sketch.get_theta() == Approx(0.001));
+ REQUIRE(update_sketch.get_estimate() == 0.0);
+ REQUIRE(update_sketch.get_lower_bound(1) == 0.0);
+ REQUIRE(update_sketch.get_upper_bound(1) == 0.0);
}
TEST_CASE("theta sketch: single item", "[theta_sketch]") {
@@ -105,6 +113,14 @@ TEST_CASE("theta sketch: resize exact", "[theta_sketch]") {
REQUIRE(compact_sketch.get_estimate() == 2000.0);
REQUIRE(compact_sketch.get_lower_bound(1) == 2000.0);
REQUIRE(compact_sketch.get_upper_bound(1) == 2000.0);
+
+ update_sketch.reset();
+ REQUIRE(update_sketch.is_empty());
+ REQUIRE_FALSE(update_sketch.is_estimation_mode());
+ REQUIRE(update_sketch.get_theta() == 1.0);
+ REQUIRE(update_sketch.get_estimate() == 0.0);
+ REQUIRE(update_sketch.get_lower_bound(1) == 0.0);
+ REQUIRE(update_sketch.get_upper_bound(1) == 0.0);
}
TEST_CASE("theta sketch: estimation", "[theta_sketch]") {
diff --git a/theta/test/theta_union_test.cpp b/theta/test/theta_union_test.cpp
index a8b3878..0deb0c0 100644
--- a/theta/test/theta_union_test.cpp
+++ b/theta/test/theta_union_test.cpp
@@ -51,35 +51,41 @@ TEST_CASE("theta union: non empty no retained keys", "[theta_union]") {
}
TEST_CASE("theta union: exact mode half overlap", "[theta_union]") {
- update_theta_sketch sketch1 = update_theta_sketch::builder().build();
+ auto sketch1 = update_theta_sketch::builder().build();
int value = 0;
for (int i = 0; i < 1000; i++) sketch1.update(value++);
- update_theta_sketch sketch2 = update_theta_sketch::builder().build();
+ auto sketch2 = update_theta_sketch::builder().build();
value = 500;
for (int i = 0; i < 1000; i++) sketch2.update(value++);
- theta_union u = theta_union::builder().build();
+ auto u = theta_union::builder().build();
u.update(sketch1);
u.update(sketch2);
- compact_theta_sketch sketch3 = u.get_result();
+ auto sketch3 = u.get_result();
REQUIRE_FALSE(sketch3.is_empty());
REQUIRE_FALSE(sketch3.is_estimation_mode());
REQUIRE(sketch3.get_estimate() == 1500.0);
+
+ u.reset();
+ sketch3 = u.get_result();
+ REQUIRE(sketch3.get_num_retained() == 0);
+ REQUIRE(sketch3.is_empty());
+ REQUIRE_FALSE(sketch3.is_estimation_mode());
}
TEST_CASE("theta union: exact mode half overlap wrapped compact", "[theta_union]") {
- update_theta_sketch sketch1 = update_theta_sketch::builder().build();
+ auto sketch1 = update_theta_sketch::builder().build();
int value = 0;
for (int i = 0; i < 1000; i++) sketch1.update(value++);
auto bytes1 = sketch1.compact().serialize();
- update_theta_sketch sketch2 = update_theta_sketch::builder().build();
+ auto sketch2 = update_theta_sketch::builder().build();
value = 500;
for (int i = 0; i < 1000; i++) sketch2.update(value++);
auto bytes2 = sketch2.compact().serialize();
- theta_union u = theta_union::builder().build();
+ auto u = theta_union::builder().build();
u.update(wrapped_compact_theta_sketch::wrap(bytes1.data(), bytes1.size()));
u.update(wrapped_compact_theta_sketch::wrap(bytes2.data(), bytes2.size()));
compact_theta_sketch sketch3 = u.get_result();
@@ -89,22 +95,28 @@ TEST_CASE("theta union: exact mode half overlap wrapped compact", "[theta_union]
}
TEST_CASE("theta union: estimation mode half overlap", "[theta_union]") {
- update_theta_sketch sketch1 = update_theta_sketch::builder().build();
+ auto sketch1 = update_theta_sketch::builder().build();
int value = 0;
for (int i = 0; i < 10000; i++) sketch1.update(value++);
- update_theta_sketch sketch2 = update_theta_sketch::builder().build();
+ auto sketch2 = update_theta_sketch::builder().build();
value = 5000;
for (int i = 0; i < 10000; i++) sketch2.update(value++);
- theta_union u = theta_union::builder().build();
+ auto u = theta_union::builder().build();
u.update(sketch1);
u.update(sketch2);
- compact_theta_sketch sketch3 = u.get_result();
+ auto sketch3 = u.get_result();
REQUIRE_FALSE(sketch3.is_empty());
REQUIRE(sketch3.is_estimation_mode());
REQUIRE(sketch3.get_estimate() == Approx(15000).margin(15000 * 0.01));
//std::cerr << sketch3.to_string(true);
+
+ u.reset();
+ sketch3 = u.get_result();
+ REQUIRE(sketch3.get_num_retained() == 0);
+ REQUIRE(sketch3.is_empty());
+ REQUIRE_FALSE(sketch3.is_estimation_mode());
}
TEST_CASE("theta union: seed mismatch", "[theta_union]") {
diff --git a/tuple/include/array_of_doubles_sketch.hpp b/tuple/include/array_of_doubles_sketch.hpp
index af9e87a..4c468a3 100644
--- a/tuple/include/array_of_doubles_sketch.hpp
+++ b/tuple/include/array_of_doubles_sketch.hpp
@@ -122,7 +122,7 @@ public:
private:
// for builder
- update_array_of_doubles_sketch_alloc(uint8_t lg_cur_size, uint8_t lg_nom_size, resize_factor rf, uint64_t theta,
+ update_array_of_doubles_sketch_alloc(uint8_t lg_cur_size, uint8_t lg_nom_size, resize_factor rf, float p, uint64_t theta,
uint64_t seed, const array_of_doubles_update_policy<A>& policy, const A& allocator);
};
diff --git a/tuple/include/array_of_doubles_sketch_impl.hpp b/tuple/include/array_of_doubles_sketch_impl.hpp
index b494d66..1f0c5dd 100644
--- a/tuple/include/array_of_doubles_sketch_impl.hpp
+++ b/tuple/include/array_of_doubles_sketch_impl.hpp
@@ -21,8 +21,8 @@ namespace datasketches {
template<typename A>
update_array_of_doubles_sketch_alloc<A>::update_array_of_doubles_sketch_alloc(uint8_t lg_cur_size, uint8_t lg_nom_size, resize_factor rf,
- uint64_t theta, uint64_t seed, const array_of_doubles_update_policy<A>& policy, const A& allocator):
-Base(lg_cur_size, lg_nom_size, rf, theta, seed, policy, allocator) {}
+ float p, uint64_t theta, uint64_t seed, const array_of_doubles_update_policy<A>& policy, const A& allocator):
+Base(lg_cur_size, lg_nom_size, rf, p, theta, seed, policy, allocator) {}
template<typename A>
@@ -43,7 +43,7 @@ tuple_base_builder<builder, array_of_doubles_update_policy<A>, A>(policy, alloca
template<typename A>
update_array_of_doubles_sketch_alloc<A> update_array_of_doubles_sketch_alloc<A>::builder::build() const {
- return update_array_of_doubles_sketch_alloc<A>(this->starting_lg_size(), this->lg_k_, this->rf_, this->starting_theta(), this->seed_, this->policy_, this->allocator_);
+ return update_array_of_doubles_sketch_alloc<A>(this->starting_lg_size(), this->lg_k_, this->rf_, this->p_, this->starting_theta(), this->seed_, this->policy_, this->allocator_);
}
// compact sketch
diff --git a/tuple/include/array_of_doubles_union.hpp b/tuple/include/array_of_doubles_union.hpp
index 592c1f9..06ca0b6 100644
--- a/tuple/include/array_of_doubles_union.hpp
+++ b/tuple/include/array_of_doubles_union.hpp
@@ -61,7 +61,7 @@ public:
private:
// for builder
- array_of_doubles_union_alloc(uint8_t lg_cur_size, uint8_t lg_nom_size, resize_factor rf, uint64_t theta, uint64_t seed, const Policy& policy, const Allocator& allocator);
+ array_of_doubles_union_alloc(uint8_t lg_cur_size, uint8_t lg_nom_size, resize_factor rf, float p, uint64_t theta, uint64_t seed, const Policy& policy, const Allocator& allocator);
};
template<typename Allocator>
diff --git a/tuple/include/array_of_doubles_union_impl.hpp b/tuple/include/array_of_doubles_union_impl.hpp
index 57899d9..c3fabf0 100644
--- a/tuple/include/array_of_doubles_union_impl.hpp
+++ b/tuple/include/array_of_doubles_union_impl.hpp
@@ -20,8 +20,8 @@
namespace datasketches {
template<typename A>
-array_of_doubles_union_alloc<A>::array_of_doubles_union_alloc(uint8_t lg_cur_size, uint8_t lg_nom_size, resize_factor rf, uint64_t theta, uint64_t seed, const Policy& policy, const A& allocator):
-Base(lg_cur_size, lg_nom_size, rf, theta, seed, policy, allocator)
+array_of_doubles_union_alloc<A>::array_of_doubles_union_alloc(uint8_t lg_cur_size, uint8_t lg_nom_size, resize_factor rf, float p, uint64_t theta, uint64_t seed, const Policy& policy, const A& allocator):
+Base(lg_cur_size, lg_nom_size, rf, p, theta, seed, policy, allocator)
{}
template<typename A>
@@ -37,7 +37,7 @@ tuple_base_builder<builder, Policy, A>(policy, allocator) {}
template<typename A>
array_of_doubles_union_alloc<A> array_of_doubles_union_alloc<A>::builder::build() const {
- return array_of_doubles_union_alloc<A>(this->starting_lg_size(), this->lg_k_, this->rf_, this->starting_theta(), this->seed_, this->policy_, this->allocator_);
+ return array_of_doubles_union_alloc<A>(this->starting_lg_size(), this->lg_k_, this->rf_, this->p_, this->starting_theta(), this->seed_, this->policy_, this->allocator_);
}
} /* namespace datasketches */
diff --git a/tuple/include/tuple_sketch.hpp b/tuple/include/tuple_sketch.hpp
index 14d3871..8a7ea50 100644
--- a/tuple/include/tuple_sketch.hpp
+++ b/tuple/include/tuple_sketch.hpp
@@ -325,6 +325,11 @@ public:
void trim();
/**
+ * Reset the sketch to the initial empty state
+ */
+ void reset();
+
+ /**
* Converts this sketch to a compact sketch (ordered or unordered).
* @param ordered optional flag to specify if ordered sketch should be produced
* @return compact sketch
@@ -341,7 +346,7 @@ protected:
tuple_map map_;
// for builder
- update_tuple_sketch(uint8_t lg_cur_size, uint8_t lg_nom_size, resize_factor rf, uint64_t theta, uint64_t seed, const Policy& policy, const Allocator& allocator);
+ update_tuple_sketch(uint8_t lg_cur_size, uint8_t lg_nom_size, resize_factor rf, float p, uint64_t theta, uint64_t seed, const Policy& policy, const Allocator& allocator);
virtual void print_specifics(std::ostringstream& os) const;
};
diff --git a/tuple/include/tuple_sketch_impl.hpp b/tuple/include/tuple_sketch_impl.hpp
index fdd91f8..37b0436 100644
--- a/tuple/include/tuple_sketch_impl.hpp
+++ b/tuple/include/tuple_sketch_impl.hpp
@@ -82,9 +82,9 @@ string<A> tuple_sketch<S, A>::to_string(bool detail) const {
// update sketch
template<typename S, typename U, typename P, typename A>
-update_tuple_sketch<S, U, P, A>::update_tuple_sketch(uint8_t lg_cur_size, uint8_t lg_nom_size, resize_factor rf, uint64_t theta, uint64_t seed, const P& policy, const A& allocator):
+update_tuple_sketch<S, U, P, A>::update_tuple_sketch(uint8_t lg_cur_size, uint8_t lg_nom_size, resize_factor rf, float p, uint64_t theta, uint64_t seed, const P& policy, const A& allocator):
policy_(policy),
-map_(lg_cur_size, lg_nom_size, rf, theta, seed, allocator)
+map_(lg_cur_size, lg_nom_size, rf, p, theta, seed, allocator)
{}
template<typename S, typename U, typename P, typename A>
@@ -215,6 +215,11 @@ void update_tuple_sketch<S, U, P, A>::trim() {
}
template<typename S, typename U, typename P, typename A>
+void update_tuple_sketch<S, U, P, A>::reset() {
+ map_.reset();
+}
+
+template<typename S, typename U, typename P, typename A>
auto update_tuple_sketch<S, U, P, A>::begin() -> iterator {
return iterator(map_.entries_, 1 << map_.lg_cur_size_, 0);
}
@@ -582,7 +587,7 @@ tuple_base_builder<builder, P, A>(policy, allocator) {}
template<typename S, typename U, typename P, typename A>
auto update_tuple_sketch<S, U, P, A>::builder::build() const -> update_tuple_sketch {
- return update_tuple_sketch(this->starting_lg_size(), this->lg_k_, this->rf_, this->starting_theta(), this->seed_, this->policy_, this->allocator_);
+ return update_tuple_sketch(this->starting_lg_size(), this->lg_k_, this->rf_, this->p_, this->starting_theta(), this->seed_, this->policy_, this->allocator_);
}
} /* namespace datasketches */
diff --git a/tuple/include/tuple_union.hpp b/tuple/include/tuple_union.hpp
index d9eff26..1c518da 100644
--- a/tuple/include/tuple_union.hpp
+++ b/tuple/include/tuple_union.hpp
@@ -80,11 +80,16 @@ public:
*/
CompactSketch get_result(bool ordered = true) const;
+ /**
+ * Reset the union to the initial empty state
+ */
+ void reset();
+
protected:
State state_;
// for builder
- tuple_union(uint8_t lg_cur_size, uint8_t lg_nom_size, resize_factor rf, uint64_t theta, uint64_t seed, const Policy& policy, const Allocator& allocator);
+ tuple_union(uint8_t lg_cur_size, uint8_t lg_nom_size, resize_factor rf, float p, uint64_t theta, uint64_t seed, const Policy& policy, const Allocator& allocator);
};
template<typename S, typename P, typename A>
diff --git a/tuple/include/tuple_union_impl.hpp b/tuple/include/tuple_union_impl.hpp
index 4b3b0a5..98ea8a5 100644
--- a/tuple/include/tuple_union_impl.hpp
+++ b/tuple/include/tuple_union_impl.hpp
@@ -20,8 +20,8 @@
namespace datasketches {
template<typename S, typename P, typename A>
-tuple_union<S, P, A>::tuple_union(uint8_t lg_cur_size, uint8_t lg_nom_size, resize_factor rf, uint64_t theta, uint64_t seed, const P& policy, const A& allocator):
-state_(lg_cur_size, lg_nom_size, rf, theta, seed, internal_policy(policy), allocator)
+tuple_union<S, P, A>::tuple_union(uint8_t lg_cur_size, uint8_t lg_nom_size, resize_factor rf, float p, uint64_t theta, uint64_t seed, const P& policy, const A& allocator):
+state_(lg_cur_size, lg_nom_size, rf, p, theta, seed, internal_policy(policy), allocator)
{}
template<typename S, typename P, typename A>
@@ -36,12 +36,17 @@ auto tuple_union<S, P, A>::get_result(bool ordered) const -> CompactSketch {
}
template<typename S, typename P, typename A>
+void tuple_union<S, P, A>::reset() {
+ return state_.reset();
+}
+
+template<typename S, typename P, typename A>
tuple_union<S, P, A>::builder::builder(const P& policy, const A& allocator):
tuple_base_builder<builder, P, A>(policy, allocator) {}
template<typename S, typename P, typename A>
auto tuple_union<S, P, A>::builder::build() const -> tuple_union {
- return tuple_union(this->starting_lg_size(), this->lg_k_, this->rf_, this->starting_theta(), this->seed_, this->policy_, this->allocator_);
+ return tuple_union(this->starting_lg_size(), this->lg_k_, this->rf_, this->p_, this->starting_theta(), this->seed_, this->policy_, this->allocator_);
}
} /* namespace datasketches */
diff --git a/tuple/test/array_of_doubles_sketch_test.cpp b/tuple/test/array_of_doubles_sketch_test.cpp
index d40491f..1451a6f 100644
--- a/tuple/test/array_of_doubles_sketch_test.cpp
+++ b/tuple/test/array_of_doubles_sketch_test.cpp
@@ -36,6 +36,17 @@ const std::string inputPath = TEST_BINARY_INPUT_PATH;
const std::string inputPath = "test/";
#endif
+TEST_CASE("aod sketch: reset", "[tuple_sketch]") {
+ auto update_sketch = update_array_of_doubles_sketch::builder().build();
+ std::vector<double> a = {1};
+ update_sketch.update(1, a);
+ REQUIRE(!update_sketch.is_empty());
+ REQUIRE(update_sketch.get_num_retained() == 1);
+ update_sketch.reset();
+ REQUIRE(update_sketch.is_empty());
+ REQUIRE(update_sketch.get_num_retained() == 0);
+}
+
TEST_CASE("aod sketch: serialization compatibility with java - empty", "[tuple_sketch]") {
auto update_sketch = update_array_of_doubles_sketch::builder().build();
REQUIRE(update_sketch.is_empty());
@@ -263,6 +274,11 @@ TEST_CASE("aod union: half overlap", "[tuple_sketch]") {
u.update(update_sketch2);
auto result = u.get_result();
REQUIRE(result.get_estimate() == Approx(1500).margin(0.01));
+
+ u.reset();
+ result = u.get_result();
+ REQUIRE(result.is_empty());
+ REQUIRE(result.get_num_retained() == 0);
}
TEST_CASE("aod intersection: half overlap", "[tuple_sketch]") {
diff --git a/tuple/test/tuple_sketch_test.cpp b/tuple/test/tuple_sketch_test.cpp
index e6a87f1..39d7265 100644
--- a/tuple/test/tuple_sketch_test.cpp
+++ b/tuple/test/tuple_sketch_test.cpp
@@ -151,6 +151,16 @@ TEST_CASE("tuple sketch float: exact mode", "[tuple_sketch]") {
++it;
}
}
+
+ update_sketch.reset();
+ REQUIRE(update_sketch.is_empty());
+ REQUIRE(!update_sketch.is_estimation_mode());
+ REQUIRE(update_sketch.get_estimate() == 0);
+ REQUIRE(update_sketch.get_lower_bound(1) == 0);
+ REQUIRE(update_sketch.get_upper_bound(1) == 0);
+ REQUIRE(update_sketch.get_theta() == 1);
+ REQUIRE(update_sketch.get_num_retained() == 0);
+ REQUIRE(!update_sketch.is_ordered());
}
template<typename T>
diff --git a/tuple/test/tuple_union_test.cpp b/tuple/test/tuple_union_test.cpp
index 10c9a25..7e172c0 100644
--- a/tuple/test/tuple_union_test.cpp
+++ b/tuple/test/tuple_union_test.cpp
@@ -81,6 +81,13 @@ TEST_CASE("tuple_union float: simple case", "[tuple union]") {
u.update(update_sketch2);
auto result = u.get_result();
REQUIRE(result.get_num_retained() == 3);
+
+ u.reset();
+ result = u.get_result();
+ REQUIRE(result.is_empty());
+ REQUIRE(result.get_num_retained() == 0);
+ REQUIRE(!result.is_estimation_mode());
+ REQUIRE(result.get_estimate() == 0);
}
TEST_CASE("tuple_union float: exact mode half overlap", "[tuple union]") {
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@datasketches.apache.org
For additional commands, e-mail: commits-help@datasketches.apache.org